/*2019-11-16
问题描述
小a学习了树状数组之后，对lowbit很感兴趣，于是出了一道题。
给定非负整数n。记lowbit(x)为x的二进制表示下最低位的1所对应的值，
如，某个数x最低位的1分别在第1,2,3位时,lowbit(x)分别是1,2,4。求sum∑(i=0,2^n)lowbit(i)。
输出答案对998244353取模后的结果。T组数据。
输入描述:
第一行一个整数T，表示数据组数。
接下来T行每行一个整数n，含义如题目描述所示。
输出描述:
输出T表示每次询问的结果。
示例1
输入
2
2
4
输出
8
48
说明
n=2时，Ans=sum∑(i=0,4)lowbit(i)=0+1+2+1+4=8。
备注
T<=3*10^5,n≤10^18。
输入数据量可能较大，建议使用较快的读入方式
*/
/*
解题思路：
ans=(n+1)*2^(n-1)+2^(n-1)=(n+2)*2^(n-1);
首先0~2^n的奇数位最低位的1代表的值为1，求和为sum1=1*2^(n-1)
再看偶数位的数最低位的1所代表的值，可以发现，在每个n=1~n,2^n左右，最低位1的数值呈对称分布，求和sum2=(n-1)*2^(n-1)+2^n=(n+1)*2^(n-1)
*/
1 //方法1：因为n<=10^18,可以直接用%lld读入(long long,-2^63-1~2^63-1;unsigned long long,0~2^64-1-------远远大于10^18) 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 const int mod=998244353; 6 ll fastpow(ll a,ll n) 7 { 8 ll b=a,res=1; 9 while(n){ 10 if(n&1) res=(b*res)%mod; 11 b=(b*b)%mod; 12 n>>=1; 13 } 14 return res; 15 } 16 int main() 17 { 18 int T; 19 scanf("%d", &T); 20 while (T--){ 21 ll n; 22 scanf("%lld",&n); 23 if(n==0){ 24 printf("%lld\n", 1); 25 continue; 26 } 27 ll tem=fastpow(2,n-1); 28 n=(n+2)%mod; 29 printf("%lld\n",(n*tem)%mod); 30 } 31 return 0; 32 }
1 //拓展，n>=10^18;用数组读入 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 const int mod=998244353; 6 ll fastpow(ll a,ll n) 7 { 8 ll b=a,res=1; 9 while(n){ 10 if(n&1) res=(b*res)%mod; 11 b=(b*b)%mod; 12 n>>=1; 13 } 14 return res; 15 } 16 int main() 17 { 18 ll T; 19 scanf("%lld",&T); 20 while(T--){ 21 ll n=0,cnt=0; 22 char s[20]; 23 scanf("%s",s); 24 int le=strlen(s); 25 if(le==1&&s[0]=='0'){ 26 printf("1\n"); 27 continue; 28 } 29 int i=0; 30 while(le--){ 31 n=n*10+s[i++]-'0'; 32 if(n>=mod) cnt=cnt*10+(int)(n/mod); 33 else cnt=cnt*10; 34 n%=mod; 35 } 36 ll ans=1; 37 if(cnt){ 38 ll tem=0; 39 tem=fastpow(2,mod); 40 ans=fastpow(tem,cnt-1); 41 if(n==0) ans=(ans*tem/2)%mod; 42 else ans=ans*tem%mod; 43 } 44 if(n){ 45 ll tmp=fastpow(2,n-1); 46 ans=ans*tmp%mod; 47 } 48 ans=(ans*(n+2)%mod)%mod; 49 printf("%lld\n",ans); 50 } 51 return 0; 52 }
还有个拓展之后再写