昨天ZZD大神邀請我做一道題，說這題很有趣啊。
哇，然后我被虐了。
Orz ZZD
?
題目大意：
code1083， 你有一個長度為n的'0-9'串，你要在其中加入k個'+'號，每種方案就會形成一個算式，算式算出來的值記做這次方案的貢獻。
問：所有方案的貢獻，對1e9+7取模。
n,k<=1e5.
?
首先我和zzd先探討了一會兒暴力一點的做法，唔，非常好弄的是k*n^2，枚舉子串，考慮這個子串出現在了多少個方案中，然后就是枚舉左邊多少個'+'，然后一堆組合數...啪啦啪啦...
然后覺得既然兩邊分的'+'號加起來的總和相等，是不是可以不用枚舉呢，比如一個預處理什么的...啪啦啪啦...
number是什么意思？好啦，感覺上面的研究不下去了...
然后又想，不是要O(n)么，感覺像是對每個字符考慮，考慮它作為個位、十位、百位...等等的貢獻。
怎么算呢？似乎現在狀態比剛才好一點了？...
首先是i作為這一段的開頭，j作為這一段的結尾。
現在是i作為這一段的第j位...好啦...然后我還是想不到= =
ZZD就開始秒題啦...因為原題相當于在n-1的空隙中放k個隔板。
CodeWeavers？那么若i不在最后一段，那么我先強制在i+j后插一個隔板[保證i是第j位]，并且強制i到i+j之間的j-1個位置不能放，同時i+j后的位置已經放了，所以還剩n-j-1個位置，k-1個隔板，即C(n-j-1,k-1)種方案。
若i在最后一段，那么我強制i到n的j-1個位置不能放，就是C(n-j,k)種方案。
好啊，發現這個東西居然和i都沒有關系，那我是不是可以把i綁起來算呢？[當然i可以用來判斷這個位置是不是在最后一段，也可以判斷這里到底能不能作為第j位]。
于是我們可以枚舉長度l。
所以在可行的位置[1...n-l+1]中，最后一位是作為最后一段，其它的值是相同的，所以就是一個前綴和*這一坨+最后一個位置的特判，就可以了。
?
codeforces教程，[怎么線性求組合數？] <-大家都會吧？...
不過看在我不會的份上，還是說一下吧...就是利用的是逆元的思想，C(n,r)=n!/(n-r)!/r!，那么要是預處理出所有的階乘以及所有階乘的逆元，每次查詢就是O(1)的了...
預處理階乘O(n)沒問題，預處理出階乘的逆元怎么辦呢？...
機智的ZZD發現：1/(n-1)!=1/n!*n
%%%，先算n!的逆元，然后倒過來再乘一遍就可以了。
?
codeforces怎么提交，[上面的描述可能和代碼中的含義有小小的不同，代碼中l表示的是長度len-1，所以和上面有小小不同]
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int maxn=100010;
const int mod=1e9+7;
typedef long long ll;int n,k;
ll s[maxn],lv[maxn],lv1[maxn];
char num[maxn];
ll ans;ll C(int n,int r){if(r>n) return 0;if(r==0 || n==r) return 1;return ((lv[n]*lv1[r])%mod*lv1[n-r])%mod;
}ll power(ll a,int k){ll ans=1;while(k){if(k&1) ans=ans*a%mod;k>>=1;a=a*a%mod;}return ans;
}int main(){
#ifndef ONLINE_JUDGEfreopen("C.in","r",stdin);freopen("C.out","w",stdout);
#endifscanf("%d%d",&n,&k);scanf("%s",num+1);for(int i=1;i<=n;i++)s[i]=(s[i-1]+num[i]-'0')%mod;lv[0]=1;for(int i=1;i<=n;i++)lv[i]=lv[i-1]*i%mod;lv1[n]=power(lv[n],mod-2);for(int i=n-1;i>=1;i--)lv1[i]=lv1[i+1]*(i+1)%mod;for(int l=0;l<n;l++){ans=(ans+(s[n-l-1]*C(n-l-2,k-1))%mod*power(10,l))%mod;ans=(ans+((num[n-l]-'0')*C(n-l-1,k))%mod*power(10,l))%mod;}printf("%I64d",ans);return 0;
} 
