Codeforces

Luogu

分析

考虑每个数 $a_i$ 的贡献。枚举长度可以得到
$$
\sum_{j=0}^{n-i-1}a_i\times 10^j\times{n-j-2\choose k-1}+a_i\times 10^{n-i}\times{i-1\choose k}
$$
后面那一项是因为最后不需要填 +。

那么答案为
$$
\sum_{i=1}^n\left(\sum_{j=0}^{n-i-1}a_i\times 10^j\times{n-j-2\choose k-1}+a_i\times 10^{n-i}\times{i-1\choose k}\right)
$$
交换一下求和号得到
$$
\sum_{j=0}^{n-2}10^j\times{n-j-2\choose k-1}\sum_{i=1}^{n-j-1}a_i+\sum_{i=k+1}^na_i\times 10^{n-i}\times{i-1\choose k}
$$
预处理 $a_i$ 的前缀和即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,k; char a[N];
int s[N],fac[N],ifac[N];

int C(int n,int m) {
    if (n<m) return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int main() {
    n=read(),k=read(); scanf("%s",a+1);
    for (int i=1;i<=n;++i) s[i]=s[i-1]+a[i]-'0';
    fac[0]=1;
    for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
    int ans=0;
    for (int i=0;i<=n-2;++i)
        ans=(ans+1ll*qpow(10,i)*C(n-i-2,k-1)%mod*s[n-i-1])%mod;
    for (int i=k+1;i<=n;++i)
        ans=(ans+1ll*qpow(10,n-i)*C(i-1,k)%mod*(a[i]-'0'))%mod;
    printf("%d\n",ans);
    return 0;
}