Codeforces #295 Div1 C. Pluses everywhere

これは割とすんなり解けた。
http://codeforces.com/contest/521/problem/C

問題

N桁の数がある。
これらの数の間にK箇所＋記号を挿入することを考える。
ただし＋同士の間は１個以上数値が無ければならない。また、leading zeroは許可される。

全ての＋記号挿入パターンにおいて、それらの数値の総和を答えよ。

解法

後ろからi桁目の数値dが最終的に答えに与える影響を考える。
全＋記号挿入パターンにおいてこの数がi桁目としてカウントされるのは、この桁目以降に＋が入らない場合なので通りなので、答えに分影響する。
また、この数はi桁目より小さいj桁目としてカウントされるのは、この数字から初めてj個後の数値のあとに＋記号が入る場合であり、そのようなケースは通りなので、答えに分影響する。

各(i,j)について計算するとO(N^2)かかってしまうが、うまく累積和を取って計算してやるとO(N)で計算してやることができる。

ll mo=1000000007;
int N,K;
string S;
ll num[101000];
ll p10[101000];

ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>K>>S;
	
	p10[0]=1;
	FOR(i,N) p10[i+1]=p10[i]*10%mo;
	FOR(i,N) num[N-1-i]+=S[i]-'0';
	
	ll ret=0;
	for(i=N-1;i>=0;i--) {
		ret += num[i+1]*p10[i]%mo*combi(N-2-i,K-1) % mo;
		ret += num[i]*p10[i]%mo*combi(N-1-i,K) % mo;
		num[i]+=num[i+1];
	}
	
	cout<<ret%mo<<endl;
}

まとめ

すんなり解けて良かった。