题解：P12028 [USACO25OPEN] Moo Decomposition

此题重点：看数据范围。

Preface

第一场 USACO

\text{\color{gold}Au}

，481 pts，本来自我感觉良好，及格线一出，850！？~~直接喷血而亡~~。

不过第一题完全没有 25 年金组该有的难度，后两题也偏简单，及格线这么高倒是可以理解。

Problem

P12028

Solution

首先 USACO 估计是脑子没转过来，居然把 L 定了个

10^{18}

，乍一看很吓人，听起来也很厉害。但是稍微想想就知道，L 这么大只有一种可能，就是每一段互相独立，最后结果用快速幂乘起来。接下来就好算了。

但是这毕竟是一篇题解，考场上可以直接开始写代码了，但我们这里还是得证明一下的。

首先发现题目给定了一定至少有一个解，说明整个串中的 M 和Ｏ的数量一定是

1

比

K

的，说明每一段中 M 和Ｏ的比例也是一定的。所以从最后一段开始匹配，发现每匹配完一段一定是一个 M 和Ｏ都不会剩下。也就是说每一段匹配是都是完全独立的。

现在我们就只需要求出匹配一段的方案数，再算个快速幂就行了。

如何求出每一段匹配方数？我们从后往前遍历。记录

cnt

表示目前有几个未匹配的 O，每遇到一个 M 就把答案乘上

{cnt \choose K}

，也就是所有

cnt

个 O 里选出

K

个与这个 M 匹配的方案数，然后

cnt = cnt - K

，因为现在就只剩

cnt - K

个 O 了。而遇到一个 O 就直接

cnt + 1

。

现在最后一个问题，如何计算

{cnt \choose K}

？直接预处理一个阶乘数组

fac_i

表示

i !

，根据排列组合的定义

{cnt \choose K}

就是

\dfrac{cnt !}{K! \cdot (cnt - K)!}

但是由于要取余做除法自然就需要求逆元，我既然都写了快速幂就直接用了费马小定理。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k, n, l, P = 1e9 + 7, cnt, fac[1000005], ans = 1;
//fac = factorial = 阶乘
string s;
int fasp(int x, int y){
	//x to the yth
	if(y == 1)return x;
	if(y == 0)return 1;
	int val = fasp(x, y / 2);
	if(y % 2)return (val % P * val % P * x % P) % P;
	else return (val % P * val % P) % P;
}
signed main(){
	cin>>k>>n>>l;
	cin>>s;
	fac[0] = 1;
	for(int i = 1; i <= n; i++){
		fac[i] = (fac[i - 1] % P * i % P) % P;
	}
	for(int i = n - 1; i >= 0; i--){
		if(s[i] == 'O'){
			cnt++;
			continue;
		}
		//否则就需要开始配对了
		//对于这个 M 一共有 （cnt 选 k） 种方案
		//选完后将 cnt 也就是能选的 O 的数量减 k
		//选择 = cnt! / ((cnt - k)! * k!)
		int div = (fac[cnt - k] % P * fac[k] % P) % P;
		//除法得用乘法逆元做
		//不过反正都有快速幂了
		int inv = fasp(div, P - 2) % P;
		ans = (ans % P * (fac[cnt] % P * inv % P) % P) % P;
		cnt -= k;
	}
	cout<<fasp(ans, l) % P;
	return 0;
}

Result

Result。

还是得吐槽一句 USACO 但凡聪明一点把 L 定一个

10^3

肯定会卡掉一大堆尝试其他方式优化，没证出来每部分独立的人，及格线也就不用 850 了。

求赞。

题解：P12028 [USACO25OPEN] Moo Decomposition

文章操作

题解：P12028 [USACO25OPEN] Moo Decomposition

Preface

Problem

Solution

Code

Result

相关推荐

评论

题解：P12028 [USACO25OPEN] Moo Decomposition