[CF 521C] Pluses everywhere

這題是數學，但我一開始就想到很麻煩的作法，然後就爛掉了QQ

作法：

考慮 a_i 被實際當成的數值等於 a_i * 10^j 的時候，會被算到幾次，第一種可能是 i 的後面隔了 j 個之後緊接著一個加號，另一種可能是後面就是數列的尾了。如果是第一種可能，那麼剩下的 k-1 個加號就會被放在從 i 和 i+j 中間的以外的地方，因為 a_i 要乘的是 10^j ，所以他們中間不能有加號，所以這樣的選擇有 C( n - j - 2 , k - 1 ) 種，也就是這個部份的總和為

sigma( i = 1 ~ n ) sigma( j = 0 ~ n - i - 1 ) ( a_i * 10^j ) * C( n - j - 2 , k - 1 )

再注意到其實 j 頂多只到 n - k - 1 ，並且把兩個 sigma 交換後可以得到他等於

sigma( j = 0 ~ n - k - 1 ) sigma( i = 1 ~ n - 1 - j ) ( a_i * 10^j ) * C( n - j - 2 , k - 1 )

把兩個 sigma 交換的動作就像是如果現在要算一個方格表裡的元素總和，那麼可以先橫著加，再直著把那些加好的數加起來，或是先直著加再橫著加。另外至於為什麼內層的 i 是從 1 跑到 n - 1 - j ，可以把所有要求和的 ( i , j ) 都畫在坐標平面上，觀察他的規律就可以得到當 j 固定的時候 i 是從 1 跑到 n - 1 - j 了。

而內層的 sigma 可以直接加起來，這樣就變成等於

sigma( j = 0 ~ n - k - 1 ) ( S_i * 10^j ) * C( n - j - 2 , k - 1 )

其中 S_i = a_1 + ... + a_i。所以這個式子的值就能O( n ) 得到了。
( 註： C 的部分會用到 C( n+1,m ) = C( n , m ) * (n+1) / ( n-m+1 ) 這件事，而在模一個質數下的除法等於乘他的反元素，所以還要另外寫的求反元素的函數 )

另外，對於第二種情形( a_i 當作 a_i * 10^j 的時候後面就是數列的尾了 )，可以得到總和等於

sigma ( i = k+1 ~ n ) a_i * 10^( n - i ) * C( i - 1 , k )

所以也可以直接O(n)作了。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=100000+10 ;
 
LL power(LL x,int n)
{
    if(n==0) return 1LL ;
    if(n==1) return x ;
    LL tmp=power(x,n/2) ;
    if(n%2) return (tmp*tmp%MOD)*x%MOD ;
    else return tmp*tmp%MOD ;
}
 
LL inv(LL x)
{
    return power(x,MOD-2) ;
}
 
LL pw[maxn] ;
int a[maxn] ;
LL sum[maxn] ;
char s[maxn] ;
 
main()
{
    int n,k ; scanf("%d%d%s",&n,&k,s+1) ;
    for(int i=1;i<=n;i++)
        a[i]=s[i]-'0' ,
        sum[i]=sum[i-1]+a[i] ;
    pw[0]=1LL ;
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*10%MOD ;
 
    LL ans=0LL , comb=1LL ;
    for(int i=k-1;i<=n-2;i++)
    {
        ans+=(sum[i+1]*pw[n-i-2]%MOD)*comb ;
        ans%=MOD ;
        comb=(comb*(i+1)%MOD)*inv(i-k+2)%MOD ;
    }
    comb=1LL ;
    for(int i=k+1;i<=n;i++)
    {
        ans+=(a[i]*pw[n-i]%MOD)*comb ;
        ans%=MOD ;
        comb=(comb*i%MOD)*inv(i-k)%MOD ;
    }
    printf("%I64d\n",ans) ;
}