专栏文章

P12840 [蓝桥杯 2025 国 A] OCR 校正 解题报告

__mi_ka_
P12840题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip21te1
此快照首次捕获于
2025/12/03 04:53
3 个月前
此快照最后确认于
2025/12/03 04:53
3 个月前
查看原文

题目大意

给定一个 长度为 nn 的字符串，这个字符串的首尾两个字符是 0，而其他字符都是 O。你可以做一些操作使得这个字符串的所有字符都变为 0：在第一次操作你可以随便选取一个 O 将其变成 0，其他操作只能选取和 0 相邻的字符 O 将其变成 0。求不同的操作顺序数对 109+710^9+7 取模。
在本题中 n=2025n=2025。

解题思路

~考场上被这道题卡了半个小时~
我们可以选择枚举第一次操作所操作的字符，这个字符可以是第 22 个字符到第 n−1n-1 个字符中的任意一个。
对第 ii 个字符这次操作，我们将整个需要操作的字符串变成了：
0O…O⏟k1个O0O…O⏟k2个O00\underbrace{O\dots O}_{k_1个O}0\underbrace{O\dots O}_{k_2个O}0
其中 k1=i−2k_1=i-2，k2=n−1−ik_2=n-1-i，这里 k1k_1 或 k2k_2 可能是 00。
如果只对前面的 k1k_1 个 O 的子串进行操作，每次只能连续个 O 的开头或者结尾进行操作，在这个子串变成单个 O 之前每次操作都有两种选择，一共 k1−1k_1-1 次，因此操作有 2k1−12^{k_1-1} 种。注意：当且仅当 k1=0k_1=0 时，这个式子不成立，此时没有操作，即操作种类数可视为 11 种。所以只对前面的 k1k_1 个 O 的子串进行操作的操作种类数为 ans1=2[k1>0](k1−1)ans_1=2^{[k_1>0](k_1-1)} 种，其中 [bool][\text{bool}] 为 bool 表达式的值。
同理，只对后面 k2k_2 个 O 的子串进行操作的操作种类数为 ans2=2[k2>0](k2−1)ans_2=2^{[k_2>0](k_2-1)}。
对这两种子串的操作是独立的。也就是说，对左子串的顺序已定的 k1k_1 个操作和对右子串的顺序已定 k2k_2 个操作可以随意组合（不能改变子串内的操作的已定相对顺序）组成长度为 k1+k2k_1+k_2 的合法操作。这个随意组合的种类数为 (k1+k2)!k1!×k2!\frac{(k_1+k_2)!}{k_1!\times k_2!}，即全排列中定了 k1k_1 个操作的相对顺序和另外 k2k_2 个操作的相对顺序。
由以上推导，最终答案为：
ans=∑i=2n−12[k1>0](k1−1)×2[k2>0](k2−1)×(k1+k2)!k1!×k2!ans=\sum_{i=2}^{n-1}2^{[k_1>0](k_1-1)}\times2^{[k_2>0](k_2-1)}\times\frac{(k_1+k_2)!}{k_1!\times k_2!}
其中 k1=i−2k_1=i-2，k2=n−1−ik_2=n-1-i。
可以对阶乘及其逆元预处理时间复杂度 O(n)O(n)，O(nlog⁡n)O(n\log n)。然后再 O(nlog⁡n)O(n\log n) 枚举统计答案，总时间复杂度 O(nlog⁡n)O(n\log n)。

AC Code

CPP
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n,ans;
int fac[3000],inf[3000];
int re()
{
	int x=0,p=1;
	char y=getchar();
	for(;y>'9'||y<'0';y=getchar())
		if(y=='-')
			p=-p;
	for(;y>='0'&&y<='9';y=getchar())
		x=x*10+y-'0';
	return x*p;
}
void wr(int x)
{
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		wr(x/10);
	putchar(x%10+'0');
}
int ksm(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a*=a,a%=mod)
		if(b&1)
			ans*=a,ans%=mod;
	return ans;
}
void pre()//预处理阶乘及其逆元 
{
	fac[0]=inf[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
	inf[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i;i--)
		inf[i]=inf[i+1]*(i+1)%mod;
}
signed main()
{
	n=re();//n=2025时输出的是本题的答案 
	pre();
	for(int i=2;i<n;i++)
	{
		int k1=i-2,k2=n-1-i;
		ans+=ksm(2,k1?k1-1:k1)*ksm(2,k2?k2-1:k2)%mod*fac[k1+k2]%mod*inf[k1]%mod*inf[k2]%mod;
		ans%=mod;
	}
	wr(ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...