P1641 [SCOI2010]生成字符串

发表于
本文字数： 5.9k | 阅读时长 ≈ 5 分钟

题意是n个1，m个0，问有多少种组合使在前k个数中1不少于0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long long ll;
#define infi 0x3f3f3f3f
#define fi first
#define se second
#define mp make_pair
const int N=2e6+1,mod=20100403;
int n,m,fact[N],inv[N];//inv表示N!的逆元 ，fact表示N!modp 
int qpow(int a, int b) {//快速幂 
    int res=1;
    while(b){
        if(b&1)res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
int C(int x, int y) {
    int z=1ll*fact[x]*inv[y]%mod;
    return 1ll*z*inv[x-y]%mod;
}
// ans= c(n)(n+m)-c(n-1)(n+m) zcy
int main(){
	int ans,n,m,t=1,e=0;
	ios::sync_with_stdio(0);
	cin>>n>>m;
	fact[0]=1;
	for(int i=1;i<=n+m;i++)
		fact[i]=(1ll*fact[i-1]*i)%mod;
    inv[n+m]=qpow(fact[n+m],mod-2);
    for (int i=n+m-1;i>=0;i--)
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
	cout<<(C(n+m,m)-C(n+m,m-1)+mod)%mod;
	return 0;
}