AtCoder ABC #171 : F - Strivore

こういうのがさっくり解けるようになってるのはいいことなんだけどな。
https://atcoder.jp/contests/abc171/tasks/abc171_f

問題

正整数Kと文字列Sが与えられる。
Sに英小文字をK個追加して得られる文字列は何通りか。

解法

例えばS=abcの場合、T=XaYbZcW という形の文字列を考える。
Xの部分はa以外、Yの部分はb以外、Zの部分はc以外、Wは任意の小文字を合計K個挿入することを考える。
そうするとこれらの埋め方は互いに重複しない。

L=|W|を総当たりすると、X,Y,Zの部分は25通りの小文字、Wの部分は26通りの小文字が入るので、

が解。

int K;
string S;
int N;

const ll mo=1000000007;	

ll comb(ll N_, ll C_) {
	const int NUM_=2400001;
	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:comb(P_+Q_-1,Q_);}

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


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>S;
	N=S.size();
	
	ll ret=0;
	FOR(i,K+1) {
		ret+=modpow(26,i)*modpow(25,K-i)%mo*hcomb(N,K-i)%mo;
	}
	cout<<ret%mo<<endl;
}

まとめ

こっち3分かかってないのに、Cで30分かかったのはなんなんですかね…。