Codeforces Round #295 (Div. 1) C. Pluses everywhere (组合数学+乘法逆元)

这题可以这样想:

      对当前第i位来讲,该位若在个位上出现,那末第i位和第i+1位中间肯定有1个“+”,剩下的k⑴个“+”散布在剩下的n⑵个空隙中,所以出现的总次数是C(n⑵,k)。同理,在10位上出现的总次数是C(n⑶,k)。因而每一个数字的贡献值就能够求出来了,累加便可。

      所以大体思路是遍历所有可能出现的位数,从个位开始,分成两部份计算,1部份用前缀和计算出前面所有的在该位上的贡献和,另外一部份算出当前位置在该位上的贡献值。

     然后对求组合数,可以先将阶乘预处理出来,然后用乘法逆元求出组合数的值。

代码以下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL long long
#define pi acos(⑴.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e⑼;
char st[110000];
int n, k, a[110000], sum[110000];
LL fac[110000], inv_fac[110000];
LL qsm(LL n, LL k)
{
LL ans=1;
while(k>0){
if(k&1)
ans=ans*n%mod;
k>>=1;
n=n*n%mod;
}
return ans;
}
void init()
{
int i;
fac[0]=1;
for(i=1;i<=n;i++){
fac[i]=fac[i⑴]*i;
if(fac[i]>=mod) fac[i]%=mod;
}
inv_fac[n]=qsm(fac[n],mod⑵);
for(i=n⑴;i>=0;i–){
inv_fac[i]=inv_fac[i+1]*(i+1);
if(inv_fac[i]>=mod) inv_fac[i]%=mod;
}
}
LL comb(LL n, LL k)
{
return fac[n]*inv_fac[k]%mod*inv_fac[n-k]%mod;
}
int main()
{
int i;
LL ans=0, base=1, s;
scanf("%d%d",&n,&k);
scanf("%s",st+1);
init();
sum[0]=0;
for(i=1;i<=n;i++){
a[i]=st[i]-'0';
sum[i]=a[i]+sum[i⑴];
}
for(i=1;i<=n-k;i++){
s=(LL)sum[n-i]*base%mod;
ans+=s*comb(n-i⑴,k⑴)%mod;

s=(LL)a[n-i+1]*base%mod;
ans+=s*comb(n-i,k)%mod;

base=base*10;
if(ans>=mod) ans%=mod;
if(base>=mod) base%=mod;
}
printf("%I64d
",ans);
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » Codeforces Round #295 (Div. 1) C. Pluses everywhere (组合数学+乘法逆元)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡