P4456题解

· · 个人记录

题意

称没有连续 1 的 01 序列为交错序列。定义一个 01 序列的权值为 x^ay^b，其中 x 和 y 分别是序列中 0 和 1 的个数，a,b 为给定常数。求所有长度为 n 的交错序列的权值和。答案对质数 m 取模。

思路

枚举 1 的个数可知答案为

(\ \sum_{i=0}^n\binom{n-i+1}{i}i^b(n-i)^a\ )\bmod m

发现 n\leq 10^7，所以可以考虑枚举 i。

现在问题在于如何 {\rm O}(n) 地对于所有的 i 计算 i^k \bmod m 和 \binom{n-i+1}{i}\bmod m。

首先设函数 f(x)=x^k。发现 f 是积性函数，所以可以用线性筛求出。具体来说，我们在质数处使用快速幂求出 i^k，在和数处在被筛掉的时候计算。这部分的时间复杂度为 {\rm O}(n+\frac{n\log ab}{\log n})={\rm O}(n)。

现在我们需要计算 \binom{n-i+1}{i}\bmod m=\frac{(n-i+1)!}{i!(n-2i+1)!}\bmod m。一个简单的思路是预处理出 i! 和 \frac{1}{i!}。

很遗憾，被我卡掉了。

我们发现题面里并没有给出 m 的下界，也就是说当 m 很小时可能出现 \frac{1}{i!}\bmod m 不存在的情况。

怎么办呢？

我们考虑把数记为 x\times m^k 的形式，其中 m\nmid x。这样有 (x\times m^k)^{-1}=x^{-1}\times m^{-k}，而因为 m 是质数且 m\nmid x ，x^{-1}\bmod m一定存在。容易从这种计数法转成整数。

我们可以提前预处理出 1\sim n 用这种表示法的表示，然后的步骤和线性预处理组合数一样。时间复杂度 {\rm O}(n)。

所以时间复杂度为 {\rm O}(n)。

但是这种做法全身都是瓶颈，所以常数可能偏大，写的时候需要注意常数，不开 O2 可能过不去。如果开了还过不去可以试试取模优化。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
int n,mod,M,a,b,pwa[N],pwb[N],p[N],pcnt,ans;
int pw(int x,int p){
    int res=1;
    for(;p;p>>=1,x=x*x%mod) if(p&1) res=res*x%mod;
    return res;
}
struct Int{
    int x,k;//x*m^k
    Int operator *(const Int&re)const{
        return (Int){x*re.x%mod,k+re.k};
    }
    Int inv(){
        return (Int){pw(x,mod-2),-k};
    }
    int toi(){
        assert(k>=0);//如果k<0，容易证明此时这个数不存在。
        if(k>0) return 0;
        return x;
    }
}F[N],Inv[N];
Int get(int x){
    int k=0;
    while(x%mod==0) x/=mod,k++;
    return (Int){x%mod,k};
}
int C(int x,int y){
    if(x<y||y<0) return 0;
    return (F[x]*Inv[y]*Inv[x-y]).toi();
}
bool s[N];
void sh(){//线性筛
    pwa[0]=a==0,pwb[0]=b==0;
    pwa[1]=1,pwb[1]=1;
    for(int i=2;i<=n;i++){
        if(!s[i]){//质数处的计算
            pwa[i]=pw(i,a);
            pwb[i]=pw(i,b);
            p[++pcnt]=i;
        }
        for(int j=1;j<=pcnt&&i*p[j]<=n;j++){//和数处的计算
            pwa[i*p[j]]=pwa[i]*pwa[p[j]]%mod;
            pwb[i*p[j]]=pwb[i]*pwb[p[j]]%mod;
            s[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
signed main(){
    cin>>n>>a>>b>>mod;
    sh();
    F[0]=get(1);
    M=min(mod-1,n+2);
    for(int i=1;i<=M;i++) F[i]=F[i-1]*get(i);
    Inv[M]=F[M].inv();
    for(int i=M;i>=1;i--) Inv[i-1]=Inv[i]*get(i);
    for(int i=0;i<=n-i+1;i++) ans=(ans+C(n-i+1,i)*pwb[i]%mod*pwa[n-i])%mod;
    cout<<ans;
    return 0;
}