求
\[\sum_{i=0}^{2^{n}}{lowbit(i)} \]
\((n≤10^{18})\)答案对998244353取模
lowbit
首先数组数组里经常出现的lowit函数
对于lowbit
给定非负整数n。记lowbit(x)为x的二进制表示下最低位的1所对应的值
比如
lowbit(1),1的二进制位1,最低为对应的是1
lowbit(3),3的二进制为11,最低位对应的是1
lowbit(4),4的二进制为100,最低位对应的是4
一般来说2^n的lowbit为本身，奇数的lowbit为1
比如n=2
\(\sum_{i=0}^{2^{n}}{lowbit(i)}\\ = \sum_{i=0}^{4}{lowbit(i)}\\ = lowbit(0) + lowbit(1)+ lowbit(2)+ lowbit(3)+ lowbit(4)\)
而对于\(lowbit(0)=0,lowbit(2^{n})=2^{n}\)
而对于\(2^{n}有2^{n-1}个奇数\)
所以式子变成了求
\(lowbit(2) + lowbit(4) +lowbit(6).....+lowbit(2^{n-1})+2^{n}+2^{n-1}\)
\(令x=lowbit(2) + lowbit(4) +lowbit(6).....+lowbit(2^{n-1})\)
打表
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#define ll long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return f*x;
}
ll lowbit(ll x){
return (x&(-x)) % mod;
}
ll quickpow(ll a,ll b){
ll ans = 1;
while(b){
if(b&1) ans = ans * a % mod;
b >>= 1;
a = a * a%mod;
}
return ans;
}
void debug(){
for(ll n = 1; n <= 20; n++){
ll all = quickpow(2,n);
ll ans = 0;
for(ll j = 1;j <= all; j++){
ans = (ans + lowbit(j)) % mod;
}
cout<<n<<" "<<ans<<" "<<ans-all-all/2<<endl;
}
}
int main(){
debug();
return 0;
}打表发现规律
n x
1 0
2 2
3 8
4 24
5 64
6 160
7 384
8 896
9 2048
10 4608
11 10240
12 22528
13 49152
14 106496
15 229376
16 491520
17 1048576
18 2228224
19 4718592
20 9961472推导
发现\(a_{n+1}=2a_{n}+2^{n}\)
所以理由生成函数解
\(a_{n+1}-2a_{n} = 2^{n}\)
①求齐次
\(a_{n+1}-2a_{n} = 0\)
$ x-2=0 \(解得\)x=2\(，所以通解为\)c_{1}2^{n}$
②求非齐次
\(x=2\)为1重根且等于常数，所以特解为\(Pn2^{n}\)
代入非齐次\(P(n+1)2^{n+1}=2Pn2^{n}+2^{n}\)
解得\(P=\frac{1}{2}\)
特解为\(n2^{n-1}\)
③求解
解为齐次通解+非齐次特解
\(x =c_{1}2^{n}+ n2^{n-1} ，其中n=1时，x=0\)
\(c_{1}=-\frac{1}{2}\)
\(x = (n-1)2^{n-1}\)
与上面合并得到
\(a_{n} = (n-1)2^{n-1}+2^{n}+2^{n-1} = (n+2)2^{n-1}\)
\(∴a_{n} = (n+2)2^{n-1}\)
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define ll long long
#define mod 998244353
using namespace std;
const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
ll pow(ll a,ll b,ll p){
ll ans = 1;
while(b){
if(b&1)ans = ans * a % p;
b >>= 1;
a = a * a %p;
}
return ans;
}
void getans(ll n){
if(n == 0)cout<<"1"<<endl;
else{
ll ans = ((n + 2) % mod) * (pow(2,n-1,mod) %mod) %mod;
cout<<ans<<endl;
}
}
int main(){
ll t = read();
while(t--){
ll n = read();
getans(n);
}
return 0;
}