[题解] 送分 二项式展开

题目描述

数据范围:$n,m \leq 10^5,~ a_i,x < 998244353$n,m≤105, ai​,x<998244353

题解

看到这种异或统计答案的题可以立马想到二进制拆分的套路。

我们可以对每一个二进制位分别讨论：

设$a$a中所有元素第$bit$bit位为$1$1的个数有$num1$num1个，为$0$0的有$num0$num0个。

那么有贡献时当且仅当$bit$bit位为$1$1的被选了奇数次，为$0$0的被选任意次。

设第$bit$bit位为$1$1的有$i$i个被选，为$0$0的有$j$j个被选。

那么贡献为:

$C_{num1}^{i} \times C_{num0}^{j} \times x^{i+j} ~~~~(i为奇数)$Cnum1i​×Cnum0j​×xi+j    (i为奇数)

把这个式子变一下为:

$(C_{num1}^{i} \times x^{i}) \times (C_{num0}^{j} \times x^{j}) ~~~~(i为奇数)$(Cnum1i​×xi)×(Cnum0j​×xj)    (i为奇数)

考虑将所有的式子相加后合并起来，那么右边这个可以写成 $\sum_{j=1}^{num0}{x^j}$∑j=1num0​xj,显然为$(x+1)^{j}$(x+1)j的展开式。

那么左边这个式子可以写成:
$\sum_{i=1,i为奇数}^{num1}{x^i}$i=1,i为奇数∑num1​xi

根据套路，可以直接写成$\frac{(1+x)^{i}-(1-x)^{i}}{2}$2(1+x)i−(1−x)i​。

那么两部分就都可以快速幂计算$O(logn)$O(logn)出来,那么对于每个询问既可以$O(log^2n)$O(log2n)做了。

$\mathcal{Code}$Code

/*******************************
Author:galaxy yr
LANG:C++
Created Time:2019年10月16日 星期三 08时21分01秒
*******************************/
#include<cstdio>
#include<algorithm>
#define int long long

using namespace std;

struct IO{
    template<typename T>
    IO & operator>>(T&res)
    {
        T q=1;char ch;
        while((ch=getchar())<'0' or ch>'9')if(ch=='-')q=-q;
        res=(ch^48);
        while((ch=getchar())>='0' and ch<='9') res=(res<<1)+(res<<3)+(ch^48);
        res*=q;
        return *this;
    }
}cin;

const int maxn=1e5+10;
const int MAXN=1005;
const int inv=499122177;
const int LG=30;
const int mod=998244353;
int n,a[maxn],m,sum[maxn][LG+1],md,lim;

int ksm(long long a,int b)
{
    int res=1; a=(a+mod)%mod;
    while(b)
    {
        if(b&1)
            res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}

void init()
{
    for(int i=LG;i>=0;i--)
        if(md>(1<<i))
        {
            lim=i+1;
            break;
        }
    for(int i=1;i<=n;i++)
    {
        for(int j=LG;j>=0;j--)
        {
            sum[i][j]=sum[i-1][j];
            if(a[i]&(1<<j))
                sum[i][j]++;
        }
    }
}

void solve(int l,int r,int x)
{
    long long ans=0;
    for(int k=0;k<=lim;k++)
    {
        int a=sum[r][k]-sum[l-1][k],b=r-l+1-a;
        ans=(ans+(1ll*ksm(1+x,a)-ksm(1-x,a)+mod)%mod*inv%mod*ksm(1+x,b)%mod*(1<<k)%mod)%mod;
    }
    printf("%lld\n",ans);
}

signed main()
{
    //freopen("score.in","r",stdin);
    //freopen("score.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i],md=max(a[i],md);
    init();
    int l,r,x;
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r>>x;
        solve(l,r,x);
    }
    return 0;
}