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

· · 题解

题目大意

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

在本题中 n=2025。

解题思路

~考场上被这道题卡了半个小时~

我们可以选择枚举第一次操作所操作的字符，这个字符可以是第 2 个字符到第 n-1 个字符中的任意一个。

对第 i 个字符这次操作，我们将整个需要操作的字符串变成了：

0\underbrace{O\dots O}_{k_1个O}0\underbrace{O\dots O}_{k_2个O}0

其中 k_1=i-2，k_2=n-1-i，这里 k_1 或 k_2 可能是 0。

如果只对前面的 k_1 个 O 的子串进行操作，每次只能连续个 O 的开头或者结尾进行操作，在这个子串变成单个 O 之前每次操作都有两种选择，一共 k_1-1 次，因此操作有 2^{k_1-1} 种。注意：当且仅当 k_1=0 时，这个式子不成立，此时没有操作，即操作种类数可视为 1 种。所以只对前面的 k_1 个 O 的子串进行操作的操作种类数为 ans_1=2^{[k_1>0](k_1-1)} 种，其中 [\text{bool}] 为 bool 表达式的值。

同理，只对后面 k_2 个 O 的子串进行操作的操作种类数为 ans_2=2^{[k_2>0](k_2-1)}。

对这两种子串的操作是独立的。也就是说，对左子串的顺序已定的 k_1 个操作和对右子串的顺序已定 k_2 个操作可以随意组合（不能改变子串内的操作的已定相对顺序）组成长度为 k_1+k_2 的合法操作。这个随意组合的种类数为 \frac{(k_1+k_2)!}{k_1!\times k_2!}，即全排列中定了 k_1 个操作的相对顺序和另外 k_2 个操作的相对顺序。

由以上推导，最终答案为：

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!}

其中 k_1=i-2，k_2=n-1-i。

可以对阶乘及其逆元预处理时间复杂度 O(n)，O(n\log n)。然后再 O(n\log n) 枚举统计答案，总时间复杂度 O(n\log n)。

AC Code

#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;
}