Problem 给一个有个加号，可变为1+234，12+34，123+4。问所有插入情况得到的数之和（mod 1e9+7），比如1+234=235，12+34=46，123+4=127–>answer=235+46+127Limits Look up Original Problem From hereSolution 用前缀和方法可以求出某个子串所表示的数。把个类，每个类含有若干个长度相同的A的子串，枚举每个类对答案的贡献度，，算出即可。实际可枚举子串的长度来求答案。我用到了前缀和的前缀和 以及 组合数来统计，求组合数用拓展gcd求的方法。Complexity My Code;ll;ld;ll mod =1e9+7;//这个必须是质数class Combination_Number{public://快速求组合数C(n,m)ll factor[N];void init(){//程序需要先执行这个函数factor[0]=1;rep(i,1,N){factor[i]=(factor[i-1]*i)%mod;}}ll extend_gcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll ans=extend_gcd(b,a%b,x,y);ll tmp=x;x=y;y=tmp-(a/b)*y;return ans;}ll inverse(ll b){ll x,y;extend_gcd(b,mod,x,y);return (x%mod+mod)%mod;}ll cal(ll n,ll m){//快速求组合数C(n,m)ll t1=1,t2=1;if(m==0) return 1LL;if(m<n/2)m=n-m;t1=factor[n];t2=factor[n-m]*factor[m]%mod;return t1*inverse(t2)%mod;}}C;int n,k;char s[N];ll a[N],b[N],ans=0,tenpower[N],ten;ll presum[N],sum_presum[N];ll cal_presum(ll from,ll to,int l){ll res=presum[to];res-=presum[from-1]*tenpower[l]%mod;res=(res%mod+mod)%mod;return res;}int main(){C.init();tenpower[0]=1;rep(i,1,N){tenpower[i]=(tenpower[i-1]*10LL)%mod;}scanf(“%d %d”,&n,&k);scanf(“%s”,s);rep(i,0,n){a[i+1]=s[i]-‘0’;}repin(i,1,n){presum[i]=(presum[i-1]*10LL+a[i])%mod;}repin(i,1,n){sum_presum[i]=(sum_presum[i-1]+presum[i])%mod;}if(k==0){ans=0;repin(i,1,n){ans=(ans*10LL+a[i])%mod;}printf(“%lld\n”,ans);exit(0);}ans=0;repin(l,1,n){int r=n-1-l;if(r>=k-1){ll res1=cal_presum(1,l,l);res1=res1*C.cal(r,k-1)%mod;ans=(ans+res1)%mod;ll res2=cal_presum(n-l+1,n,l);res2=res2*C.cal(r,k-1)%mod;ans=(ans+res2)%mod;}r=n-1-(l+1);if(k>=1 && r>=k-2){int p=2+l-1;if(p<=n-1){ll res=sum_presum[n-1]-sum_presum[p-1];res=(res%mod+mod)%mod;res-=sum_presum[n-1-l]*tenpower[l]%mod;res=(res%mod+mod)%mod;res=res*C.cal(r,k-2)%mod;ans=(ans+res)%mod;}}}printf(“%lld\n”,ans);}
影子依旧可以相亲相爱。哪一块骨骼最温暖，总能一击即中。
