题解 CF1608D 【Dominoes】

enucai · 2021-12-13 22:04:36 · 题解

~~前言：这可能是蒟蒻能写出来的计数题的难度上限了~~

题意简述

让你给 n 个多米诺骨牌黑白染色，每个骨牌有两个格子。

若将这 n 个骨牌重新排列后至少存在一种方案，使得 \forall i，第i个骨牌右边格子颜色与第 (i\bmod n)+1 个骨牌左边颜色不同，则这种染色方法合法。

问你有几种合法的染色方案。

~~可能不是讲得很清楚，看不懂去看英文题面吧（逃~~

思路简述

首先通过观察，我们发现对于任意一种合法的染色方案：

BB 和 WW 这两种颜色类型的骨牌数量一定是相等的。
如果有 BW 和 WB 种类的骨牌，那么至少要有 1 个 BB 和 1 个 WW 类型的骨牌。

而且这两个条件是合法染色方案的充要条件。接下来是对以上两个结论的感性证明：

对于第一条结论，我们可以认为 WW 与 BB 为骨牌序列的转折点，因为一个连续的 WB 序列后面跟上一个 WW 序列后，后面就会变成连续的 BW 序列。因为所有的序列构成一个环后始终符合条件。所以，我们可以清晰地看到，两种转折点地数量一定相等。

可以来张图片：我们认为 BW 的连续序列为橙色线段，WB 的连续序列为绿色线段。那么黑点表示 BB，作为 BW 与 WB 的转折点；灰点表示 WW，作为 WB 与 BW 的转折点。因为最后环上一定是橙绿线段首尾衔接的，所以橙线段与绿线段数量相等，黑点与灰点数量相等，所以 BB 与 WW 数量也就一样多了。
对于第二条结论，如果 BW 与 WB 都存在，那么必定存在至少一个转折点，所以必定有 WW 与 BB。

性质观察完了，我们开始想想应该怎么算。

我们先定义：出现在一个骨牌左边的 W 为 W1，右边的 W 为 W2。同理，有 B1，B2，Q1 与 Q2 （ Q 表示 ? ）。假设 B1 有 i 个，W2 也有 i 个，那么可得 B2 有 n-i 个，W1 也有 n-i 个。枚举这个 i 即可算出大致合法的有几个，公式为：

\sum\limits_{i=1}^n C_{Q1}^{i-B1}\times C_{Q2}^{n-i-B2}

但是这并不符合我们推出来的结论，我们想想他们之间的差距在哪里。

经过观察，我们发现，不符合第二条结论的情况会被数进去。因此要减去有 BW 与 WB 但是没有 WW 与 BB 的情况。我们可以先减去没有 WW 与 BB 的情况，再加回只有 WB 与 BW 的情况。

要算没有 BB 与 WW 的情况，由于 BB 和 WW 的数量一定相等，所以如果已经有 BB 或 WW 了，那么就不用减。减的数量为：

2^{??}

因为只有 ?? 可以构造出 BW 与 WB 两种情况，其他的 W?,?W,?B,B? 都只能构造出一种不是 BB 且不是 WW 的情况，相当于乘了 1，等于没乘。

最后，还要算只有 WB 与 BW 的情况，那么有两种情况会加 1：

W1 与 B2 都是 0。
B1 与 W2 都是 0。

好了，总算算完了。所以最后的公式是：

\sum\limits_{i=1}^n C_{Q1}^{i-B1}\times C_{Q2}^{n-i-B2}-[bb=0\&ww=0]\times 2^{??}+[w1=0\&b2=0]+[b1=0\&w2=0]

蒟蒻代码

Talk is cheap, show me the code.

#define mod 998244353
#define int long long
int n,cnt[3][3];
string s;
int change(char x){
    if(x=='?') return 0;
    else if(x=='W') return 1;
    else if(x=='B') return 2;
}//将字符转化为数字，方便统计
int inv[100010],fact[100010],ifact[100010];
void init(){
    inv[1]=1;
    For(i,2,100000) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    fact[0]=ifact[0]=1;
    For(i,1,100000) fact[i]=fact[i-1]*i%mod;
    For(i,1,100000) ifact[i]=ifact[i-1]*inv[i]%mod;
}//阶乘预处理，用来算组合数
int C(int n,int m){
    if(n<m||m<0) return 0;
    return fact[n]*ifact[m]%mod*ifact[n-m]%mod;
}//组合数的简单计算
int qpow(int a,int p){
    if(p==0) return 1;
    int qwq=qpow(a,p/2);
    if(p%2==1) return qwq*qwq%mod*a%mod;
    else return qwq*qwq%mod;
}//快速幂模板
signed main(){
    init();
    n=read();
    For(i,1,n){
        cin>>s;
        cnt[change(s[0])][change(s[1])]++;//统计各种类型的数量
    }
    int w1=cnt[1][0]+cnt[1][1]+cnt[1][2];//算w1
    int b1=cnt[2][0]+cnt[2][1]+cnt[2][2];//算b1
    int w2=cnt[0][1]+cnt[1][1]+cnt[2][1];//算w2
    int b2=cnt[0][2]+cnt[1][2]+cnt[2][2];//算b2
    int q1=n-w1-b1,q2=n-w2-b2;//算q1和q2
    int ans=0;
    For(i,0,n) ans=(ans+C(q1,i-b1)*C(q2,n-i-b2))%mod;//先算第一个sigma
    if(cnt[1][1]==0&&cnt[2][2]==0) ans-=qpow(2,cnt[0][0]);//减去没有WW和BB的
    if(w1==0&&b2==0) ans++;
    if(b1==0&&w2==0) ans++;//加回只有BW和WB的
    cout<<ans<<endl;//Happy Ending
}