P12028 [USACO25OPEN] Moo Decomposition G 題解

題目傳送門

我的博客

前言

涉及知識：階乘、逆元、組合數。

思路

拿到這道題，相信數學比較好的人已經有想法了——一定和組合數相關。

為什么呢？看下面這個例子。

MOOOO...OOOO//共有 n 個 O

那這個字符串分解出的子序列個數（這里請先忽略本題中每個子序列均需合法的這個條件）是不是就是 \(C_{n}^{k}\) 嗎。

那么，對于每個M，都是與這個M后面O的個數有關的組合數嗎？

不完全是。比如樣例 \(1\)。第一個M后面有 \(4\) 個O，但是顯然不能任取兩個，因為這樣的話另一個子序列就不合法了。如下。

MOomoO//小寫的子序列不合法

所以我們需要倒著枚舉，且必須保證每個子序列均合法。

那么哪些O可以對它之前的M有作用呢？

只需要保證從后向前的每個M的后面都有 \(k\) 個O即可。于是我們每次遇到O就讓 \(cnt\) 加 \(1\)，每次遇到M就讓 \(cnt\) 減 \(1\)，同時統計 \(C_{cnt}^k\)。

再想有 \(L\) 個串 \(S\) 拼在一起。先說結論：每個串都可以獨立求貢獻，每個串 \(S\) 對前后兩個串不會產生貢獻。證明如下。

如果一個串對前后的串有貢獻，那么必然為 \(S=\)O......M這種類型。可是如果串 \(S\) 在開頭，那么第一個字符O必然是不合法的（因為它前面沒有可以與之匹配的M）。如果 \(S\) 在結尾，那么最后一個字符M必然是不合法的（因為它后面沒有O）。因此，每個串必然不會對前后相鄰的串有貢獻。因此每個串可以單獨計算。

所以只需要求一個串的方案數 \(ans\)，最終答案為 \(ans^L\)。

總結

1. 每個串單獨求方案數。
2. 從后向前枚舉，按照上述方式進行統計。
3. 最終答案為 \(ans^L\)。

警示后人

• 勤取模！
• 認真讀題，形如每個子序列之類的字眼看仔細。
• 十年OI一場空，不開________見祖宗

代碼

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define int long long 
#define ___ __int128
#define INF 0x3f3f3f3f3f3f3f3f 
inline int Read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return x*f;
}
inline void Write(int x){
	if(x<0) {putchar('-');x=-x;}
	if(x>9) Write(x/10);
	putchar(x%10+'0');
}
const int N=1e6+10;
const int mod=1e9+7;
int k,n,m,t,ans;
int jc[N],inv[N];
//jc：階乘，inv：逆元
string s;
int qsm(int a,int b){//快速冪板子
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int C(int n,int m){//組合數，也可以用楊輝三角實現
	if(m>n) return 0;
	return jc[n]%mod*inv[n-m]%mod*inv[m]%mod;
}
void init(){//求階乘、逆元
	jc[0]=1;//別忘了賦初值
	for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;//階乘
	inv[n]=qsm(jc[n],mod-2);
	for(int i=n-1;i>=0;i--){//倒敘線性求逆元
		inv[i]=inv[i+1]*(i+1)%mod;
	}
}
signed main(){
	k=Read();n=Read();m=Read(); //m==L
	cin>>s;s=" "+s;//s 串下標從 1 開始
	init();//別忘了加到主函數里面
	ans=1;t=0;//t：當前可用的 O 的數量
	for(int i=n;i>=1;i--){//倒敘
		if(s[i]=='O') t++;
		else {
			ans*=C(t,k)%mod;
			ans%=mod;
			t-=k;//需要給當前 M 留下 k 個 O
		}
	}
	ans=qsm(ans,m)%mod;
	printf("%lld\n",ans);
	return 0; 
}