[loj3075]组合数求和

Subtask1：$m,nd\le 2\times 10^{3}$

对$M$质因数分解，假设$M=\prod_{i=1}^{k}p_{i}^{\alpha_{i}}$（其中$p_{i}$为素数），对每个$i$求出$f(j)\ mod\ p_{i}^{\alpha_{i}}$的值，再通过exgcd即可求出$f(j)$，注意到$\sum \log p_{i}^{\alpha_{i}}=\log M$，即exgcd的复杂度仅为$o(m\log M)$

在模$p^{\alpha}$的意义下，只需要将数值以$r\cdot p^{k}$的形式描述（其中$p\not\mid r$），即可支持求逆元

预处理$nd$以内阶乘即逆元，复杂度为$o(nd\log M)$，即可$o(1)$求出${n\choose m}mod\ p^{\alpha}$，那么暴力计算即可

时间复杂度为$o(nm\log M)$，可以通过

Subtask2：$d=1$

对于多项式$F(x)$，记$F(x)[x^{n}]$表示该多项式$n$次项系数

根据二项式定理，有${n\choose m}=(1+x)^{n}[x^{m}]$，即$f(j)=(\sum_{i=0}^{n-1}(1+x)^{id})[x^{j}]mod\ M$

记后者为$C(x)$，根据等比数列求和，即$C(x)=\frac{(1+x)^{nd}-1}{(1+x)^{d}-1}mod\ x^{m}$

由于分子和分母同时除以$x$，即分别为$\begin{cases}A(x)=\sum_{i=1}^{nd}{nd\choose i}x^{i-1}\\B(x)=\sum_{i=1}^{d}{d\choose i}x^{i-1}\end{cases}$，那么$C(x)=\frac{A(x)}{B(x)}mod\ x^{m}$

由于$d=1$，即$B(x)=1$，那么$C(x)=A(x)\ mod\ x^{m}$

考虑$A(x)[x^{i}]={nd\choose i+1}$，将$i$从小到大枚举，每次即乘上$\frac{nd-i}{i+1}$，关于如何支持除法与Subtask1相同（对$M$质因数分解并将数值以$r\cdot p^{k}$的形式描述），即可$o(m\log M)$求出$A(x)$

时间复杂度为$o(m\log M)$，可以通过

Subtask3：$m\le 8\times 10^{3}$，$M=998244353$

当$M=998244353$时，$A(x)$可以线性预处理逆元做到$o(m)$，$B(x)$多项式求逆即可

时间复杂度为$o(m \log m)$，可以通过

（由于本做法与正解关系不大，这里就不实现了）

Subtask4：$\gcd(d,M)=1$

仍考虑$C(x)=\frac{A(x)}{B(x)}mod\ x^{m}$，也即$B(x)\cdot C(x)\equiv A(x)(mod\ x^{m})$

考虑$i$次项系数，即$\forall 0\le i<m,\sum_{j=0}^{i}B(x)[x^{j}]\cdot C(x)[x^{i-j}]=A(x)[x^{i}]$

再代入具体的式子，即$\sum_{j=0}^{i}{d\choose j+1}\cdot C(x)[x^{i-j}]=A(x)[x^{i}]$

将$j\ne 0$的部分减到右边并同除以$d$，即$C(x)[x^{i}]=\frac{A(x)[x^{i}]-\sum_{j=1}^{i}{d\choose j+1}\cdot C(x)[x^{i-j}]}{d}$

$A(x)$可以$o(m\log M)$求出，而求和式在$j\ge d$时无意义，可以$o(d)$求出

由于$\gcd(d,M)=1$，也即$p\not\mid d$，可以扩欧求出$d$在模$p^{\alpha}$意义下的逆元来支持除法

时间复杂度为$o(m(d+\log M))$，可以通过

Subtask5：$d$为质数

当$p\not\mid d$时，仍用逆元的方式处理即可，以下考虑$p\mid d$的情况：

由于$d$是素数，那么$p\mid d$当且仅当$p=d$

此时，将原式变形，可得$C(x)[x^{i}]=A(x)[x^{i+d-1}]-\sum_{j=1}^{d-1}{d\choose j}C(x)[x^{i+j}]$

（虽然这个等式仅在$i+d\le m$时成立，但令其在$i$更大时成立不影响正确性）

不断迭代，即按照$i$从小到大维护当前$C(x)[x^{i}]$的系数，并将其乘上$-{d\choose j}$转移到$C(x)[x^{i+j}]$

每转移一次都会让$p$的幂次增加1，那么最多转移$\alpha$次即会在模$p^{\alpha}$意义下为0

由此，我们发现$C(x)[x^{i}]$可以被描述为关于$A(x)[x^{i+d-1}],A(x)[x^{i+d}],...,A(x)[x^{i+d\alpha}]$的一个线性的式子，在一开始迭代$o(d^{2}\alpha)$预处理出来，再利用此递推式$o(md\alpha)$计算即可

时间复杂度为$o(md\log M)$，可以通过

Subtask6：无特殊限制

仍考虑$p\not\mid d$的情况，此时前面的做法并不一定正确，原因是存在$1\le j<d$使得${d\choose j}$使得不是$p$的倍数

对于这个问题，令$t$为最大的$j$使得${d\choose j}$不是$p$的倍数（其中$1\le j<d$），将原式变形，即
$$
C(x)[x^{i+t}]=\frac{A(x)[x^{i+d-1}]-\sum_{j=0}^{t-1}{d\choose j}C(x)[x^{i+j}]-\sum_{j=t+1}^{d-1}{d\choose j}C(x)[x^{i+j}]}{{d\choose t}}
$$
注意到每向后迭代一次（最后一项），都会让$p$的幂次增加1

换言之，我们只需要将其分层迭代，每一层按次数从大到小迭代，并且当迭代到$i$之前后就不需要再迭代（直接取该值即可），那么每一层要迭代$o(d\alpha)$个数，每一个数迭代复杂度为$o(d)$，最多$\alpha$层，复杂度即$o(d^{2}\alpha^{2})$

同样预处理出这个线性的式子，再$o(md\alpha)$计算即可

时间复杂度为$O(d^{2}\log^{2}M+md\log M)$，可以通过

（事实上，前面Subtask4和Subtask5即$t=d-1$和$t=0$的情况）

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 3000005

  4 #define D 105

  5 #define L 35

  6 vector<pair<int,int> >v;

  7 int n,m,d,M,p,s,mod,Ans,mi[L],C[D][D],A[N+D*L],tot[D*L],Tot[D*L],f[N],ans[N];

  8 int exgcd(int a,int b,int &x,int &y){

  9     if (!b){

 10         x=1,y=0;

 11         return a;

 12     }

 13     int g=exgcd(b,a%b,y,x);

 14     y-=a/b*x;

 15     return g;

 16 }

 17 int get_inv(int k){

 18     int x,y;

 19     exgcd(k,mod,x,y);

 20     return (x%mod+mod)%mod;

 21 }

 22 struct num{

 23     int r,k;

 24     num(){

 25         r=1,k=0;

 26     }

 27     num(int rr){

 28         r=rr,k=0;

 29         if (!r)return;

 30         while (r%p==0){

 31             r/=p;

 32             k++;

 33         }

 34     }

 35     num(int rr,int kk){

 36         r=rr,k=kk;

 37     }

 38     num operator * (const num &a)const{

 39         return num(1LL*r*a.r%mod,k+a.k);

 40     }

 41     num inv(){

 42         return num(get_inv(r),-k);

 43     }

 44     int get(){

 45         if (k>=s)return 0;

 46         return 1LL*r*mi[k]%mod;

 47     }

 48 };

 49 void calc(){

 50     mi[0]=1;

 51     for(int i=1;i<s;i++)mi[i]=mi[i-1]*p;

 52     for(int i=0;i<=d;i++){

 53         C[i][0]=C[i][i]=1;

 54         for(int j=1;j<d;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;

 55     }

 56     num ans=num(1);

 57     for(int i=0;i<=m+s*d;i++){

 58         if (n*d<i)ans=num(0);

 59         else ans=ans*num(n*d-i)*num(i+1).inv();

 60         A[i]=ans.get();

 61     }

 62     int t=0;

 63     for(int i=1;i<d;i++)

 64         if (C[d][i]%p)t=i;

 65     int inv=get_inv(C[d][t]);

 66     memset(tot,0,sizeof(tot));

 67     memset(Tot,0,sizeof(Tot));

 68     tot[d]=1;

 69     for(int i=0;i<s;i++)

 70         for(int j=d*s;j>=d;j--){

 71             Tot[j]=(Tot[j]+1LL*inv*tot[j])%mod;

 72             for(int k=0;k<d;k++)

 73                 if (k!=t)tot[j+k-t]=(tot[j+k-t]-1LL*C[d][k]*inv%mod*tot[j]%mod+mod)%mod;

 74             tot[j]=0;

 75         }

 76     for(int i=0;i<m;i++){

 77         f[i]=0;

 78         for(int j=1;j<=min(i,d-1);j++)f[i]=(f[i]+1LL*tot[d-j]*f[i-j]%mod)%mod;

 79         for(int j=d;j<=d*s;j++)f[i]=(f[i]+1LL*Tot[j]*A[i+j-t-1])%mod;

 80     }

 81 }

 82 int main(){

 83     scanf("%d%d%d%d",&n,&m,&d,&M);

 84     int k=M;

 85     for(int i=2;i*i<=k;i++){

 86         int s=0;

 87         while (k%i==0){

 88             k/=i;

 89             s++;

 90         }

 91         if (s)v.push_back(make_pair(i,s));

 92     }

 93     if (k>1)v.push_back(make_pair(k,1));

 94     k=1;

 95     for(int i=0;i<v.size();i++){

 96         p=v[i].first,s=v[i].second,mod=1;

 97         for(int j=0;j<s;j++)mod*=p;

 98         calc();

 99         int x=get_inv(k),kk=k*mod;

100         for(int j=0;j<m;j++)ans[j]=(1LL*x*(f[j]-ans[j]+kk)%kk*k+ans[j])%kk;

101         k=kk;

102     }

103     for(int i=0;i<m;i++)Ans^=ans[i];

104     printf("%d",Ans);

105 }

巴特西

[loj3075]组合数求和

Subtask1：$m,nd\le 2\times 10^{3}$

Subtask2：$d=1$

Subtask3：$m\le 8\times 10^{3}$，$M=998244353$

Subtask4：$\gcd(d,M)=1$

Subtask5：$d$为质数

Subtask6：无特殊限制

最新文章

热门文章

巴特西

[loj3075]组合数求和

Subtask1：​​​$m,nd\le 2\times 10^{3}$

Subtask2：$d=1$

Subtask3：$m\le 8\times 10^{3}$，$M=998244353$

Subtask4：$\gcd(d,M)=1$

Subtask5：$d$为质数

Subtask6：无特殊限制

最新文章

热门文章

Subtask1：$m,nd\le 2\times 10^{3}$