2020-2021:teams:namespace:牛客多校第五场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:牛客多校第五场 [2020/07/28 21:56] great_designer [做法] |
2020-2021:teams:namespace:牛客多校第五场 [2020/07/28 22:34] (当前版本) great_designer [代码] |
||
|---|---|---|---|
| 行 446: | 行 446: | ||
| 考虑生成函数。我们知道等比数列求和： | 考虑生成函数。我们知道等比数列求和： | ||
| - | $$\frac{1}{1-x}=\sum_{i=0} x^i$$ | + | $$\frac{1}{1-x}=\sum_{i=0}^{\infty} x^i$$ |
| 考虑x和y的无限大系数矩阵（类比第一象限附带正坐标轴整点）。那么全1矩阵就是： | 考虑x和y的无限大系数矩阵（类比第一象限附带正坐标轴整点）。那么全1矩阵就是： | ||
| 行 470: | 行 470: | ||
| 因此，所求的答案就是多项式： | 因此，所求的答案就是多项式： | ||
| - | $$frac{x^Ky^K}{{(1-x)}^K{(1-y)}^K}\frac{1}{{(1-xy)}^K}$$ | + | $$\frac{x^Ky^K}{{(1-x)}^K{(1-y)}^K}\frac{1}{{(1-xy)}^K}$$ |
| + | |||
| + | 之中x^Ny^M前的系数。即多项式： | ||
| + | |||
| + | $$\frac{1}{{(1-x)}^K}\frac{1}{{(1-y)}^K}\frac{1}{{(1-xy)}^K}$$ | ||
| + | |||
| + | 之中x^{N-K}y^{M-K}前的系数。 | ||
| + | |||
| + | 我们希望，将“对角线”(1/(1-xy))^K的各项系数全部列出来，再乘上两个方向1/(1-x)^K和1/(1-y)^K，补到N-K和M-K。那么这就需要K次方与组合数的知识： | ||
| + | |||
| + | $$\frac{1}{(1-x)^K}=\sum_{i=0}^{\infty} C_{K-1+i}^{K-1}x^i$$ | ||
| + | |||
| + | $$\frac{1}{{(1-x)}^K}\frac{1}{{(1-y)}^K}\frac{1}{{(1-xy)}^K}=\left(\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} C_{K-1+i}^{K-1}C_{K-1+j}^{K-1}x^iy^j\right)\left(\sum_{s=0}^{\infty} C_{K-1+s}^{K-1}{(xy)}^s\right)$$ | ||
| + | |||
| + | 由于在xy项中指数相等，在x^{N-K}y^{M-K}里面的贡献，差值必然由前面来提供。因此多项式中x^{N-K}y^{M-K}项前的系数为： | ||
| + | |||
| + | $$\sum_{t=0}^{\min(N,M)-K} C_{K-1+t}^{K-1}C_{N-1-t}^{K-1}C_{M-1-t}^{K-1}$$ | ||
| + | |||
| + | 为所求答案。 | ||
| - | 之中x^Ny^M前的系数。 | ||
| - | 枚举(1/(1-xy))^K的次数。 | ||
| - | 用1/(1-x)^K和1/(1-y)^K补到N-K和M-K。 | ||
| ====代码==== | ====代码==== | ||
| 行 482: | 行 498: | ||
| <hidden> | <hidden> | ||
| <code C> | <code C> | ||
| - | |||
| #include<stdio.h> | #include<stdio.h> | ||
| 行 491: | 行 506: | ||
| int C(int n,int m) | int C(int n,int m) | ||
| { | { | ||
| - | return 1ll*fac[n]*ffac[m]%mod*ffac[n-m]%mod; | + | return ((1ll*fac[n]*ffac[m])%mod*ffac[n-m])%mod; |
| } | } | ||
| int qpow(int n,int k) | int qpow(int n,int k) | ||
| { | { | ||
| - | int ret = 1; | + | int ret=1; |
| while(k) | while(k) | ||
| { | { | ||
| if(k&1) | if(k&1) | ||
| { | { | ||
| - | ret = 1ll * ret * n % mod; | + | ret=(1ll*ret*n)%mod; |
| } | } | ||
| - | n = 1ll * n * n % mod; | + | n=(1ll*n*n)%mod; |
| - | k /= 2; | + | k/=2; |
| } | } | ||
| return ret; | return ret; | ||
| } | } | ||
| - | int main() | + | void init() |
| { | { | ||
| - | fac[0] = 1; | + | fac[0]=1; |
| - | int i; | + | int i; |
| - | for(i = 1; i <= 2e6; i++) | + | for(i=1;i<=2e6;i++) |
| { | { | ||
| - | fac[i] = 1ll * fac[i-1] * i % mod; | + | fac[i]=(1ll*fac[i-1]*i)%mod; |
| } | } | ||
| - | ffac[2000000] = qpow(fac[2000000], mod - 2); | + | ffac[2000000]=qpow(fac[2000000],mod-2); |
| - | for(i = 2e6; i >= 1; i--) | + | for(i=2e6;i>=1;i--) |
| { | { | ||
| - | ffac[i - 1] = 1ll * ffac[i] * i % mod; | + | ffac[i-1]=(1ll*ffac[i]*i)%mod; |
| } | } | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | init(); | ||
| int T; | int T; | ||
| - | scanf("%d", &T); | + | scanf("%d",&T); |
| while(T--) | while(T--) | ||
| { | { | ||
| - | int N, M, K; | + | int N,M,K; |
| - | scanf("%d%d%d", &N, &M, &K); | + | scanf("%d%d%d",&N,&M,&K); |
| - | int ans = 0; | + | int ans=0; |
| - | for(i = 0; i <=(N<M?N:M) - K; i++) | + | int i; |
| + | for(i=0;i<=(N<M?N:M)-K;i++) | ||
| { | { | ||
| - | ans += 1ll * C(i + K - 1, K - 1) * C(N - i - 1, K - 1) % mod * C(M - i - 1, K - 1) % mod; | + | ans+=((1ll*C(i+K-1,K-1)*C(N-i-1,K-1))%mod*C(M-i-1,K-1))%mod; |
| - | if(ans >= mod) | + | ans-=(ans>=mod)?mod:0; |
| - | { | + | |
| - | ans -= mod; | + | |
| - | } | + | |
| } | } | ||
| printf("%d\n",ans); | printf("%d\n",ans); | ||
2020-2021/teams/namespace/牛客多校第五场.1595944568.txt.gz · 最后更改: 2020/07/28 21:56 由 great_designer
