题解：CF1608D Dominoes

· · 题解

感觉我在青题紫做，因为这题是 NOIP 模拟赛 T3（

首先，显然有左格的 W 个数等于右格的 B 个数，右格的 W 个数等于左格的 B 个数。

而加入一个 WB 或者 BW 显然不会影响上面的条件，所以 WW 的个数等于 BB 的个数。

又注意到：

WW[这里可以插入任意个 BW]BB[这里可以插入任意个 WB]

所以，存在 WW 和 BB 时，可以有任意个 WB 和 BW。

而没有 WW 和 BB 的时候，只可能全是 WB 或全是 BW。

所以，答案可以转化为：WW 和 BB 个数相等的方案数，减去没有 WW 和 BB 的方案数，加上全是 WB 和全是 BW 的方案数。

后两个是容易的，重点在于第一种。

我们设有 a_1 个 WW（指输入时的状态），a_2 个 W? 或 ?W，b_1 个 BB，b_2 个 B? 或 ?B，c 个 ??。

首先，我们给所有 ?? 的左格染上颜色。枚举染上的 W 个数，设为 i。这样就不存在 ?? 了。

接下来，枚举染成 WW 的 W? 或 ?W 个数，设为 j，则染成 BB 的 B? 或 ?B 为 a_1+j-b_1。总方案数为：

\sum_i \sum_j \dbinom ci \dbinom{a_2+i}j \dbinom{b_2+c-i}{a_1+j-b_i}

之后，你需要知道有一个东西叫做范德蒙德卷积：

\sum_i\dbinom ni\dbinom m{k-i}=\dbinom{n+m}k

于是：

\begin{aligned} &\sum_i \sum_j \dbinom ci \dbinom{a_2+i}j \dbinom{b_2+c-i}{a_1+j-b_i}\\ &=\sum_i \sum_j \dbinom ci \dbinom{a_2+i}{a_2+i-j} \dbinom{b_2+c-i}{a_1+j-b_i}\\ &=\sum_i \dbinom ci \dbinom{a_2+b_2+c}{a_2+i+a_1-b_1}\\ &=\sum_i \dbinom c{c-i} \dbinom{a_2+b_2+c}{a_2+i+a_1-b_1}\\ &=\dbinom{a_2+b_2+2c}{a_1-b_1+a_2+c} \end{aligned}

于是可以直接求了。复杂度 O(n)。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#define double long double
#define sqrt(x) sqrtl(x)
#define cbrt(x) cbrtl(x)
#define pow(x,y) powl(x,y)
#define sin(x) sinl(x)
#define cos(x) cosl(x)
#define tan(x) tanl(x)
#define vct basic_string
const int N=6e5+10,mod=998244353;
namespace count{...}
using namespace count;
void solve()
{
    int n;
    cin>>n;
    int a1=0,a2=0,b1=0,b2=0,c=0;
    mi s1=1,s2=1,s3=1;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        int x=(s[0]=='?'?0:(s[0]=='W'?1:2)),y=(s[1]=='?'?0:(s[1]=='W'?1:2));
        if(x==1||y==2) s2=0;
        if(x==2||y==1) s3=0;
        if(x==0&&y==0) s1*=2,c++;
        if(x==1&&y==1) a1++,s1=0;
        if(x==2&&y==2) b1++,s1=0;
        if((x==1&&y==0)||(x==0&&y==1)) a2++;
        if((x==2&&y==0)||(x==0&&y==2)) b2++;
    }
    mi ans=C(a2+b2+c*2,a1-b1+a2+c)-s1+s2+s3;
    cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    while(t--) solve();
    return 0;
}

:::