题解 P1641 【[SCOI2010]生成字符串】(待填坑)

pantw

2018-04-06 13:18:50

Personal

先丢着。以后再来填坑。 ${{n+1}\choose{n+m+1}}-2\times {{n+1}\choose{n+m}}$ $={{n}\choose{n+m}}+{{n+1}\choose{n+m}}-2\times {{n+1}\choose{n+m}}$ $={{n}\choose{n+m}}-{{n+1}\choose{n+m}}$ $=\frac{(n+m)!}{n!m!} - \frac{(n+m)!}{(n+1)!(m-1)!}$ $=\frac{(n+m)!}{n!m!} - \frac{m}{n+1}\times\frac{(n+m)!}{n!m!}$ $=\frac{n-m+1}{n+1}\times\frac{(n+m)!}{n!m!}$ ```cpp #include <cstdio> #define mod 20100403 #define Lovelive long long inline Lovelive pow(Lovelive x, int p = mod - 2) { Lovelive ret = 1; for(; p; p >>= 1, x = x * x % mod) if(p & 1) ret = ret * x % mod; return ret; } int main() { Lovelive ans, fac; register int n, m, i; scanf("%d%d", &n, &m); for(i = ans = fac = 1; i <= m; ++i) fac = fac * i % mod; ans = pow(fac); for(; i <= n; ++i) fac = fac * i % mod; ans = ans * pow(fac) % mod; for(; i <= m + n; ++i) fac = fac * i % mod; ans = ans * fac % mod * (n - m + 1) % mod * pow(n + 1) % mod; printf("%d", (int)ans); } ```