Atcoder 171_fK.Strivore(テクニックのある組み合わせ数学)

Atcoder 171_fK.Strivore(テクニックのある組み合わせ数学)
トランスファゲート
テーマの大意
長さm文字列を与えて、n文字を挿入した後に何種類の異なる文字列を形成することができるかを聞きます.
問題を解く構想.
1つの誤った解法は、与えられた文字列の各文字を仕切り板と見なし、挿入法を用いてどれだけの挿入方法があるかを計算し、最後に26のn次方を乗じることである.このやり方には明らかな問題があるのは、重く考えていないことだ.例えば、所与の文字列abcには2文字が挿入され、まず所与の文字列は仕切りとして文字列を「①a②b③c④」に区切る.もし私たちが2番位に「ba」を挿入して文字列ababcを得ると同時に、3番位置に「ab」を挿入しても文字列ababcを得る.この2つの異なる挿入方法で同じ文字列が得られることがわかり,1つの場合として計算すべきであるが,2回計算した.  さらに重複の原因を分析し、上記の例ababcを用いて、重複の原因は、この文字列の最初のbを与えられた文字列abc中のセパレータbとすることができ、ababc中の2番目のbを与えられた文字列abc中のセパレータbとすることもできるからである.このように、abbbcの3番目のbが与えられた文字列abcのbであり、aabbcの2番目のbがabcのbであることを規定するなど、1つの文字列の中で仕切り文字ができるだけ遅く現れるべきであることを強制的に規定している.言い換えれば、スペーサの後ろの位置にスペーサ文字を有する文字列を挿入することはできない.例えば、位置②はアルファベットaを含む文字列を挿入することができず、位置③はアルファベットbを含む文字列を挿入することができない.このようにしても、上記の例では、bを含む文字列baを3番ビットに挿入すれば、2番ビットにbを3番ビットに挿入してaに置き換えるという、上記の規定を満たす挿入方法を見つけることができます.そのため②③④番の位置に挿入されたアルファベットは位置の前の仕切り文字と一致しないため、25種類の挿入方法しかありません.1番の位置は26種類の挿入方法で任意に挿入できます.1番の位置を列挙する長さを考慮し,残りの位置を空欄に挿入すればよい,詳細はコードを参照する.
コード#コード#

#include 
#include 
#include 
#define LL long long
const int MAXN = 2e6 + 5;
const int Mod = 1e9 + 7; 
int n, m;
char str[MAXN];
LL fact[MAXN], inv[MAXN]; 

//    
LL qpow(LL a, int b) {
	LL res = 1;
	for (; b; b >>= 1, a = a * a % Mod)
		if (b & 1) res = a * res % Mod;
	return res;
}

//    
LL C(int n, int m) {
	return fact[n] * inv[n - m] % Mod * inv[m] % Mod;
} 

int main() {
	LL ans = 0;
	scanf("%d%s", &n, str + 1);
	m = strlen(str + 1);
	
	//   
	fact[0] = 1;
	for (int i = 1; i <= n + m; i++) fact[i] = fact[i - 1] * i % Mod;
	
	//    ，inv[i]  i       
	inv[n + m] = qpow(fact[n + m], Mod - 2);
	for (int i = n + m - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % Mod;
	
	//        
	/*
	   ，  ①       i           ，   ①      26   
	   ，  m-1   n-i       ，        25   
	  ，          
	*/
	for (int i = 0; i <= n; i++) 
		ans  = (ans + qpow(26, i) * C(n + m - i - 1, m - 1) % Mod * qpow(25, n - i) % Mod) % Mod;
	printf("%lld
", ans);
	return 0;
}