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\)。
总结
- 每个串单独求方案数。
- 从后向前枚举，按照上述方式进行统计。
- 最终答案为 \(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==Lcin>>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;
}