牛客练习赛54B-求和
程序员文章站
2022-07-07 15:46:03
...
链接:https://ac.nowcoder.com/acm/contest/1842/B
来源:牛客网
题目描述
输入描述:
第一行一个整数T,表示数据组数。 接下来T行每行一个整数n,含义如题目描述所示。输出描述:
输出T行,表示每次询问的结果。示例1
输入
2 2 4输出
8 48说明
备注:
T≤3×1e5, n≤1e18。 输入数据量可能较大,建议使用较快的读入方式。
题目大意:
给定一个数n,让计算i从0开始到2^n的每一个数字的lowbit的和。
题解:
由于数据范围较大,可以把前面的几个数据给找到,然后看看是否能够找到规律:
n | 1 | 2 | 3 | 4 | 5 |
2^n | 2 | 4 | 8 | 16 | 32 |
lowbit和 | 3 | 8 | 20 | 48 | 112 |
规律1:
我们发现8=2*2+4=2*2^1+2^2
20=3*4+8=3*2^2+2^3
48=4*8+16=4*2^3+2^4
也就是对于输入的n,它的lowbit 的和是n*2^(n-1)+2^n,由于输入的n较大,所以需要使用快速幂:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll pow_mod(ll a,ll n,ll mod)
{
ll ret=1;
ll temp=a%mod;
while(n)
{
if(n&1)
ret=(ret%mod*temp%mod)%mod;
temp=(temp%mod)*(temp%mod)%mod;
n>>=1;
}
return ret;
}
ll solve(ll x)
{
return ((x%mod*pow_mod(2,x-1,mod))%mod+pow_mod(2,x,mod)%mod)%mod;
}
int main()
{
int T;
ll number;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&number);
if(number==0)
printf("1\n");
else
printf("%lld\n",solve(number));
}
return 0;
}
规律2:
n | 1 | 2 | 3 | 4 | 5 |
2^n | 2 | 4 | 8 | 16 | 32 |
lowbit和 | 3 | 8 | 20 | 48 | 112 |
当n=1时:结果=3=2*1+2(1-1)
当n=2时:结果=8=2*3+2^(2-1)
当n=3时:结果=20=2*8+2^(3-1)
也就是对于n=x,它的结果就等于2*(n=x-1的结果)*2^(x-1)。
由于数据范围较大,所以我们直接使用矩阵快速幂:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll x;
int n;
int lowbit(int x)
{
return x&(-x);
}
ll binaryPow(ll a, ll b, ll m)
{
ll ans=1;
while(b>0)
{
if(b&1)
{
ans=ans*a%m;
}
a=a*a%m;
b>>=1;
}
return ans;
}
struct xiao
{
ll f[4][4];
} ans,mapp;
void init(xiao &ans)
{
for(int i=0; i<2; ++i)
{
for(int j=0; j<2; ++j)
{
if(i==j)
ans.f[i][j]=1;
else
ans.f[i][j]=0;
}
}
}
void power(xiao &x,xiao &y,xiao &z)
{
memset(z.f,0,sizeof(z.f));
for(int i=0; i<2; ++i)
{
for(int j=0; j<2; ++j)
{
if(x.f[i][j])
{
for(int k=0; k<2; ++k)
{
z.f[i][k]+=(x.f[i][j]%mod*y.f[j][k]%mod)%mod;
z.f[i][k]%=mod;
}
}
}
}
}
ll solve(ll k)
{
init(ans);
ll number=k-1;
xiao temp=mapp,t;
while(number)
{
if(number%2==1)
{
power(ans,temp,t);
ans=t;
}
power(temp,temp,t);
temp=t;
number/=2;
}
return (ans.f[0][0]*3+ans.f[0][1]*2)%mod;
}
int main()
{
mapp.f[0][0]=2;
mapp.f[0][1]=1;
mapp.f[1][0]=0;
mapp.f[1][1]=2;
scanf("%d",&n);
while(n--)
{
scanf("%lld",&x);
if(x==0)
printf("1\n");
else
printf("%lld\n",solve(x));
}
return 0;
}