首页 > 代码库 > [SCOI2010]生成字符串
[SCOI2010]生成字符串
OJ题号：
BZOJ1856、洛谷1641
思路：
总方案数为$\binom{n+m}{m}$，非法方案数为$\binom{n+m}{m-1}$。
则合法方案数为$(n-m+1)\frac{(n+2)(n+3)...(n+m)}{m!}$。
其中除以$m!$可以用乘以逆元实现，边乘边模。
因为要求出1~m的连续的逆元，所以可以线性推。
另外注意中间结果和最终乘积可能会超过int范围，所以要转long long，不然只有10分。
1 #include<cstdio> 2 #include<cctype> 3 inline int getint() { 4 char ch; 5 while(!isdigit(ch=getchar())); 6 int x=ch^‘0‘; 7 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘); 8 return x; 9 }10 const int mod=20100403;11 int main() {12 int n=getint(),m=getint();13 long long sum=n-m+1;14 for(int i=2;i<=m;i++) {15 sum=sum*(n+i)%mod;16 }17 int inv[m+1];18 inv[1]=1;19 for(int i=2;i<=m;i++) {20 inv[i]=(long long)(mod-mod/i)*inv[mod%i]%mod;21 sum=sum*inv[i]%mod;22 }23 printf("%lld\n",sum);24 return 0;25 }
[SCOI2010]生成字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。