P12028 [USACO25OPEN] Moo Decomposition G

题目传送门

“这是什么地方？”

教练当模拟赛出的。没有一眼这个题。我是不是该退役了。

另外警示一下后人。

---

进入正题。

计数题优先考虑排列组合和 dp，然而在推了半天的 dp 式子后还是过不去样例，所以我们考虑排列组合。

原题保证了 S 串可以分解，这也能说明 T 串可以分解。

接下来我们证明这个结论。

S 串可以分解，说明 \((k+1)|n\)。

如果 T 串前面有若干个 O 的话，那么第一个循环节是以 O 打头的，没有 M 能选它们，S 串就分解不出来了。与题目给的假设矛盾了，所以原假设不成立。

所以 T 串一定是以 M 打头。如果 T 串多了 O 或者少了 O 的话，那 S 的第一个循环节还是会有选不上的 O，S 仍然无法划分出来。所以原假设不成立。

于是可以先考虑一个循环节的情况。因为每个 O 都必须接到它前面 M 的后面，所以我们倒序枚举 T，每遇到一个 M 就排列组合一次，选它后面的 O。

因为 O 可以随便选，所以如果这个 M 的位置为 \(pos\)，T 的串长为 \(n\)，并且它后面有 \(m\) 个 M 的话，它选 O 的方案数就是 \(C_{n-i-m*k}^{k}\)。

一个循环节的答案显然就是所有 M 选择 O 方案数之积 \(res\)。

当我们有多个循环节的时候，如果存在两个循环节 \(l,r(l<r)\)，\(l\) 中的 M 去选了 \(r\) 中的 O，那么 \(l\) 中就会剩一个 O，但是 \(r\) 中的那个 M 选不了这个 O，\(l\) 前的循环节如果选了这个 O 也会有这个问题。所以我们不可能跨循环节选择。

既然如此，说明每个循环节都是独立的，每个循环节的方案直接相乘就是答案。当有 \(L\) 个循环节的时候，答案就是 \(res^L\)。

（补充：\(C_n^m=\frac{n!}{m!(n-m)!}\)，模意义下要使用费马小定理处理阶乘的逆元）

（另外，设 \(inv_i\) 为 \(i!\) 的逆元，则 \(inv_i=inv_{i+1} \times (i+1)\)。）

代码也是非常的简短：

P12028

#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();}while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}const int N=1e6+6;
const int mod=1e9+7;
int k,n,qwq,awa,ans=1,inv[N],pw[N];
char s[N];inline int qpow(int a,int b){//快速幂 int res=1;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;
}inline int C(int n,int m){return pw[n]*inv[m]%mod*inv[n-m]%mod;
}inline void INIT(){//预处理阶乘及其逆元 pw[0]=1;for(int i=1;i<=n;i++){pw[i]=pw[i-1]*i%mod;}inv[n]=qpow(pw[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(),qwq=read();scanf("%s",s+1); INIT();ans=1;for(int i=n;i>=1;i--){if(s[i]=='M'){ans=ans*C(n-i-awa*(k+1),k)%mod;awa++;}}ans=qpow(ans,qwq);printf("%lld",ans);return 0;
}