题解：P10101 [ROIR 2023 Day 2] 一个普通的字符串问题

· · 题解

Solution

一道普通的组合计数问题。

考虑现在有三种点，\rm A、\rm B、\rm C，表示这三种颜色的连续段。

我们需要保证这三种颜色的连续段两两相邻的次数满足题目所给的条件。再次基础上，如果我们知道三种颜色分别出现了多少次，就可以具体分配内部 \rm a、\rm b、\rm c 的个数以实现目标。

后者是平凡的，关注一下前面的问题。

先考虑计算 \rm A、\rm B、\rm C 出现的次数。我们发现，除了第一个位置以外，其他的字母必定为某一条相邻关系的出边。也就是说，如果我们枚举起点，我们就知道每个位置的出现次数了。

显然我们还可以判断，那种点的最后一个是没有出边的，具体表现为这种点的总出边比这种点的出现次数少 1。

如果只有一种点出现，答案是 3（如果 n=1）或 1（n>1），下面不妨设有两种点出现。

一种很自然的想法是，我们可以把每个点的所有出边赋上颜色，表示它走向另外两个点中的哪一个。每一种序列都会对应唯一一个颜色的赋值方式，但是有的颜色赋值方式可能是不合法的。

假设 \rm A 的最后一个点没有出边。当 \rm B 和 \rm C 的最后一个点走向的都不是 \rm A，那么最后一个 \rm A 会提前出现，这时候就路断了。而如果 \rm B 或 \rm C 的最后一个走向 \rm A，那么就是合法的。不妨设 \rm B 最后一个走向 \rm A，那么 \rm A 之后显然不会返回 \rm B，有可能已经结束了，有可能返回到 \rm C。\rm C 这时候也不能去 \rm B，但是它又不能结束（根据假设），因此会在 \rm A 和 \rm C 中徘徊，最终正确的停在 \rm A。

这样写几个组合数就好了。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e6+10,MOD=1e9+7;
int op,n,m,q,frac[MAXN],inv[MAXN];
int qpow(int base,int p) {
    int ans=1;
    while(p) {
        if(p&1) ans=ans*base%MOD;
        base=base*base%MOD,p>>=1;
    }
    return ans;
}
int C(int u,int d) {
    if(u>d) return 0;
    return frac[d]*inv[u]%MOD*inv[d-u]%MOD; 
}
string S;
int cnt[3][3];
signed main() {
    freopen("str.in","r",stdin);
    freopen("str.out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    m=2000000;
    frac[0]=1;
    ffor(i,1,m) frac[i]=frac[i-1]*i%MOD;
    inv[m]=qpow(frac[m],MOD-2);
    roff(i,m-1,0) inv[i]=inv[i+1]*(i+1)%MOD;
    cin>>op>>q;
    ffor(i,1,q) {
        cin>>S,n=S.size(),S="&"+S;
        if(n==1) {
            cout<<3<<'\n';
            continue ;
        }
        int flg=1;
        memset(cnt,0,sizeof(cnt));
        ffor(j,2,n) cnt[S[j-1]-'a'][S[j]-'a']++,flg&=(S[j]==S[1]);
        if(flg) {
            cout<<1<<'\n';
            continue ;  
        }
        int ans=0;
        ffor(s,0,2) {
            int col[3]={0,0,0},in[3]={0,0,0},out[3]={0,0,0};
            col[s]++;
            ffor(c1,0,2) ffor(c2,0,2) if(c1!=c2) in[c2]+=cnt[c1][c2],out[c1]+=cnt[c1][c2],col[c2]+=cnt[c1][c2];
            int flg=0,psl=0,ed=0;
            ffor(c,0,2) {
                if(out[c]!=col[c]&&out[c]+1!=col[c]) flg=1;
                if(out[c]!=col[c]) psl++,ed=c;
            }
            if(out[s]==0) continue ;
            if(flg||psl!=1) continue ;
            int mul=C(cnt[0][1],out[0])*C(cnt[1][0],out[1])%MOD*C(cnt[2][0],out[2])%MOD;
            if(ed==0) mul=(mul-C(cnt[0][1],out[0])*C(cnt[1][0],out[1]-1)%MOD*C(cnt[2][0],out[2]-1)%MOD)%MOD;
            else if(ed==1) mul=(mul-C(cnt[0][1],out[0]-1)*C(cnt[1][0],out[1])%MOD*C(cnt[2][1],out[2]-1)%MOD)%MOD;
            else mul=(mul-C(cnt[0][2],out[0]-1)*C(cnt[1][2],out[1]-1)%MOD*C(cnt[2][0],out[2])%MOD)%MOD;
            ffor(c,0,2) {
                if(col[c]==0) {
                    if(cnt[c][c]!=0) mul=0;
                    continue ;
                }
                mul=mul*C(col[c]-1,cnt[c][c]+col[c]-1)%MOD;
            }
            ans=(ans+mul)%MOD;
        }
        cout<<(ans%MOD+MOD)%MOD<<'\n';
    }
    return 0;
}

我怎么想不到 \rm BEST 引理，这辈子真有了。