SP19148 Kill them All

· · 题解

截止2020.4.27晚，另外的所有题解都有根本性问题（详情可以去讨论区）。

先来看一个简单版的问题：

[SCOI2010] 生成字符串

lxhgww 最近接到了一个生成字符串的任务，任务需要他把 n 个 1 和 m 个 0 组成字符串，但是任务还要求在组成的字符串中，在任意的前 k 个字符中，1 的个数不能少于 0 的个数。现在 lxhgww 想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

考虑一个转化，从 (0,0) 开始出发，设当前点为 (x,y) 每次如果遇到 1 就走到 (x+1,y-1) ，每次遇到 0 就走到 (x+1,y+1)，那么最终就是走到 (n+m,m-n) 的、不跨过直线 x=0 方案数。这…似乎是一个十分经典的组合问题了。大概就是考虑把走到 y=1 这条直线以下的那些路径全都翻转到 y=1 以下（做镜像对称），那么就可以看做是从 (0,2) 走到 (n+m,m-n) 的方案数。所以答案就是两者相减。

考虑怎么算这两部分。发现本质上从 (0,0) 走到 (n+m,m-n) 、每次向右下或者右上走的方案数。一种比较简单的理解就是从 n+m 步里面选出 n 步向右下走的方案数，所以答案是 \binom{n+m}{m}-\binom{n+m}{m-1} ，因为从 (0,2) 开始走相当于把其中向上走的某一步魔改成了成了向下走的，所以 m 要减一。

再考虑这题：

[SP19148] Kill them All

$1\leq n\leq 10^6$ 。

回顾历史的时候顺便发现了这道题…

大概就是上个题把 \geq 换成了 > 。考虑首先让 1 号怪兽必须被 Digo 干掉，那么就变成了从 (1,0) 出发，走 n-1 步，途中不能碰到 y=0 的方案数。考虑最后走到的地方只会是 (n,\lceil\frac{n}{2}\rceil),(n,\lceil\frac{n}{2}\rceil+1)\cdots (n,n)，那么不妨对这些东西分别计数，那么答案就是

1+\sum_{i=1}^{\lceil\frac{n}{2}\rceil-1}\left(\binom{n-1}{i}-\binom{n-1}{i-1}\right)

其中第一个 1 是全部被 Digo 干掉的方案数。那么可以知道…这个式子里面前面的都被消掉了，最后只剩一个 1+\binom{n-1}{\lceil\frac{n}{2}\rceil-1}-\binom{n-1}{0}=\binom{n-1}{\lceil\frac{n}{2}\rceil-1} 。 然后就预处理阶乘+输出即可。


int t, n ;
int fac[N] ;
int inv[N] ;

int expow(int a, int b){
    int ret = 1 ;
    while (b){
        if (b & 1)
            ret = (ll)ret * a % P ;
        a = (ll)a * a % P ; b >>= 1 ;
    }
    return ret ;
}
int binom(int x, int y){//\binom{x}{y}
    return (ll)fac[x] * inv[y] % P * inv[x - y] % P ;
}
int main(){
    fac[0] = inv[0] = 1 ; cin >> t ;
    for (int i = 1 ; i <= M + 1 ; ++ i)
        fac[i] = (ll)fac[i - 1] * i % P ;
    inv[M + 1] = expow(fac[M + 1], P - 2) ;
    for (int i = M ; i >= 1 ; -- i)
        inv[i] = (ll)inv[i + 1] * (i + 1) % P ;
    while (t --) n = qr(), printf("%d\n", binom(n - 1, ceil(1.0 * n / 2.0) - 1)) ;
}