专栏文章

题解：P11487 「Cfz Round 5」Gnirts 10

AA2_Zenith
P11487题解参与者 7已保存评论 6

文章操作

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

当前评论
6 条
当前快照
1 份
快照标识符
@miqmj334
此快照首次捕获于
2025/12/04 07:14
3 个月前
此快照最后确认于
2025/12/04 07:14
3 个月前
查看原文
挺好的题，来写题解了！
首先，我们可以想到，要对答案是 ii 的 0101 序列 TT 计数。不妨设这样的串的数量是 F(i)F(i)，那么答案是 ∑i=1niF(i)\sum\limits_{i=1}^niF(i)。
令 PreiPre_i 为 SS 的长度为 ii 的前缀。
考虑对 SS 中长度为 ii 的前缀检查一个 0101 串 TT 是否合法。我们不难想到一个正确的贪心：设当前匹配到 sis_i，设 sis_i 与 TpT_p 匹配，那么 si+1s_{i+1} 匹配到 TpT_p 往后第一个等于 si+1s_{i+1} 的位置，没有那么整个前缀就匹配失败了。
那么我们将 TT 划成若干个由极长的 0/10/1 组成的连续段（伏笔 1），不难发现这时的子序列要么在某一段内一点不取，要么就取一段前缀（其实可以合并成一种情况）。
发现若 TT 中有 PreiPre_i 做为前缀，那么其一定是在 PreiPre_i 中插入若干个 0/10/1 连续段的方式生成的。怎么不重不漏的插呢？不妨对于相邻的两个字符讨论。
0000：只能插 11。因为伏笔 1 中的连续段可以取完，然后跳过整个 11 段，再继续取。
0101：只能插 00。因为是前缀嘛。
1010：只能插 11，原因同上。
1111：只能插 00，原因同上。
这个限制可以规约成：设相邻两个字符中右边的那个是 xx，那么中间只能填 1−x1-x。
不难发现这个限制能够以一种成功的方式归约到 11 前面的部分与 PrepPre_p 后面的部分。（这里假设我们在算 F(p)F(p)。）
原因很简单：对于 11 前面的部分，肯定不能与之相同，正好符合我们的这个条件；
对于 pp 后面的部分，其肯定不能与 p+1p+1 相同，不然答案肯定是 p+1p+1 或者更多。p=n+mp=n+m 的情况另算。
那么我们设现在有 C0C_0 个可以插 00 的空隙，C1C_1 个可以插 11 的空隙，已经用掉 S0S_0 个 00，S1S_1 个 11 了。
那么答案就是 F(m−S0,C0)×F(n−S1,C1)F(m-S_0,C_0) \times F(n-S_1,C_1)。其中 F(n,k)=(n+k−1k−1)F(n,k)=\dbinom{n+k-1}{k-1}，但是 F(0,0)=1F(0,0) =1。
直接预处理组合数然后 O(n+m)O(n+m) 算出就好了。
对于 p=n+mp=n+m 的情况：考虑 SS 中是否有 nn 个 11 与 mm 个 00，有的话就给总答案加上 n+mn+m。
不值得注意的是，这玩意在赛时卡了我快半个小时。
就做完了。
欢迎大家多多膜拜我的学长/IOIAKer @Sharpsmile，他以 0.01h 的优势拿下了本场比赛的 rk1。
CPP
#include<bits/stdc++.h>
#define int long long
#define doub long double
#define PII pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define PC __builtin_popcountll
using namespace std;
const int maxn=6e6+7;
const int mod=2933256077;
int n,m;
bool Ss[maxn];
int Fac[maxn];
int iFac[maxn];
inline int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ull*ans*a%mod;
        a=1ull*a*a%mod;
        b>>=1;
    }   
    return ans; 
}
inline void Init(){
    Fac[0]=1;
    for(int i=1;i<=n+m+5;i++)Fac[i]=1ull*Fac[i-1]*i%mod;
    iFac[n+m]=qpow(Fac[n+m],mod-2);
    for(int i=n+m-1;i>=0;i--)iFac[i]=1ull*iFac[i+1]*(i+1)%mod;
}
inline int C(int n,int m){
    if(n<0||m<0||n<m)return 0;
    return 1ull*Fac[n]*iFac[m]%mod*iFac[n-m]%mod;
}
inline int F(int n,int m){
    if(n<0||m<0)return 0;
    if(n==0&&m==0)return 1;
    return C(n+m-1,m-1);
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    cin>>n>>m;
    Init();
    for(int i=1;i<=n+m;i++){
        char t;
        cin>>t;
        Ss[i]=t-'0';
    }
    int C0=0,C1=0;
    int S0=0,S1=0;
    int ans=0;
    for(int i=0;i<n+m;i++){
        if(i){
            if(Ss[i]==0)S0++;
            else S1++;
        }
        if(Ss[i+1]==0)C1++;
        else C0++;
        ans=(ans+1ull*i*F(m-S0,C0)%mod*F(n-S1,C1)%mod)%mod;
    }
    if(Ss[n+m]==0)S0++;
    if(Ss[n+m]==1)S1++;
    if((S0==m)&&(S1==n))ans+=(n+m);
    ans%=mod;
    cout<<ans<<endl;
    return 0;
}

评论

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

正在加载评论...