题解：CF1765C Card Guessing

· · 题解

考虑计算对于所有排列总的猜对次数，答案除以 (4n)!。

考虑每种长度为 k 的序列的贡献。首先，我们先把这 k 张牌放在一个连续段里。只要它的下一个位置对应的花色是最少的，那就会产生贡献。如果连续段在最后，没有贡献。如果有多个最少花色，那下一位是什么最少花色都行，但又等概率选，和只有一个最少花色的情况等价。

下一个位置的花色必须在这 k 张牌里最少，记这 k 张中最少花色有 x 张，那么只需要在剩下 (n-x) 张里面选一张放后面就行。

连续段的位置有 (4n-k) 个。

这 k 张牌内部的顺序任意；其他没提到的牌顺序任意，再乘上 k!(4n-k-1)!。-1 的阶乘没有意义，这里认为是 0，不过不影响答案，因为此时 x 必然为 n，贡献本来就已经是 0 了。

所以，当这 k 张牌里面四种花色从小到大依次是 x,y,z,w 时，贡献就是 \mathrm C ^x_n \mathrm C ^y_n \mathrm C ^z_n \mathrm C ^w_n k! (4n-k-1)!(n-x)。由于四种花色本身没有区别，讨论一下 x,y,z,w 里有多少重复的数，乘上一个系数 u(x,y,z,w) 就行。这个系数是什么，怎么来的，留作习题。

对于原排列前 k 位的贡献是类似的，只是贡献的位置只有 1 个了，考虑少于 k 的一组牌即可。

至此已经 O(n^4)。我们可以记 f_{i,z} 表示 \sum_{x+y+z=i,x\le y\le z}\mathrm C ^x_n \mathrm C ^y_n \mathrm C ^z_n \mathrm (n-x) u(x,y,z,z+1)。则对于每个 f_{i,z}，计算 \sum_{z<w,i+w<k} f_{i,z}\mathrm C ^w_n (i+w)! (4n-i-w)! + f_{i,z} \mathrm C ^{k-i}_n (4n-k) (4n-k-1)!k! 即可。O(n^3) 处理是简单的。j 的用处似乎不大，也许有平方做法？但那样可能需要讨论比较多的系数，不想写了 qwq。

:::info[Code Time]

#include <bits/stdc++.h>
using namespace std;
const int N=2007,wac=998244353;
int f[N][N],_fa[N],*fa=_fa+1,fi[N]; // 虽然在涉及到 -1 的阶乘时一定没有贡献，但要防 RE。
int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%wac) if(b&1) ans=1ll*ans*a%wac;
    return ans;
}
int c(int n,int m){
    if(n>m) return 0;
    return 1ll*fa[m]*fi[n]%wac*fi[m-n]%wac;
}
int main(){
    int n,k;
    cin>>n>>k;
    fa[0]=1;
    for(int i=1;i<N;i++) fa[i]=1ll*i*fa[i-1]%wac;
    fi[N-1]=qpow(fa[N-1],wac-2);
    for(int i=N-1;i;i--) fi[i-1]=1ll*i*fi[i]%wac;
    int ans=0;
    for(int i=0;i<=n;i++) for(int j=i;j<=n;j++) for(int l=j;l<=n&&i+j+l<=k;l++){
        int m=i+j+l;
        if(m+l<=k){
            int qwq=1ll*c(i,n)*c(j,n)%wac*c(l,n)%wac*c(l,n)%wac*fa[m+l]%wac*fa[4*n-m-l-1]%wac*(n-i)%wac; // 考虑 (x,y,z,z) 型贡献。
            int awa;
            if(i==l) awa=1;
            else if(i==j) awa=6;
            else if(j==l) awa=4;
            else awa=12;
            ans=(ans+1ll*qwq*awa%wac*(m+l==k?(4*n-k):1))%wac;
        }
        int qwq=1ll*c(i,n)*c(j,n)%wac*c(l,n)%wac*(n-i)%wac;
        int awa;
        if(i==l) awa=4;
        else if(i==j||j==l) awa=12;
        else awa=24;
        f[m][l]=(f[m][l]+1ll*qwq*awa)%wac; // 处理 f_{i,j}。
    }
    for(int i=0;i<=k;i++) for(int j=0;j<=n;j++) for(int l=j+1;l<=n&&i+l<=k;l++) ans=(ans+1ll*f[i][j]*c(l,n)%wac*fa[i+l]%wac*fa[4*n-i-l-1]%wac*(i+l==k?(4*n-k):1))%wac;
    cout<<1ll*ans*fi[4*n]%wac<<'\n'; // 答案除以 (4n)!。
}

:::