学考时候推的。场上记错模数,以为是 \(998244353\) 然后想了半天组合数怎么算)
简单题。
首先序列问题考虑每个位置的生成函数然后乘起来。位置 \(k\) 的生成函数显然是
\[\sum_{i=1}\min(i,k)x^i \]那么观察一下尝试搞封闭形式。它前 \(k\) 项和 \(\dfrac x{(1-x)^2}\) 是一样的,后边全是 \(k\)。我的推法是大减小,即:
\[\begin{aligned} &\sum_{i=1}\min(i,k)x^i\\ =&\sum_{i=1}ix^i-\sum_{i=0}ix^{i+k}\\ =&\frac x{(1-x)^2}-x^k\frac x{(1-x)^2}\\ =&x\frac {1-x^k}{(1-x)^2} \end{aligned} \]那么答案就是
\[\begin{aligned} &[x^m]\prod_{i=1}^nx\frac{1-x^i}{(1-x)^2}\\ =&[x^{m-n}]\prod_{i=1}^n\frac{1-x^i}{(1-x)^2}\\ =&[x^{m-n}]\frac 1{(1-x)^{2n}}\prod_{i=1}^n(1-x^i) \end{aligned} \]前边这个东西的第 \(k\) 项显然是 \(\dbinom{2n-1+k}k\)。关于后边这个东西,一看长的就很像五边形数。由于 \(m-n\le n\),那么 \([x^{m-n}]\prod_{i=1}^n(1-x^i)=[x^{m-n}]\prod_{i=1}(1-x^i)=[x^{m-n}]1+\sum_{i=1}(-1)^ix^{\frac{i(3i\pm 1)}2}\)。只有 \(O(\sqrt n)\) 个取值,lucas 爆算即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int mod=200003;
int n,m,ans,jc[200010],inv[200010];
int binom(int n,int m){
if(m<0||n<m)return 0;
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int C(int n,int m){
if(!m)return 1;
return 1ll*binom(n%mod,m%mod)*C(n/mod,m/mod)%mod;
}
signed main(){
scanf("%lld%lld",&n,&m);jc[0]=inv[0]=inv[1]=1;
for(int i=1;i<mod;i++)jc[i]=1ll*jc[i-1]*i%mod;
for(int i=2;i<mod;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<mod;i++)inv[i]=1ll*inv[i-1]*inv[i]%mod;
for(int i=0;;i++){
int ret=i*(3*i-1)>>1;
if(ret>m-n)break;
ans=(ans+1ll*((i&1)?mod-1:1)*C(m+n-ret-1,m-n-ret))%mod;
ret=i*(3*i+1)>>1;
if(!i)continue;
if(ret>m-n)break;
ans=(ans+1ll*((i&1)?mod-1:1)*C(m+n-ret-1,m-n-ret))%mod;
}
printf("%d\n",ans);
return 0;
}
标签:ABC279H,frac,int,题解,sum,ret,ans,mod
From: https://www.cnblogs.com/gtm1514/p/17189621.html