题解 CF520E 【Pluses everywhere】

题目链接

ps:可能组合数一不小心打错了，请发现的大佬提出，谢谢。

我们来讨论每一位数$a_{i}$被算了多少次。

总共有$n-1$个空位可以放$'+'$所以，$a_{i}$左边有$i-1$个空位，右边$n-1-(i-1)$个。

举个例子来说~~（手动模拟一下）~~，如果数$a_{i}$右边有一个加号，则剩下$n-2$个空位放$k-1$个加号的方案里，每种方案$a_{i}$都当做各位记录到答案里，所以对答案影响：$C^{k-1}_{n-2}*$ $a_{i}$。

假设右边第一个不放，第二个放加号，则还有$n-3$个空位，$k-2$个加号。（因为$a_{i}$右边的以为不能放加号）对答案影响： $C_{n-3}^{k-2}*10*$ $a_{i}$。

$emm……$规律好像找出来了。

这样一直递推下去~~（找规律）~~的话。到$a_{n-1}$ 和 $a_{n}$ 位填的话。对答案的影响： $C^{1}_{n-k-2}*10^{k-1}*a_{i}$

但是，我们发现，最后一位数的后面好像并不能放加号。也就是说，最后一位需要特判。。。

所以，当右边全空着的时候对答案的贡献 $10^{i}*C_{n-i-1}^{i}*a_{i}$

全部统计起来，输出就好。

代码奉上。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const long long p=1e9+7;
int n,k;
long long ans[100010];
char a[100010];

long long pen[100010];//阶乘
long long rpen[100010];//阶乘逆元
long long num[100010];//系数

long long pow2(long long a,long long b)
{
    long long res=1;
    for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p;
    return res%p;
}

void rebiut()
{
    num[0]=pen[0]=rpen[0]=1;
    for(int i=1;i<=n;i++)
        pen[i]=pen[i-1]*i%p,
        rpen[i]=pow2(pen[i],p-2),
        num[i]=10*num[i-1]%p;
    return ;
}

long long C(long long n,long long k)//计算组合数，n下面，k上面
{
    if(k<0||k>n||n<0) return 0;
    else return ((pen[n]*rpen[k])%p)*rpen[n-k]%p;
}

long long now;

int main()
{
    scanf("%d%d",&n,&k);
    scanf("%s",a);
    rebiut();

    for(int i=0;i<n;i++) now=(now+num[i]*(a[n-i-1]-'0'))%p;
    if(k==0) {printf("%lld ",now);return 0;}
    
    int d=n-k-1;
    ans[0]=C(n-2,k-1);

    for(int i=0;i<=d;i++) ans[i]=(ans[i-1]+num[i]*C(n-i-2,k-1))%p;
    for(int i=d+1;i<n;i++) ans[i]=ans[i-1];
    for(int i=0;i<=d;i++) ans[i]=(ans[i]+num[i]*C(n-i-2,k))%p;
    now=0;
    for(int i=0;i<n;i++) now=(now+ans[n-i-1]*(a[i]-'0'))%p;
    printf("%lld ",now);
    return 0;
}