欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客练习赛54B-求和

程序员文章站 2022-07-07 15:46:03
...

链接:https://ac.nowcoder.com/acm/contest/1842/B
来源:牛客网

题目描述

牛客练习赛54B-求和

输入描述:

第一行一个整数T,表示数据组数。
接下来T行每行一个整数n,含义如题目描述所示。

输出描述:

输出T行,表示每次询问的结果。

示例1

输入

2
2
4

输出

8
48

说明
牛客练习赛54B-求和

备注:

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)。

由于数据范围较大,所以我们直接使用矩阵快速幂:
牛客练习赛54B-求和

#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;
}