Luogu 1641 [SCOI2010]生成字符串

结果和dp没有一点关系……

30分算法：设$f_{i, j}$表示已经选了$i$个并且有$j$个是白色的状态数，转移显然，最后答案就是$f_{n + m, m}$，时间复杂度$O(n^{2})$。

100分算法：

把已经选了的$0$的个数和$1$的个数和看作$x$轴，已经选了个$1$的个数和$0$的个数的差看作$y$轴，就相当于每一步可以向右上或者是右下走一步，最后要到达$(n + m, n - m)$的方案数。

可以发现就相当于在$n + m$步中选出$m$步向右下走的方案数$\binom{n + m}{m}$。

考虑一下限制条件，其实就相当于不经过$y = -1$这条线。根据对称性，从$(0, 0)$开始经过$y = -1$到达$(n + m, n - m)$的方案数就相当于从$(0, -2)$出发，相当于在$n + m$步中选择$m - 1$步中向下走，所以不合法的方案数有$\binom{n + m}{m - 1}$个。

最后的答案就是两个组合数相减。

其中阶乘和阶乘的逆元可以$O(n)$预处理。

时间复杂度$O(n)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 2e6 + ;

const ll P = 20100403LL;

int n, m;

ll fac[N], inv[N];

inline ll pow(ll a, ll b) {

    ll res = 1LL;

    for(; b > ; b >>= ) {

        if(b & ) res = res * a % P;

        a = a * a % P;

    }

    return res;

}

inline ll getC(int a, int b) {

    return fac[a] * inv[b] % P * inv[a - b] % P;

}

int main() {

    scanf("%d%d", &n, &m);

    fac[] = 1LL;

    for(int i = ; i <= n + m; i++) fac[i] = 1LL * i * fac[i - ] % P;

    inv[n + m] = pow(fac[n + m], P - );

    for(int i = n + m - ; i >= ; i--) inv[i] = 1LL * inv[i + ] * (i + ) % P; 

    printf("%lld\n", (getC(n + m, m) - getC(n + m, m - ) + P) % P);

    return ;

}

巴特西

Luogu 1641 [SCOI2010]生成字符串

最新文章

热门文章