题意：有一个长为n的数字字符串，要求其中插入k个加号，求所有合法表达式的和之和
0<=k<n<=1e5
思路：参考官方题解，讲的很好很清楚
字符串下标从0开始
考虑第i位d[i]的贡献，分两类讨论
1.d[i]不是最后一个串
枚举i到该串最后一个字符的距离l
d[i]之前未知，从d[i]到d[i+l]之间确定没有加号，d[i+l]后面是加号
有n-1个间隔，确定l+1个没有加号，剩余n-l-2个间隔内要放k-1个加号，方案数即C(n-l-2,k-1)
2.d[i]是最后一个串
d[i]之前未知，从d[i]到d[i+l]之间确定没有加号
有n-1个间隔，确定l个没有加号，剩余n-l-1个间隔内要放k个加号，方案数即C(n-l-1,k)=C(i,k)
最后需要交换一下求和顺序
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef long double ld; 7 typedef pair<int,int> PII; 8 typedef pair<ll,ll> Pll; 9 typedef vector<int> VI; 10 typedef vector<PII> VII; 11 typedef pair<ll,ll>P; 12 #define N 200000+10 13 #define M 200000+10 14 #define INF 1e9 15 #define fi first 16 #define se second 17 #define MP make_pair 18 #define pb push_back 19 #define pi acos(-1) 20 #define mem(a,b) memset(a,b,sizeof(a)) 21 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 22 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 23 #define lowbit(x) x&(-x) 24 #define Rand (rand()*(1<<16)+rand()) 25 #define id(x) ((x)<=B?(x):m-n/(x)+1) 26 #define ls p<<1 27 #define rs p<<1|1 28 #define fors(i) for(auto i:e[x]) if(i!=p) 29 30 const int MOD=1000000007,inv2=(MOD+1)/2; 31 //int p=1e4+7; 32 double eps=1e-6; 33 int dx[4]={-1,1,0,0}; 34 int dy[4]={0,0,-1,1}; 35 36 char ch[N]; 37 ll fac[N],inv[N],ten[N],s[N],d[N]; 38 39 int read() 40 { 41 int v=0,f=1; 42 char c=getchar(); 43 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 44 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 45 return v*f; 46 } 47 48 ll readll() 49 { 50 ll v=0,f=1; 51 char c=getchar(); 52 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 53 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 54 return v*f; 55 } 56 57 ll C(int x,int y) 58 { 59 if(y>x) return 0; 60 return fac[x]*inv[y]%MOD*inv[x-y]%MOD; 61 } 62 63 int main() 64 { 65 //freopen("1.in","r",stdin); 66 //freopen("1.out","w",stdout); 67 int n=read(),K=read(); 68 scanf("%s",ch); 69 rep(i,0,n-1) d[i]=ch[i]-'0'; 70 fac[0]=1; 71 rep(i,1,2e5) fac[i]=fac[i-1]*i%MOD; 72 inv[0]=inv[1]=1; 73 rep(i,2,2e5) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD; 74 rep(i,1,2e5) inv[i]=inv[i-1]*inv[i]%MOD; 75 ten[0]=1; 76 rep(i,1,2e5) ten[i]=ten[i-1]*10%MOD; 77 s[0]=d[0]; 78 rep(i,1,n-1) s[i]=s[i-1]+d[i]; 79 ll ans=0; 80 rep(i,0,n-2) ans=(ans+ten[i]*C(n-i-2,K-1)%MOD*s[n-i-2]%MOD)%MOD; 81 rep(i,0,n-1) ans=(ans+d[i]*ten[n-i-1]%MOD*C(i,K)%MOD)%MOD; 82 printf("%I64d\n",ans); 83 return 0; 84 }