我想问一下我的思路错哪了呢？

我的思路是：考虑m个1，m个0的方案数为C(2m,m)/(m+1)，再考虑插入n-m个1，然后我得出了一个结论：这相当于只考虑原来0的个数，因为如果考虑1的个数会导致重复。比如110010，要还要插入2个1，相当于可以在画横线位置插入11_0_01_0_，由于一个位置可以插2个1，所以=C(5,2)=C(3+2,2)=C(n-m+m,n-m)=C(n,m)，所以最终答案为C(2m,m)/(m+1)*C(n,m)，但是交上去只有20pts，应该是n=m的分数，代码如下，求指点，谢谢！

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10,M=2e6,mod=20100403;
int n,m,fac[N],inv[N];
int qPow(int x,int y){
	int ans=1;
	while(y){
		if(y&1){
			ans=1ll*ans*x%mod;
		}
		y>>=1,x=1ll*x*x%mod;
	}
	return ans;
}
int C(int x,int y){
	return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){
	scanf("%d%d",&n,&m);
	fac[0]=1;
	for(int i=1;i<=M;++i){
		fac[i]=1ll*fac[i-1]*i%mod;
	}
	inv[M]=qPow(fac[M],mod-2)%mod;
	for(int i=M-1;i>=0;--i){
		inv[i]=1ll*inv[i+1]*(i+1)%mod;
	}
	printf("%lld",1ll*C(2*m,m)*qPow(m+1,mod-2)%mod*C(n,m)%mod);
}

我想问一下我的思路错哪了呢？

讨论操作

回复

相关推荐

我想问一下我的思路错哪了呢？