Codeforces #349 Div1. C. Codeword

せっかく解法思いついたのにMLE…。
http://codeforces.com/contest/666/problem/C

問題

以下のクエリを順次答えよ。

• 文字列Sを与えられた文字列に置き換える。
• 文字列Sを部分文字列として含むようなアルファベット小文字で構成されたN文字の文字列の数を答える。

なお、前者のクエリで与えられる文字列は合計10^5文字を超えない。

解法

まず後者を考える。
文字列S="XYZ"を含むような文字列は、例えば"xxxXyyyYzzzZ***"のような形を取る。
xxx,yyy,zzzはそれぞれX,Y,Z以外の0文字以上の文字列で、***は任意の文字を取る0文字以上の文字列である。

xxx,yyy,zzzの部分が合計i文字、"***"の部分をN-|S|-i文字あるとする。
xxx,yyy,zzzの部分の文字数の配分は通りで、かつ各文字はX,Y,Z以外の25通りが取れる。
また***の部分はそれぞれ26通りが取れる。
よって求める解はNとSの長さだけによって決まり、Sの文字のうち分けは関係なくである。

事前に|S|に対し累積和を求めておこう。
すると後者のクエリに対しを答えるだけでよくなる。

前者のクエリの合計文字列数の制限より、|S|の組み合わせは√2*10^5通り程度しかないので、必要なテーブル数をうまく抑えることが出来ず。

ll mo=1000000007;

ll modpow(ll a, ll n) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

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;
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:combi(P_+Q_-1,Q_);}

int M,L;
string S;
ll p[2][201010];
int r25_26;

vector<int> V[101010];

inline int mulmod(int a,int b,int mo) {
	int d,r;
	if(a==0 || b==0) return 0;
	if(a==1 || b==1) return max(a,b);
	__asm__("mull %4;"
	        "divl %2"
		: "=d" (r), "=a" (d)
		: "r" (mo), "a" (a), "d" (b));
	return r;
}

void create(int len) {
	if(V[len].size()) return;
	int i;
	int a=1;
	ll sum=0;
	FOR(i,101010) {
		sum += mulmod(hcomb(len,i),a,mo);
		if(sum>=mo) sum-=mo;
		V[len].push_back(sum);
		a=mulmod(a,r25_26,mo);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p[0][0]=p[1][0]=1;
	FOR(i,200000) p[0][i+1]=p[0][i]*25%mo, p[1][i+1]=p[1][i]*26%mo;
	
	r25_26=25*modpow(26,mo-2)%mo;
	
	cin>>M>>S;
	L=S.size();
	create(L);
	while(M--) {
		cin>>i;
		if(i==1) cin>>S, L=S.size(), create(L);
		else {
			cin>>x;
			if(x<L) cout<<0<<endl;
			else cout<<V[L][x-L]*p[1][x-L]%mo<<endl;
		}
	}
}

まとめ

うまく抑えられると言いつつ、long longでMLEしてしまった。
考えたら要素数450*10^5程度の配列で8byte整数取ったらそりゃMLEするよね…。