题解 | #求和#

玄学做法：
打表找规律：

根据递推公式：$a_n=2\ast a_{n-1}+2^{n-1}a\_n=2*a\_\{n-1\}+2^\{n-1\}$
可以得到：$a_n=n\ast 2^{n-1}+2^{n}a\_n=n*2^\{n-1\}+2^\{n\}$
逻辑做法:
注：${10_n}_2\{10\_n\}\_2$表示二进制写法，1后面有n个0
对于$a_{n}a\_n$，最终目标是${10_n}_2\{10\_n\}\_2$。对于${\sum }_{i=0}^{2^n}lowbit(i)\backslash sum\_\{i=0\}^\{2^n\}lowbit(i)$相当于二进制从$11$加到${10_n}_2\{10\_n\}\_2$，那么
${10_n}_2={10_{n-1}}_2+{10_{n-2}}_2+\mathrm{.}\mathrm{.}\mathrm{.}+{10_0}_2\{10\_n\}\_2=\{10\_\{n-1\}\}\_2+\{10\_\{n-2\}\}\_2+...+\{10\_\{0\}\}\_2$
表示出来就可以得到$a_n={\sum }_{i=0}^{n-1}{a}_i+2^{n}a\_n=\backslash sum\_\{i=0\}^\{n-1\}a\_i+2^\{n\}$
$=2\ast a_{n-1}+2^{n-1}=2*a\_\{n-1\}+2^\{n-1\}$
AC代码

#include <bits/stdc++.h>
#define end '\n'
using namespace std;
const long long mod = 998244353;
inline void IOS()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
}
long long qpow(long long a, long long b)
{
    long long ans = 1;
    if(b<0)
        return 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
unsigned long long n;
void dilingtian()
{
    __int128 ans = ((__int128)qpow(2, n - 1) * (__int128)n % (__int128)mod + (__int128)qpow(2, n)) % (__int128)mod;
    printf("%lld\n", (int)ans);
}
int main(void)
{
    // IOS();
    long long t;
    scanf("%lld",&t);
    while (t--)
    {
        scanf("%lld", &n);
        dilingtian();
    }
    return 0;
}