2015年3月3日 星期二

[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) ;
}
 

沒有留言:

張貼留言