AtCoder AGC036C GP 2 (组合计数)
题目链接https://atcoder.jp/contests/agc036/tasks/agc036_c 题解终于有时间补agc036的题了。 首先转化一下题目: 一个序列可以被按题目的操作方式生成当且仅当它长度为(N),总和为(3M),且最大数不超过(2M),奇数的个数不超过(M). 然后考虑怎么计数: 先不考虑第二个条件,定义(f(n,m,k))表示长度为(n)总和为(m)奇数不超过(k)个的方案数,那么枚举奇数的个数(i),剩下的偶数和为(m-1),有(f(n,k)=sum^{k}_{iequiv m(mod 2)}{nchoose i}{frac{m-i}{2}+n-1choose n-1}). 因此最后答案就是(f(N,3M,M)-N(f(N,M,M)-f(N-1,M))). 时间复杂度(O(N+M)). 代码#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #define llong long long using namespace std; inline int read() { int x=0; bool f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=0; for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0'); if(f) return x; return -x; } const int N = 2e6; const int P = 998244353; llong fact[N+3],finv[N+3]; llong quickpow(llong x,llong y) { llong cur = x,ret = 1ll; for(int i=0; y; i++) { if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;} cur = cur*cur%P; } return ret; } llong comb(llong x,llong y) {return x<0||y<0||x<y ? 0ll : fact[x]*finv[y]%P*finv[x-y]%P;} llong calc(llong n,llong m,llong k) { llong ret = 0ll; for(int i=0; i<=k; i++) { if((m-i)&1) continue; llong tmp = comb(n,i)*comb(((m-i)>>1)+n-1,n-1)%P; ret = (ret+tmp)%P; } // printf("calc %lld %lld %lld=%lldn",n,k,ret); return ret; } int n,m; int main() { fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P; finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P; scanf("%d%d",&n,&m); llong ans = calc(n,3*m,m); ans = (ans-n*(calc(n,m)-calc(n-1,m)+P)%P+P)%P; printf("%lldn",ans); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |