「题单题解」数数入门

Coffee_zzz · 2025-10-10 21:01:43 · 算法·理论

P1758 [NOI2009] 管道取珠

:::info[题解]

有一个经典的 trick 是，可以将每个东西出现次数的平方转化为选择两个相同东西的方案数。对于此题，即为将 \sum {a_i}^2 转化为选择两个相同的输出序列的方案数。

考虑 dp：设 f_{i,j,k} 表示，选择两个长度为 i 的相同的输出序列，第一个输出序列由上管道中的 j 个球和下管道中的 i-j 个球构成，第二个输出序列由上管道中的 k 个球和下管道中的 i-k 个球构成的方案数。转移时枚举两个输出序列的下一位分别选择哪个管道即可。

对第一维做滚动优化，时间复杂度 \mathcal O(n^3)，空间复杂度 \mathcal O(n^2)。

:::

:::success[代码]

const int N=505,mod=1024523;
int n,m,f[2][N][N];
string s,t;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>m>>s>>t;
    f[0][0][0]=1;
    for(int i=0;i<n+m;i++){
        int x=i&1,y=(i&1)^1;
        for(int j=0;j<=min(n,i);j++){
            for(int k=0;k<=min(n,i);k++){
                if(j<n&&k<n&&s[j]==s[k]) add(f[y][j+1][k+1],f[x][j][k]);
                if(j<n&&i-k<m&&s[j]==t[i-k]) add(f[y][j+1][k],f[x][j][k]);
                if(i-j<m&&k<n&&t[i-j]==s[k]) add(f[y][j][k+1],f[x][j][k]);
                if(i-j<m&&i-k<m&&t[i-j]==t[i-k]) add(f[y][j][k],f[x][j][k]);
            }
        }
        memset(f[x],0,sizeof f[x]);
    }
    cout<<f[(n+m)&1][n][n];
}

:::

CF509F Progress Monitoring

:::info[题解]

给出的序列 b 实际上就是树的 dfs 序。由于一个子树的 dfs 序会形成一个区间，因此可以考虑区间 dp。

设 f_{l,r} 表示 b_l\sim b_r 形成一棵树的方案数，g_{l,r} 表示 b_l\sim b_r 形成一个森林的方案数。初始化 f_{i,i}=g_{i,i}=1，转移时枚举森林中第一棵树覆盖的区间，转移方程为：

答案即为 f_{1,n}。时间复杂度 \mathcal O(n^3)。

:::

:::success[代码]

const int N=505,mod=1e9+7;
int n,b[N],f[N][N],g[N][N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>b[i],f[i][i]=g[i][i]=1;
    for(int l=n;l>=1;l--){
        for(int r=l+1;r<=n;r++){
            f[l][r]=g[l][r]=g[l+1][r];
            for(int k=l;k<r;k++) if(b[l]<b[k+1]) add(g[l][r],1ll*f[l][k]*g[k+1][r]%mod);
        }
    }
    cout<<f[1][n]<<endl;
}

:::

CF449D Jzzhu and Numbers

:::info[题解]

直接计算按位与为 0 的非空子序列的数量有点困难，因此考虑对于每一个 S，计算按位与是 S 的超集的非空子序列的数量 f_S，再做一个高维差分得到按位与等于 S 的非空子序列的数量 g_S，那么答案即为 g_0。

接下来考虑怎么计算 f_{S}。显然，对于所有 a_i \supseteq S，a_i 可选可不选，但不能每个都不选；而对于所有 {a_i \nsupseteq S}，a_i 一定不能选。于是可以记 c_S 表示序列 a 中满足 a_i=S 的 a_i 的数量，d_S 表示序列 a 中满足 a_i \supseteq S 的 a_i 的数量，对 c_S 做一个高维后缀和得到 d_S，那么 f_S 就等于 2^{d_S}-1，再做高维差分得到 g_0 即可。

时间复杂度 \mathcal O(n + V \log V)。

:::

:::success[代码]

const int V=1<<20,N=V+5,mod=1e9+7;
int n,pw[N],c[N],f[N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void And(int V,int *f,int c){
    for(int k=1;k<V;k<<=1){
        for(int i=0;i<V;i++){
            if(i&k) continue;
            if(c) add(f[i],f[i^k]);
            else add(f[i],mod-f[i^k]);
        }
    }
}
void solve(){
    cin>>n;
    for(int i=1,x;i<=n;i++) cin>>x,c[x]++;
    And(V,c,1);
    pw[0]=1;
    for(int i=1;i<V;i++) pw[i]=pw[i-1]*2%mod;
    for(int i=0;i<V;i++) f[i]=pw[c[i]]-1;
    And(V,f,0);
    cout<<f[0]<<endl;
}

:::

ABC295E Kth Number

:::info[题解]

设 a 中 0 的个数为 c。题目需要我们求出 a_k 的期望值，转化一下可以变成：求对于所有 m^c 种序列 a，a_k 之和，即：

求第 k 小的数不好求，于是考虑把 a_k 的贡献拆到每一个 1 \le v \le a_k 的 v 上，式子变成：

于是我们可以枚举 v，计算有多少种 a 满足 v \le a_k。

设 a 中小于 v 的不为 0 的数有 x 个，枚举一下再添加多少个小于 v 的数，那么答案即为：

注意特判 c \lt i 的情况。

时间复杂度 \mathcal O(n^2)。

:::

:::success[代码]

const int N=2005,mod=998244353;
int n,m,k,a[N],pw[N][N],c,fac[N],infac[N],ans;
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
int C(int n,int m){
    return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==0) c++;
    }
    for(int i=0;i<N;i++){
        pw[i][0]=1;
        for(int j=1;j<N;j++) pw[i][j]=1ll*pw[i][j-1]*i%mod;
    }
    fac[0]=1,infac[0]=1;
    for(int i=1;i<N;i++) fac[i]=1ll*fac[i-1]*i%mod,infac[i]=ksm(fac[i],mod-2);
    for(int v=1;v<=m;v++){
        int x=0;
        for(int i=1;i<=n;i++) if(a[i]!=0&&a[i]<v) x++;
        int res=0;
        for(int i=0;i<k-x;i++) if(c>=i) res+=1ll*C(c,i)*pw[v-1][i]%mod*pw[m-v+1][c-i]%mod,res%=mod;
        ans=(ans+res)%mod;
    }
    cout<<1ll*ans*ksm(pw[m][c],mod-2)%mod;
}

:::

ARC139D Priority Queue 2

:::info[题解]

首先把总和拆开，将 \sum\limits_{i=1}^n a_i 转化为 \sum\limits_{j=1}^m \sum\limits_{i=1}^n [a_i \ge j]。

于是考虑枚举 j，计算 \sum\limits_{i=1}^n [a_i \ge j] 的总和。

设初始时满足 a_i \ge j 的 i 的个数等于 c，操作过程中一共加了 p 个大于等于 j 的数：

• 若 c \ge n-x+1，则最终满足 a_i \ge j 的 i 的个数等于 f(c,p)=\max(n-x+1,c+p-k)；
• 若 c \lt n-x+1，则最终满足 a_i \ge j 的 i 的个数等于 f(c,p)=\min(n-x+1,c+p)。

于是可以得到：

预处理后直接计算即可。时间复杂度 \mathcal O(n+mk)。

:::

:::success[代码]

#define int long long
const int N=2005,mod=998244353;
int n,m,k,x,a[N],pw[N][N],fac[N],infac[N],ans;
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1,a=a*a%mod;
    }
    return res;
}
int f(int c,int p){
    if(c>=n-x+1) return max(n-x+1,c+p-k);
    else return min(n-x+1,c+p);
}
int C(int n,int m){
    return fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void solve(){
    cin>>n>>m>>k>>x;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=m;i++){
        pw[i][0]=1;
        for(int j=1;j<=k;j++) pw[i][j]=pw[i][j-1]*i%mod;
    }
    fac[0]=infac[0]=1;
    for(int i=1;i<=k;i++) fac[i]=fac[i-1]*i%mod;
    infac[k]=ksm(fac[k],mod-2);
    for(int i=k-1;i>0;i--) infac[i]=infac[i+1]*(i+1)%mod;
    for(int j=1;j<=m;j++){
        int c=0;
        for(int i=1;i<=n;i++) if(a[i]>=j) c++;
        for(int p=0;p<=k;p++) ans+=f(c,p)*pw[m-j+1][p]%mod*pw[j-1][k-p]%mod*C(k,p),ans%=mod;
    }
    cout<<ans<<endl;
}

:::

ARC183C Not Argmax

:::info[题解]

首先考虑对于一个确定的排列，如何判断其是否合法。

可以参考建立笛卡尔树的过程，设当前递归到的区间为 [a,b]，找到区间内最大值所在位置 k，如果存在条件 (l_i,r_i,x_i) 满足 a \le l_i \le k \le r_i \le b 且 x_i=k，那么该排列就不合法，否则递归区间 [a,k-1] 和 [k+1,b] 直到 a=b 或 a=b+1；如果递归到的所有区间都满足条件，那么该排列就合法。

接下来考虑如何对合法的排列进行计数。参考判断排列是否合法的过程，我们考虑计算每个区间 [a,b] 内合法的排列的数量，转移时枚举区间内最大值所在位置 k，将 [a,k-1] 和 [k+1,b] 合并起来。

具体地，定义 f_{a,b} 表示，只考虑区间 [a,b] 内每个元素的相对大小，合法的长度为 b-a+1 的排列的数量。预处理 c_{k,a,b}=0/1 表示 k 能 / 不能作为区间 [a,b] 的最大值，转移时枚举满足 k \in [a,b] 且 c_{k,a,b}=0 的 k，将 [a,k-1] 和 [k+1,b] 的方案合并起来，方案数为：

初始化 f_{i,i-1}=f_{i,i}=1，答案即为 f_{1,n}。记得特判 l_i=r_i=x_i 的情况，此时答案为 0。

时间复杂度 \mathcal O(n^3)。

:::

:::success[代码]

const int N=505,mod=998244353;
int n,m,f[N][N],fac[N],infac[N];
bool c[N][N][N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int C(int n,int m){
    return 1ll*fac[n]*infac[n-m]%mod*infac[m]%mod;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
void solve(){
    cin>>n>>m,fac[0]=infac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    for(int i=1,l,r,x;i<=m;i++) cin>>l>>r>>x,c[x][l][r]=1;
    for(int l=n;l>=1;l--) for(int r=l+1;r<=n;r++) for(int x=l;x<=r;x++) c[x][l][r]=c[x][l][r]|c[x][l+1][r]|c[x][l][r-1];
    for(int i=1;i<=n;i++) if(!c[i][i][i]) f[i][i]=1;
    for(int i=0;i<=n;i++) f[i+1][i]=1;
    for(int l=n;l>=1;l--) for(int r=l+1;r<=n;r++) for(int x=l;x<=r;x++) if(!c[x][l][r]) add(f[l][r],1ll*f[l][x-1]*f[x+1][r]%mod*C(r-l,x-l)%mod);
    cout<<f[1][n]<<endl;
}

:::

ARC170C Prefix Mex Sequence

:::info[题解]

首先考虑 n \le m 的情况：

• 若 s_i=1，则 a_i 只有前缀 \operatorname{mex} 一种选择方案；
• 若 s_i=0，则 a_i 除了前缀 \operatorname{mex} 都可以选，共有 m-1 种选择方案。

直接将每个数的方案数相乘即可得到总方案数。

接着考虑 n \gt m 的情况。相比于 n \le m 的情况，此时唯一不同的点在于，a_i 的前缀 \operatorname{mex} 可能等于 m+1，导致方案数发生变化。具体地，仍然考虑分类讨论：

• 若 s_i=1：
  • 若 a_i 的前缀 \operatorname{mex} 小于等于 m，则 a_i 只有前缀 \operatorname{mex} 一种选择方案；
  • 若 a_i 的前缀 \operatorname{mex} 等于 m+1，则没有满足条件的选择方案；
• 若 s_i=0：
  • 若 a_i 的前缀 \operatorname{mex} 小于等于 m，则 a_i 除了前缀 \operatorname{mex} 都可以选，共有 m-1 种选择方案；
  • 若 a_i 的前缀 \operatorname{mex} 等于 m+1，则所有数都可以选，共有 m 种选择方案。

于是我们可以发现一个关键性质：我们只关心当前的前缀 \operatorname{mex} 是否等于 m+1，即是否 0 \sim m 的数都被选过了。

那么我们就可以进行 dp 了。设 f_{i,j} 表示考虑到第 i 个数，且 0 \sim m 中有 j 个数被选过的方案数。初始化 f_{0,0}=1，转移时考虑分类讨论：

• 若 s_i=1，则 f_{i,j+1}\leftarrow f_{i,j+1}+f_{i-1,j}；
• 若 s_i=0：
  • 选择一个没有被选择过的，不为前缀 \operatorname{mex} 的数，f_{i,j+1} \leftarrow f_{i-1,j} \times \max(m-j,0)；
  • 选择一个选择过的数，f_{i,j} \leftarrow f_{i-1,j} \times j。

设 k=\min(m+1,n)，答案即为 \sum\limits_{j=0}^{k} f_{n,j}。

时间复杂度 \mathcal O(n^2)。

:::

:::success[代码]

const int N=5005,mod=998244353;
int n,m,s[N],f[N][N],ans;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        if(s[i]==0){
            for(int j=0;j<i;j++){
                add(f[i][j+1],1ll*f[i-1][j]*max(m-j,0)%mod);
                add(f[i][j],1ll*f[i-1][j]*j%mod);
            }
        }
        else for(int j=0;j<i;j++) add(f[i][j+1],f[i-1][j]);
    }
    for(int j=0;j<=min(n,m+1);j++) add(ans,f[n][j]);
    cout<<ans<<endl;
}

:::

ABC246Ex 01? Queries

:::info[题解]

首先考虑没有修改的时候怎么做。

定义 f_{i,0} 表示考虑到第 i 位且以 0 结尾的本质不同的非空子序列的个数，f_{i,1} 表示考虑到第 i 位且以 1 结尾的本质不同的非空子序列的个数。

转移时，若 s_i 为 \tt{1}，则显然 f_{i,0}=f_{i-1,0}，否则我们强制选择第 i 位作为 \tt{0} 加入到子序列的末尾，注意不能不选，因为不选第 i 位且末位为 \tt{0} 的子序列一定在选择第 i 位的子序列中出现过，此时 f_{i,0}=f_{i-1,0}+f_{i-1,1}+1，其中加 1 是因为单独的第 i 位同样可以作为一个子序列。f_{i,1} 的转移方式同理。

初始化 f_{0,0}=f_{0,1}=0，答案即为 f_{n,0}+f_{n,1}。

接下来我们考虑怎么处理修改操作。

我们把 f 数组用矩阵维护，用下面的矩阵来记录 f 数组：

其中初始时的矩阵为：

根据转移方程可知，转移时相当于给原矩阵乘上了下面的矩阵：

其中 [\ ] 是艾佛森括号，若表达式 P 为真则 [P]=1，否则 [P]=0。

于是我们用线段树维护每一位所对应的矩阵，每次进行单点修改，查询所有矩阵的乘积即可。

时间复杂度 \mathcal O(n+q\log n)。

:::

:::success[代码]

#define int long long
const int N=1e5+5,mod=998244353;
struct mat{
    int v[4][4]={},n,m;
}a[N],val[N<<2];
mat mul(mat a,mat b){
    mat res;
    res.n=a.n;
    res.m=b.m;
    for(int i=1;i<=a.n;i++) for(int j=1;j<=b.m;j++) for(int k=1;k<=a.m;k++) res.v[i][j]+=a.v[i][k]*b.v[k][j],res.v[i][j]%=mod;
    return res;
}
void modify(int x,char c){
    a[x].n=a[x].m=3;
    a[x].v[1][1]=a[x].v[2][2]=a[x].v[3][3]=1;
    a[x].v[2][1]=a[x].v[3][1]=(c!='1');
    a[x].v[1][2]=a[x].v[3][2]=(c!='0');
    a[x].v[1][3]=a[x].v[2][3]=0;
}
void upd(int g){
    val[g]=mul(val[g<<1],val[g<<1|1]);
}
void build(int g,int l,int r){
    if(l==r){
        val[g]=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(g<<1,l,m);
    build(g<<1|1,m+1,r);
    upd(g);
}
void work(int g,int l,int r,int x){
    if(l==r){
        val[g]=a[l];
        return;
    }
    if(r<x||x<l) return;
    int m=(l+r)>>1;
    work(g<<1,l,m,x);
    work(g<<1|1,m+1,r,x);
    upd(g);
}
int n,q;
string s;
void solve(){
    cin>>n>>q>>s;
    s=" "+s;
    for(int i=1;i<=n;i++) modify(i,s[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++){
        int x;
        char c;
        cin>>x>>c;
        modify(x,c);
        work(1,1,n,x);
        mat res;
        res.n=1,res.m=3;
        res.v[1][3]=1;
        res=mul(res,val[1]);
        cout<<(res.v[1][1]+res.v[1][2])%mod<<endl;
    }
}

:::

P8321 『JROI-4』沈阳大街 2

:::info[题解]

考虑把 a_i 看作 1 类数，b_i 看作 2 类数，将所有 a_i 和所有 b_i 扔进一个长度为 2n 的数列 c 中并从大到小排序，每次选出一个 1 类数和 2 类数进行匹配，贡献乘上较小的数的值，将问题转化为求所有匹配方案的贡献之和。

设 f_{i,j} 表示考虑到数列 c 的第 i 项，此时一共匹配了 j 对数的方案的贡献的和。转移时，首先根据 i,j 和前缀和数组，计算出未匹配的 1 类数数量 x 和未匹配的 2 类数数量 y，再根据 c_{i+1} 的类型分别处理：

• 若 c_{i+1} 为 1 类数：
  • 若 y>0：对 c_{i+1} 进行匹配，f_{i+1,j+1} \leftarrow f_{i+1,j+1}+y\times c_{i+1} \times f_{i,j}；
  • 不对 c_{i+1} 进行匹配，f_{i+1,j} \leftarrow f_{i+1,j}+f_{i,j}。
• 若 c_{i+1} 为 2 类数：
  • 若 x>0：对 c_{i+1} 进行匹配，f_{i+1,j+1} \leftarrow f_{i+1,j+1}+x\times c_{i+1} \times f_{i,j}；
  • 不对 c_{i+1} 进行匹配，f_{i+1,j} \leftarrow f_{i+1,j}+f_{i,j}。

初始化 f_{0,0}=0，答案即为 f_{2n,n}。

时间复杂度 \mathcal O(n^2)。

:::

:::success[代码]

const int N=5005,mod=998244353;
int n,f[N<<1][N],s[N<<1][3];
pii p[N<<1];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i].fi,p[i].se=1;
    for(int i=1;i<=n;i++) cin>>p[n+i].fi,p[n+i].se=2;
    sort(p+1,p+n+n+1),reverse(p+1,p+n+n+1);
    for(int i=1;i<=n+n;i++) for(int k=1;k<=2;k++) s[i][k]=s[i-1][k]+(p[i].se==k);
    f[0][0]=1;
    for(int i=0;i<n+n;i++){
        for(int j=0;j<=min(s[i][1],s[i][2]);j++){
            int x=s[i][1]-j,y=s[i][2]-j;
            if(p[i+1].se==1){
                if(y>0) add(f[i+1][j+1],1ll*y*p[i+1].fi%mod*f[i][j]%mod);
                add(f[i+1][j],f[i][j]);
            }
            else{
                if(x>0) add(f[i+1][j+1],1ll*x*p[i+1].fi%mod*f[i][j]%mod);
                add(f[i+1][j],f[i][j]);
            }
        }
    }
    int fac=1;
    for(int i=1;i<=n;i++) fac=1ll*fac*i%mod;
    cout<<1ll*ksm(fac,mod-2)*f[n+n][n]%mod<<endl;
}

:::

ARC207A Affinity for Artifacts

:::info[题解]

设总成本为 w，第 i 个灯是第 p_i 个被点亮的。考虑每个灯节约了多少成本，则显然有：

考虑把 a_i 看作 1 类数，p_i-1 看作 2 类数，将所有 a_i 和所有 p_i-1 扔进一个长度为 2n 的数列 c 中并从大到小排序，每次选出一个 1 类数和 2 类数进行匹配，贡献为较小的数的值。

设 f_{i,j,k} 表示考虑到数列 c 的第 i 项，此时一共匹配了 j 对数，总贡献为 k 的方案数。转移时，首先根据 i,j 和前缀和数组，计算出未匹配的 1 类数数量 x 和未匹配的 2 类数数量 y，再根据 c_{i+1} 的类型分别处理：

• 若 c_{i+1} 为 1 类数：
  • 若 y>0：对 c_{i+1} 进行匹配，f_{i+1,j+1,k+c_{i+1}} \leftarrow f_{i+1,j+1,k+c_{i+1}}+y \times f_{i,j,k}；
  • 不对 c_{i+1} 进行匹配，f_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k}。
• 若 c_{i+1} 为 2 类数：
  • 若 x>0：对 c_{i+1} 进行匹配，f_{i+1,j+1,k+c_{i+1}} \leftarrow f_{i+1,j+1,k+c_{i+1}}+x \times f_{i,j,k}；
  • 不对 c_{i+1} 进行匹配，f_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k}。

初始化 f_{0,0,0}=1。设 v=\left(\sum\limits_{i=1}^n a_i\right)-x，特判一下 v \lt 0 和 v \gt \frac {n(n-1)}2 的情况，答案即为 \sum\limits_{i=v}^{\frac{n(n-1)}{2}} f_{2n,n,i}。

时间复杂度 \mathcal O(n^4)。

:::

:::success[代码]

const int N=105,mod=998244353;
int n,x,a[N],s[N<<1][3],f[N<<1][N][N*(N-1)/2];
ll sum,v;
pii p[N<<1];
int get(int i,int j){
    int a=s[i][1],b=s[i][2];
    return b-a+j;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    v=sum-x;
    if(v<0) v=0;
    if(v>n*(n-1)/2) v=n*(n-1)/2+1;
    for(int i=1;i<=n;i++) p[i]={a[i],1},p[n+i]={i-1,2};
    sort(p+1,p+n+n+1),reverse(p+1,p+n+n+1);
    for(int i=1;i<=n+n;i++) for(int j=1;j<=2;j++) s[i][j]=s[i-1][j]+(p[i].se==j);
    f[0][0][0]=1;
    for(int i=0;i<n+n;i++){
        for(int j=0;j<=min(s[i][1],s[i][2]);j++){
            int x=s[i][1]-j,y=s[i][2]-j;
            for(int s=0;s<=n*(n-1)/2;s++){
                if(p[i+1].se==1){
                    if(y!=0) add(f[i+1][j+1][s+p[i+1].fi],1ll*f[i][j][s]*y%mod);
                    add(f[i+1][j][s],f[i][j][s]);
                }
                else{
                    if(x!=0) add(f[i+1][j+1][s+p[i+1].fi],1ll*f[i][j][s]*x%mod);
                    add(f[i+1][j][s],f[i][j][s]);
                }
            }
        }
    }
    int ans=0;
    for(int i=v;i<=n*(n-1)/2;i++) add(ans,f[n+n][n][i]);
    cout<<ans<<endl;
}

:::

ARC150D Removing Gacha

:::info[题解]

显然总期望操作次数等于每个点期望操作次数之和，于是考虑对于每个点 u，计算点 u 被操作次数的期望。

设点 u 的深度为 d_u，那么点 u 是否还需要被操作只和点 u 到根路径上的 d_u 个点的状态有关，所以我们可以只考虑这 d_u 个点。

于是现在问题转化为了，有 d_u 个点，每次随机选择一个点，直到每个点都被选择过为止，求第 d_u 个点被选择次数的期望。

设当前已经选择了 k 个点，那么有 \frac {d_u-k}{d_u} 的概率选择到一个新点，也就是期望 \frac {d_u}{d_u-k} 次选择到一个新点。相加可以得到总的期望选择次数等于 \sum\limits_{k=0}^{d_u-1}\frac {d_u}{d_u-k}=d_u\sum\limits_{k=1}^{d_u}\frac {1}{k}，而每个点被选择到的概率相等，所以第 d_u 个点期望被选择 \sum\limits_{k=1}^{d_u}\frac {1}{k} 次。

将所有点期望操作次数相加，得到答案为 \sum\limits_{u=1}^n \sum\limits_{k=1}^{d_u}\frac {1}{k}。直接计算即可，时间复杂度 \mathcal O(n)。

:::

:::success[代码]

const int N=2e5+5,mod=998244353;
int n,p[N],d[N],ans,fac[N],infac[N],inv[N],pre[N];
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
void solve(){
    cin>>n;
    for(int i=2;i<=n;i++) cin>>p[i];
    fac[0]=infac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>0;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    for(int i=1;i<=n;i++) inv[i]=1ll*fac[i-1]*infac[i]%mod;
    for(int i=1;i<=n;i++) pre[i]=(pre[i-1]+inv[i])%mod;
    for(int i=1;i<=n;i++) d[i]=d[p[i]]+1,ans=(ans+pre[d[i]])%mod;
    cout<<ans<<endl;
}

:::

ABC134F Permutation Oddness

:::info[题解]

绝对值不好处理，因此考虑把 \sum\limits_{i=1}^n |i-p_i| 拆成 \sum\limits_{i=1}^n \max(i,p_i)-\min(i,p_i)。

对于这种经典形式，我们可以从小到大枚举每个值 i，分别选择 x=i 和 p_y=i 作为 \min 还是 \max，并立刻计算其对答案的贡献。

具体地，定义 f_{i,j,w} 表示，考虑到的值为 i，当前有 j 个 x 和 p_y 作为了 \min 且还未被匹配（不用开两维是因为两者的数量一定相等），目前作为 \max 的数的和减去作为 \min 的数的和等于 w 的方案数。初始化 f_{0,0,0}=1，转移时考虑分类讨论：

• - $x$ 和 $p_y$ 匹配：$f_{i,j,w}\leftarrow f_{i,j,w}+f_{i-1,j,w}$； - $x$ 不和 $p_y$ 匹配：$f_{i,j,w}\leftarrow f_{i,j,w}+f_{i-1,j,w} \times j \times 2$。

答案即为 f_{n,0,k}。由于过程中 w 可能会为负数，所以需要给第三维加一个提前量 W=\mathcal O(n^2)。

时间复杂度 \mathcal O(n^4)。

:::

:::success[代码]

const int N=55,K=5200,mod=1e9+7;
int n,k,f[N][N][K+K];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>k;
    f[0][0][K]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            int p=2*(i-1)*(i-1);
            for(int w=K-p;w<=K+p;w++){
                add(f[i][j][w],1ll*f[i-1][j][w]*(2*j+1)%mod);
                add(f[i][j+1][w-i*2],f[i-1][j][w]);
                if(j) add(f[i][j-1][w+i*2],1ll*f[i-1][j][w]*j*j%mod);
            }
        }
    }
    cout<<f[n][0][K+k]<<endl;
}

:::

CF626F Group Projects

:::info[题解]

考虑从小到大枚举每个 a_i，立刻选择其作为一组的 \min 或 \max 或中间的数，并计算其对于答案的贡献。

设 f_{i,j,k} 表示，考虑到第 i 个数，之前有 j 个组还缺 \max，且对答案的总贡献为 k 的方案数。转移时，如果 a_i 作为 \min 则 k \leftarrow k-a_i，如果 a_i 作为 \max 则 k\leftarrow k+a_i，否则 k 不变。不过有一个问题是，在转移过程中 k 的范围是 \mathcal O(\sum a_i) 的，总复杂度 \mathcal O(n^2 \sum a_i)，不足以接受，考虑优化。

注意到本题中 k \lt \sum a_i，因此考虑把代表 \max-\min 的 a_r-a_l 拆成 \sum\limits_{m=l}^{r-1} a_{m+1}-a_m，并在每次转移时立刻对答案做出贡献。

具体地，设 f_{i,j,k} 表示，考虑到第 i 个数，之前有 j 个组还缺 \max，且对答案的总贡献为 k 的方案数。令 a_0=a_1，设 k'=k+j \times (a_i-a_{i-1})，转移考虑分类讨论：

• 如果 a_i 作为 \min，则 f_{i,j+1,k'}\leftarrow f_{i,j+1,k'}+f_{i-1,j,k}；
• 如果 a_i 作为 \max，则 f_{i,j-1,k'}\leftarrow f_{i,j-1,k'}+j\times f_{i-1,j,k}；
• 如果 a_i 既作为 \min 也作为 \max，则 f_{i,j,k'}\leftarrow f_{i,j,k'}+f_{i-1,j,k}；
• 如果 a_i 作为中间的数，则 f_{i,j,k'}\leftarrow f_{i,j,k'}+j\times f_{i-1,j,k}。

答案即为 \sum\limits_{v=0}^k f_{n,0,v}。时间复杂度 \mathcal O(n^2k)。

:::

:::success[代码]

const int N=205,K=1005,mod=1e9+7;
int n,k,a[N],f[N][N][K],ans;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1),a[0]=a[1];
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            for(int x=0;x<=k;x++){
                int xx=x+j*(a[i]-a[i-1]);
                if(xx>k) continue;
                add(f[i][j+1][xx],f[i-1][j][x]);
                if(j>0) add(f[i][j-1][xx],1ll*j*f[i-1][j][x]%mod);
                add(f[i][j][xx],1ll*(j+1)*f[i-1][j][x]%mod);
            }
        }
    }
    for(int x=0;x<=k;x++) add(ans,f[n][0][x]);
    cout<<ans<<endl;
}

:::

CF103202M United in Stormwind

:::info[题解]

设 c_w 表示值为 w 的 01 串的数量，f_S 表示满足 0 \le x \lt y \lt n 且 s_x 和 s_y 恰好在下标 i \in S 的位置不同的 (x,y) 的数量；特殊地，为了方便，令 f_S=0。把 w 和 S 都看成一个二进制数，容易得到转移方程：

于是对 c 做一个异或卷积即可计算出 f。

设 g_S 表示在只保留每个 01 串中下标 i\in S 的位置后满足条件的 (x,y) 的数量，那么每个 f_T 会对所有满足 S \cap T \ne \varnothing 的 g_S 做出贡献，推一下式子可以得到：

计算一下 f 的高维前缀和即可快速得到 g_S。答案即为 \sum\limits_{S \subseteq U}[g_S \ge k]。

:::

:::success[代码]

const int S=1<<20;
int n,m,V,ans;
ll k,c[S],f[S];
void Or(int V,ll *f,int c){
    for(int k=1;k<V;k<<=1){
        for(int i=0;i<V;i++){
            if(i&k) continue;
            if(c==1) f[i|k]+=f[i];
            else f[i|k]-=f[i];
        }
    }
}
void Xor(int V,ll *f,int c){
    for(int k=1;k<V;k<<=1){
        for(int i=0;i<V;i++){
            if(i&k) continue;
            ll x=f[i],y=f[i|k];
            f[i]=x+y,f[i|k]=x-y;
        }
    }
    if(c!=1) for(int i=0;i<V;i++) f[i]/=c;
}
void solve(){
    cin>>n>>m>>k,V=1<<m;
    for(int i=1;i<=n;i++){
        string s;
        int res=0;
        cin>>s;
        for(int j=0,p=1;j<m;j++,p<<=1) if(s[j]=='B') res+=p;
        c[res]++;
    }
    Xor(V,c,1);
    for(int i=0;i<V;i++) f[i]=c[i]*c[i];
    Xor(V,f,V*2),f[0]=0,Or(V,f,1);
    for(int i=1;i<V;i++) if(f[V-1]-f[V-1-i]>=k) ans++;
    cout<<ans<<endl;
}

:::

ARC121E Directed Tree

:::info[题解]

将对排列 a 的计数转化为对其逆排列 b 的计数，那么此时要求结点 b_i 不在结点 i 的子树内。

考虑容斥。设 g_i 表示钦定 i 个结点不合法，且只考虑这 i 个结点的方案数，那么 ans=\sum\limits_{i=0}^n (-1)^i\times g_i\times (n-i)!。

接下来思考如何求 g_i。设 f_{u,i} 表示以 u 为根的子树内，钦定了 i 个结点不合法，且只考虑这 i 个结点的方案数。考虑转移：

• 新加入一个儿子时，因为两个子树的不合法的集合是不交的，所以可以直接合并，转移方程为 f'_{u,i+j}\leftarrow f_{u,i} \times f_{v,j}；
• 加入所有儿子后，枚举点 u 是否合法，得到转移方程为 f'_{u,i+1} \leftarrow f_{u,i} \times (siz_u-1-i)+f_{u,i+1}。

于是 g_i 就等于 f_{1,i}。时间复杂度 \mathcal O(n^2)。

:::

:::success[代码]

const int N=2005,mod=998244353;
int n,p[N],siz[N],f[N][N],tmp[N],fac[N],ans;
vector <int> ve[N];
void add(int &u,int v){
    u+=v;
    if(u>=mod) u-=mod;
}
void dfs(int u){
    f[u][0]=1;
    for(auto v:ve[u]){
        dfs(v);
        for(int i=0;i<=siz[u];i++) tmp[i]=f[u][i],f[u][i]=0;
        for(int i=0;i<=siz[u];i++) for(int j=0;j<=siz[v];j++) add(f[u][i+j],1ll*tmp[i]*f[v][j]%mod);
        siz[u]+=siz[v];
    }
    siz[u]++;
    for(int i=siz[u]-1;i>=0;i--) add(f[u][i+1],1ll*f[u][i]*(siz[u]-i-1)%mod);
}
void solve(){
    cin>>n;
    for(int i=2;i<=n;i++) cin>>p[i],ve[p[i]].pb(i);
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    dfs(1);
    for(int i=0;i<=n;i++){
        if(i&1) add(ans,mod-1ll*f[1][i]*fac[n-i]%mod);
        else add(ans,1ll*f[1][i]*fac[n-i]%mod);
    }
    cout<<ans<<endl;
}

:::

P3349 [ZJOI2016] 小星星

:::info[题解]

考虑在树上做一个 DP：设 f_{u,i,s} 表示，考虑到结点 u，p_u=i 且以 u 为根的子树内使用了 s 二进制下为 1 的数的方案数。初始时 f_{u,i,2^i}=1，转移时枚举儿子结点 v，那么转移方程形如：

注意到，s \land t=0 的限制实际上是没用的，因为只有 \text{popcount}(s) 等于当前考虑的结点数量的状态 s 才会贡献到答案里，是否要求 s \land t=0 不会影响答案，于是我们可以直接把转移方程看作：

这就是或卷积的形式。设 F_{u,i}=\text{FMT}(f_{u,i})，那么有：

直接转移后再把每个 F_{root,i} IFMT 回去即可。

时间复杂度 \mathcal O(2^nn^3)。

:::

:::success[代码]

const int N=17,S=1<<17;
int n,m,V,e[N][N];
ll f[N][N][S],tmp[S],ans;
vector <int> ve[N];
void FWT(int V,ll *f,int c){
    for(int k=1;k<V;k<<=1){
        for(int i=0;i<V;i++){
            if(i&k) continue;
            if(c==1) f[i|k]+=f[i];
            else f[i|k]-=f[i];
        }
    }
}
void dfs(int u,int fa){
    for(int i=0;i<n;i++) for(int k=0;k<V;k++) if(k&(1<<i)) f[u][i][k]=1;
    for(auto v:ve[u]){
        if(v==fa) continue;
        dfs(v,u);
        for(int i=0;i<n;i++){
            for(int k=0;k<V;k++) tmp[k]=0;
            for(int j=0;j<n;j++){
                if(!e[i][j]) continue;
                for(int k=0;k<V;k++) tmp[k]+=f[u][i][k]*f[v][j][k];
            }
            for(int k=0;k<V;k++) f[u][i][k]=tmp[k];
        }
    }
}
void solve(){
    cin>>n>>m,V=1<<n;
    for(int i=1,u,v;i<=m;i++) cin>>u>>v,e[u-1][v-1]=1,e[v-1][u-1]=1;
    for(int i=1,u,v;i<n;i++) cin>>u>>v,ve[u-1].pb(v-1),ve[v-1].pb(u-1);
    dfs(0,0);
    for(int i=0;i<n;i++) FWT(V,f[0][i],0),ans+=f[0][i][V-1];
    cout<<ans;
}

:::

NC21207 msc 的背包

:::info[题解]

对两种物品做背包计数比较困难，因此考虑把两种物品转化为一种物品。

具体地，我们可以枚举不大于 \min(n,k) 的与 k 奇偶性相同的非负整数 i，表示买了奇数次的大小为 1 的物品的数量。对于每个买了奇数次的物品，我们可以忽略掉最后一次购买；这样相当于每个大小为 1 的物品都买了偶数次，可以当作有 n+m 个大小为 2 的物品，背包大小为 k-i。

第一部分选择买了奇数次的大小为 1 的物品的方案数为 {n \choose i}，第二部分插板法的方案数为 {\frac{k-i}{2}+n+m-1 \choose n+m-1}，将每个 i 的方案数相加，可以得到总方案数为：

其中 {n \choose i} 和 {\frac{k-i}{2}+n+m-1 \choose n+m-1} 都可以预处理，时间复杂度 \mathcal O(n+m+\log k)。

:::

:::success[代码]

const int N=2e6+5,mod=998244353;
int n,m,k,kk,fac[N],infac[N],inv[N],ans,pro;
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
int C(int n,int m){
    return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>m>>k,kk=k/2,pro=1,ans=0;
    fac[0]=infac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*(kk-i+n+m)%mod;
    infac[n]=ksm(fac[n],mod-2),inv[n]=1ll*infac[n]*fac[n-1]%mod;
    for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(kk-i-1+n+m)%mod,inv[i]=1ll*infac[i]*fac[i-1]%mod;
    for(int i=1;i<=n+m;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[n+m]=ksm(fac[n+m],mod-2);
    for(int i=n+m-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    for(int i=kk+1;i<kk+n+m;i++) pro=1ll*pro*i%mod;
    for(int i=0;i<=n;i++){
        if(k%2!=i%2||i>k) continue;
        int kk=(k-i)/2;
        add(ans,1ll*C(n,i)*pro%mod*infac[n+m-1]%mod);
        pro=1ll*pro*kk%mod*inv[i/2+1]%mod;
    }
    cout<<ans<<endl;
}

:::

CF2048G Kevin and Matrices

:::info[题解]

先考虑 \min\limits_{1 \le i \le n}\left(\max\limits_{1 \le j \le m} a_{i,j}\right)\lt \max\limits_{1 \le j \le m}\left(\min\limits_{1 \le i \le n} a_{i,j}\right) 的情况。此时需要满足，存在 x 使得存在一行都小于 x，且存在一列都大于等于 x。显然这两个条件无法同时满足，故这种情况不存在。

接下来考虑 \min\limits_{1 \le i \le n}\left(\max\limits_{1 \le j \le m} a_{i,j}\right)= \max\limits_{1 \le j \le m}\left(\min\limits_{1 \le i \le n} a_{i,j}\right) 的情况。设这个值等于 k，那么相当于要求：

• 存在一行的最大值等于 k，且每一行的最大值都大于等于 k；
• 存在一列的最小值等于 k，且每一列的最小值都小于等于 k。

设此时的答案为 ans_k，f(a,b) 表示每一行的最大值都大于等于 a 且每一列的最小值都小于等于 b 的方案数，那么做一个二维差分即可得到：

于是问题转化为了如何求 f(a,b)。

考虑容斥：

• 钦定 i 行的最大值都小于 a；
• 对于每一列：
  • 先不考虑列的限制，方案数为 v^{n-i}(a-1)^i；
  • 再减掉这一列的最小值大于 b 的方案数，于是需要减去 (v-b)^{n-i}(\max(a-b-1,0))^i；
• 由于每一列是等价的，所以其对答案的贡献为：

这里我们认为 0^0=1。预处理组合数后枚举 i 并快速幂计算即可。

时间复杂度 \mathcal O(nv \log m)。

:::

:::success[代码]

const int N=1e6+5,mod=998244353;
int n,m,v,fac[N],infac[N];
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1;
        a=1ll*a*a%mod;
    }
    return res;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
void init(int n){
    fac[0]=infac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>0;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
}
int C(int n,int m){
    return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
int f(int a,int b){
    int res=0;
    for(int i=0;i<=n;i++){
        int val=ad(1ll*ksm(v,n-i)*ksm(a-1,i)%mod,mod-1ll*ksm(v-b,n-i)*ksm(max(a-b-1,0),i)%mod);
        int ans=1ll*C(n,i)*ksm(val,m)%mod;
        if(i&1) add(res,mod-ans);
        else add(res,ans);
    }
    return res;
}
void solve(){
    cin>>n>>m>>v;
    init(n);
    int ans=0;
    for(int k=1;k<=v;k++) add(ans,(0ll+f(k,k)-f(k+1,k)-f(k,k-1)+f(k+1,k-1)+mod+mod)%mod);
    cout<<ans<<endl;
}

:::

P9669 [ICPC 2022 Jinan R] DFS Order 2

:::info[题解]

设 p_u 表示结点 u 的父亲，son_{u} 表示所有结点 u 的儿子组成的集合，f_{u,i} 表示结点 u 位于 dfs 序的第 i 位的方案数，g_{u,i} 表示在只考虑结点 \boldsymbol{p_u} 的儿子的顺序的情况下，结点 u 在 dfs 序中的位置比 p_u 在 dfs 序中的位置大 i 的方案数，则有：

接下来考虑怎么求 g_{u,i}。此时相当于要对集合 S=son_{p_u} \setminus \{u\} 做一个 01 背包。设 m=|S|，siz_u 表示以结点 u 为根的子树大小，h_{S,i,j,k} 表示考虑到 S 中的第 i 个数，目前一共选了 j 个数，选了的数的 siz_u 之和为 k 的方案数，则有：

不过直接计算 h_{S,i,j,k} 的时间复杂度是 \mathcal O(n^4) 的，需要使用回退背包优化。具体地，考虑对每个 S=son_u 计算 h_{S,i,j,k}，在求 g_{v,i} 时把结点 v 的贡献回退掉即可。这样每个结点只会位于最多一个背包中，时间复杂度 \mathcal O(n^3)。

:::

:::success[代码]

const int N=505,mod=998244353;
int n,fac[N],infac[N],p[N],son[N],siz[N],f[N][N],g[N][N],h[N][N];
vector <int> ve[N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
void init(int u){
    siz[u]=1;
    for(auto v:ve[u]) if(v!=p[u]) p[v]=u,init(v),siz[u]+=siz[v],son[u]++;
}
void dfs(int u){
    memset(h,0,sizeof h);
    h[0][0]=1;
    for(auto v:ve[u]){
        if(v==p[u]) continue;
        for(int j=son[u]-1;j>=0;j--) for(int k=siz[u]-siz[v];k>=0;k--) add(h[j+1][k+siz[v]],h[j][k]);
    }
    for(auto v:ve[u]){
        if(v==p[u]) continue;
        for(int j=0;j<=son[u]-1;j++) for(int k=0;k<=siz[u]-siz[v];k++) add(h[j+1][k+siz[v]],mod-h[j][k]);
        for(int k=1;k<=siz[u];k++) for(int j=0;j<son[u];j++) add(g[v][k],1ll*h[j][k-1]*fac[j]%mod*fac[son[u]-1-j]%mod);
        for(int j=son[u]-1;j>=0;j--) for(int k=siz[u]-siz[v];k>=0;k--) add(h[j+1][k+siz[v]],h[j][k]);
        for(int i=1;i<=n;i++) for(int j=1;j<i;j++) add(f[v][i],1ll*f[u][j]*g[v][i-j]%mod*infac[son[u]]%mod);
    }
    for(auto v:ve[u]) if(v!=p[u]) dfs(v);
}
void solve(){
    cin>>n,fac[0]=infac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    for(int i=1,u,v;i<n;i++) cin>>u>>v,ve[u].pb(v),ve[v].pb(u);
    init(1),f[1][1]=1;
    for(int u=1;u<=n;u++) f[1][1]=1ll*f[1][1]*fac[son[u]]%mod;
    dfs(1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cout<<f[i][j]<<' ';
        cout<<endl;
    }
}

:::

CF2150D Attraction Theory

:::info[题解]

首先做一个经典转化：设最终位于位置 i 的人的数量为 c_i，则 \sum\limits_{i=1}^n a_{p_i} 可以转化为 \sum\limits_{i=1}^n a_ic_i。显然数列 p 始终有序，因此不同的数列 p 会生成不同的数列 c，可以考虑对所有可以被生成的数列 c 计算 \sum\limits_{i=1}^n a_ic_i 之和。

接下来考虑刻画什么样的数列 c 是可以被生成的。手玩可以发现，数列 c 中一定存在一个下标区间 [l,r]，满足：

证明考虑归纳：初始时满足条件的下标区间为 [1,n]；设一次操作前满足条件的下标区间为 [l,r]：

• 若在位置 1\sim l-1 内设置景点，则操作后 [l-1,r-1] 仍为满足条件的下标区间，位置 r+1\sim n 同理；
• 若在位置 l 设置景点，则操作后 [l,r-1] 仍为满足条件的下标区间，位置 r 同理；
• 若在位置 l+1\sim r-1 内设置景点，则操作后 [l+1,r-1] 仍为满足要求的下标区间。

显然，所有存在满足要求的下标区间的数列都可以被生成，因此我们只需要对所有存在满足要求的下标区间的数列 c 计算 \sum\limits_{i=1}^n a_ic_i 之和即可。

设 c_i=2f_i+1\ (l \lt i \lt r)，考虑枚举 r-l+1，并枚举 x,y \in \{1,2\} 表示 c_l=2f_l+x 和 c_r=2f_r+y，则 f_l \sim f_r 只有一个和为 \frac{n+l-r-x-y+1}2 的要求。插板法得到将 \frac{n+l-r-x-y+1}2 分成 r-l+1 个非负整数的方案数为：

对于 l \lt i \lt r，因为 f 中所有数的取值是公平的，可以得到 c_i 的期望为 \frac{n-x-y+2}{r-l+1}，所有方案中 c_i 之和为：

而对于 i=l 和 i=r，特殊处理一下 x 或 y 带来的贡献即可。

单个 [l,r] 所带来的贡献可以直接用前缀和计算，又因为 [l,r] 可以从 [1,r-l+1] 一直取到 [n-r+l,n]，所以可以使用前缀和的前缀和来计算 c_i 的和。

注意特殊处理 l=r 的情况。时间复杂度 \mathcal O(n)。

:::

:::success[代码]

const int N=2e5+5,mod=998244353;
int n,a[N],c[N],fac[N],infac[N],inv[N],s[N],ss[N],ans;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
int C(int n,int m){
    return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void solve(){
    cin>>n,ans=0;
    for(int i=0;i<=n+1;i++) a[i]=c[i]=fac[i]=infac[i]=inv[i]=s[i]=ss[i]=0;
    fac[0]=infac[0]=inv[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[n]=ksm(fac[n],mod-2),inv[n]=1ll*infac[n]*fac[n-1]%mod;
    for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod,inv[i]=1ll*infac[i]*fac[i-1]%mod;
    for(int i=1;i<=n;i++) cin>>a[i],add(c[i],n);
    for(int k=2;k<=n;k++){
        for(int x=1;x<=2;x++){
            for(int y=1;y<=2;y++){
                int p=n+k-x-y;
                if(p%2!=0||k+x+y-2>n) continue;
                int v=C(p/2,k-1),w=1ll*v*(n-x-y+2)%mod*inv[k]%mod;
                add(s[1],w),add(s[k+1],mod-w),add(s[n-k+2],mod-w);
                if(x==2) add(ss[1],v),add(ss[n-k+2],mod-v);
                if(y==2) add(ss[k],v);
            }
        }
    }
    for(int i=1;i<=n;i++) add(s[i],s[i-1]),add(ss[i],s[i]),add(ss[i],ss[i-1]),add(c[i],ss[i]),add(ans,1ll*a[i]*c[i]%mod);
    cout<<ans<<endl;
}

:::

P7154 [USACO20DEC] Sleeping Cows P

:::info[题解]

为了区分「等待被匹配」和「没有被匹配」，在本文中，若一个奶牛 / 牛棚没有被匹配，则称它被扔掉了。

首先分析一下极大匹配的性质：

• 如果存在一个奶牛 i 被扔掉了，那么所有满足 s_i \le t_j 的牛棚 j 必须被匹配；
• 如果存在一个牛棚 j 被扔掉了，那么所有满足 s_i \le t_j 的奶牛 i 必须被匹配。

于是考虑把所有 s_i 和 t_j 都扔进数组 a 里，将数组 a 排序（若 s_i=t_j 则 s_i 在前）之后做一个 dp：设 f_{i,j,0/1} 表示考虑到 a_i，在此之前有 j 个奶牛正在等待被匹配，且之前有 / 没有被扔掉的奶牛；注意这 j 个奶牛必须在之后被全部匹配。

对于转移方程，考虑分类讨论：

• 若 a_{i+1} 为奶牛（即 a_{i+1} 属于 s）：
• 若 a_{i+1} 为牛棚（即 a_{i+1} 属于 t）：

答案即为 f_{2n,0,0}+f_{2n,0,1}。时间复杂度 \mathcal O(n^2)。

:::

:::success[代码]

const int N=3005,mod=1e9+7;
int n,m,f[N<<1][N][2];
pii p[N<<1];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n,m=n+n;
    for(int i=1;i<=n;i++) cin>>p[i].fi,p[i].se=0;
    for(int i=1;i<=n;i++) cin>>p[i+n].fi,p[i+n].se=1;
    sort(p+1,p+1+m);
    f[0][0][1]=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<=min(n,i);j++){
            if(p[i+1].se==0){
                add(f[i+1][j+1][0],f[i][j][0]);
                add(f[i+1][j][0],f[i][j][0]);
                add(f[i+1][j+1][1],f[i][j][1]);
                add(f[i+1][j][0],f[i][j][1]);
            }
            else{
                add(f[i+1][j-1][0],1ll*j*f[i][j][0]%mod);
                add(f[i+1][j-1][1],1ll*j*f[i][j][1]%mod);
                add(f[i+1][j][1],f[i][j][1]);
            }
        }
    }
    cout<<(f[m][0][0]+f[m][0][1])%mod<<endl;
}

:::

P14364 [CSP-S 2025] 员工招聘

:::info[题解]

设集合 U=\{i \mid s_i=1\}，考虑钦定一个集合 S \subseteq U，满足：

• 对于所有 i\in S，第 i 个位置的人会被录取，即要求 c_i \gt \sum\limits_{j=1}^{i-1} [j \notin S]；
• 对于所有 i\in U\setminus S，第 i 个位置的人不会被录取，即要求 c_i \le \sum\limits_{j=1}^{i-1} [j \notin S]。

考虑容斥，把第一个条件的形式与第二个条件统一。具体地，钦定一个集合 T \subseteq S，满足：

• 对于所有 i \in T，第 i 个位置的人不会被录取，即要求 c_i \le \sum\limits_{j=1}^{i-1} [j \notin S]；
• 对于所有 i \in S\setminus T，第 i 个位置的人没有要求。

容斥系数为 (-1)^{|T|}。

考虑从前往后 dp。设 f_{i,j,k} 表示，考虑到第 i 个位置，此时一共有 j 个数在 S 中，k 个数在 T 中，且仅考虑 T \cup (U \setminus S) 中的位置填的数的方案数。初始化 f_{0,0,0}=1，设 a_i=\sum\limits_{j=1}^n [c_j \le i]，b_i=\sum\limits_{j=1}^i [s_j=1]，考虑转移：

• 若 s_{i+1}=0，f_{i+1,j,k} \leftarrow f_{i,j,k}；
• 若 s_{i+1}=1：
  • 令 i+1 \in U\setminus S，f_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k} \times (a_{i-j}-k-b_i+j)；
  • 令 i+1 \in S\setminus T，f_{i+1,j+1,k} \leftarrow f_{i+1,j+1,k}+f_{i,j,k}；
  • 令 i+1 \in T，f_{i+1,j+1,k+1} \leftarrow f_{i+1,j+1,k+1}+f_{i,j,k} \times (a_{i-j}-k-b_i+j)。

其中，系数为 a_{i-j}-k-b_i+j 的原因是：当前位置填的数需要小于等于 i-j，且之前已经用了 k+b_i-j 个这样的数。

答案即为 \sum\limits_{j=m}^n \sum\limits_{k=0}^j f_{n,j,k} \times (-1)^k \times (n-b_n+j-k)!，其中 n-b_n+j-k 是满足 i \notin T \cup (U \setminus S) 的 i 的数量，这些位置上的数可以任意排列。

使用滚动数组优化，空间复杂度 \mathcal O(n^2)，时间复杂度 \mathcal O(n^3)。

:::

:::success[代码]

const int N=505,mod=998244353;
int n,m,c[N],s[N],a[N],b[N],f[2][N][N],fac[N],ans;
string str;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>m>>str;
    for(int i=1;i<=n;i++) cin>>c[i],a[c[i]]++;
    for(int i=1;i<=n;i++) s[i]=(str[i-1]=='1'),b[i]=b[i-1]+s[i];
    for(int i=0;i<=n;i++) a[i]+=a[i-1];
    f[0][0][0]=1,fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=0;i<n;i++){
        int t=i&1;
        memset(f[t^1],0,sizeof f[t^1]);
        for(int j=0;j<=b[i];j++){
            for(int k=0;k<=j;k++){
                if(s[i+1]==0) add(f[t^1][j][k],f[t][j][k]);
                else{
                    add(f[t^1][j+1][k],f[t][j][k]);
                    int x=a[i-j]-k-b[i]+j;
                    add(f[t^1][j][k],1ll*f[t][j][k]*x%mod);
                    add(f[t^1][j+1][k+1],1ll*f[t][j][k]*x%mod);
                }
            }
        }
    }
    for(int j=m;j<=b[n];j++){
        for(int k=0;k<=j;k++){
            int x=n-b[n]+j-k;
            if(k&1) add(ans,mod-1ll*f[n&1][j][k]*fac[x]%mod);
            else add(ans,1ll*f[n&1][j][k]*fac[x]%mod);
        }
    }
    cout<<ans<<endl;
}

:::

CF2129D Permutation Blackhole

:::info[题解]

由于对白色区间内的某个点染色后，这个区间会分成两个互不干扰的白色子区间，因此考虑区间 dp：设 f_{l,r,x,y} 表示，位置 l-1 和位置 r+1 已经被染色，只考虑区间 [l,r] 内的贡献和被染色的相对顺序，位置 l-1 的得分增加了 x 且位置 r+1 的得分增加了 y 的方案数。

由于对同一个数造成多次贡献会导致区间长度每次减半，所以一个数的得分上限是 \mathcal O(\log n) 级别的。于是我们可以知道，只有数组 f 的前两维是 \mathcal O(n) 的，而后两维都是 \mathcal O(\log n) 的。

设 w_{l,r,k} 表示对白色区间 [l,r] 中的位置 k 染色所造成贡献的位置，那么有：

• 若 r=n，则 w_{l,r,k}=l-1；
• 否则，若 l=1，则 w_{l,r,k}=r+1；
• 否则，若 2k\le l+r，则 w_{l,r,k}=l-1。
• 否则，w_{l,r,k}=r+1。

转移考虑枚举区间 [l,r] 内第一个被染色的位置 k，分类讨论：

• 若 s_k=-1，则 f_{l,r,x,y}\leftarrow f_{l,r,x,y}+f_{l,k-1,x-[w_{l,r,k}=l-1],y'} \times f_{k+1,r,x',y-[w_{l,r,k}=r+1]} \times {r-l \choose k-l}；
• 若 s_k\ne-1，则 f_{l,r,x,y}\leftarrow f_{l,r,x,y}+f_{l,k-1,x-[w_{l,r,k}=l-1],v} \times f_{k+1,r,s_k-v,y-[w_{l,r,k}=r+1]} \times {r-l \choose k-l}。

其中，s_k\ne-1 的情况可以直接枚举 v，而 s_k=-1 的情况可以先计算 \sum_{y'} f_{l,k-1,x-[w_{l,r,k}=l-1],y'} 和 \sum_{x'} f_{k+1,r,x',y-[w_{l,r,k}=r+1]} 再相乘，做到每次转移 \mathcal O(n \log n)。

对于所有满足 s_i\le 0 的 i，初始化 f_{i,i,[w_{i,i,i}=i-1],[w_{i,i,i}=i+1]}\leftarrow 1，并对于所有不大于 n 的非负整数 i，初始化 f_{i+1,i,0,0}\leftarrow 1，那么答案即为 f_{1,n,1,0}。

时间复杂度 \mathcal O(n^3 \log^3 n)。

:::

:::success[代码]

const int N=105,L=8,mod=998244353;
int n,s[N],fac[N],infac[N],f[N][N][L][L];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
int choose(int n,int m){
    return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
int w(int l,int r,int k){
    if(r==n) return l-1;
    else if(l==1) return r+1;
    else if(k+k<=l+r) return l-1;
    else return r+1;
}
void solve(){
    cin>>n;
    fac[0]=infac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) for(int x=0;x<L;x++) for(int y=0;y<L;y++) f[i][j][x][y]=0;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) if(s[i]>L+L-2) return cout<<0<<endl,void();
    for(int i=1;i<=n;i++) if(s[i]<=0) f[i][i][w(i,i,i)==i-1][w(i,i,i)==i+1]=1;
    for(int i=0;i<=n;i++) f[i+1][i][0][0]=1;
    for(int len=2;len<=n;len++){
        for(int l=1,r=len;r<=n;l++,r++){
            for(int x=0;x<L;x++){
                for(int y=0;y<L;y++){
                    for(int k=l;k<=r;k++){
                        if(s[k]==-1){
                            int sum1=0,sum2=0;
                            for(int b=0;b<L;b++) add(sum1,f[l][k-1][x-(w(l,r,k)==l-1)][b]);
                            for(int a=0;a<L;a++) add(sum2,f[k+1][r][a][y-(w(l,r,k)==r+1)]);
                            add(f[l][r][x][y],1ll*sum1*sum2%mod*choose(r-l,k-l)%mod);
                        }
                        else{
                            for(int v=0;v<L;v++){
                                if(s[k]-v>=L||s[k]-v<0) continue;
                                int val1=f[l][k-1][x-(w(l,r,k)==l-1)][v],val2=f[k+1][r][s[k]-v][y-(w(l,r,k)==r+1)];
                                add(f[l][r][x][y],1ll*val1*val2%mod*choose(r-l,k-l)%mod);
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<f[1][n][1][0]<<endl;
}

:::

P14636 [NOIP2025] 清仓甩卖

:::info[题解]

合法的方案数并不好求，因此考虑正难则反，计算不合法的方案数。

首先尝试刻画一下不合法的条件。显然，如果小 R 购买的糖果是按照性价比排序后的一段前缀，则他买到的糖果一定是最优的；因此，我们只需要考虑中间有一些糖果因为买不起而没有买的情况。设：

• 小 R 在只剩下恰好一元钱前，购买的最后一颗满足 w_i=1 的糖果为 y（其性价比为 a_y）；
• 小 R 在只剩下恰好一元钱后，遇到的第一颗满足 w_i=2 的糖果的编号为 x（其性价比为 \dfrac {a_x} 2）；
• 小 R 在只剩下恰好一元钱后，遇到的第一颗满足 w_i=1 的糖果的编号为 z（其性价比为 a_z）；特殊地，若不存在糖果 z，则认为 z=n+1，其原价 a_z 等于 0；

则小 R 会先购买糖果 y，再购买若干满足 w_i=2 的糖果，并在只剩下恰好一元钱时遇到糖果 x；由于小 R 买不起糖果 x，他只能被迫购买糖果 z。
显然，当 a_x \gt a_y+a_z 时，购买糖果 x 是比购买糖果 y 和糖果 z 更优的，这种定价方案并不能使小 R 买到的糖果的原价总和最大。于是，我们只需要计算满足 a_x \gt a_y+a_z 的方案数即可。

我们将所有糖果按照原价从大到小排序，并将此时的下标作为糖果的编号。考虑枚举 x 和 y（a_x \gt a_y \gt \dfrac{a_x}2），设 u 为最大的满足 a_u \gt \dfrac {a_x} 2 的正整数，v 为最大的满足 a_v \ge a_x-a_y 的正整数，则有下面的要求：

• 对于 i\in [1,x-1]，w_i 可以等于 1 或 2；
• 对于 i=x，w_i 需要等于 2；
• 对于 i\in [x+1,y-1]，w_i 可以等于 1 或 2（若 w_i=1 则它会被放在 x 前面，若 w_i=2 则它会被放在 x 后面）；
• 对于 i=y，w_i 需要等于 1；
• 对于 i\in [y+1,u]，w_i 需要等于 2，因为如果 w_i=1 的话糖果 y 就不是剩下恰好一元钱前购买的最后一颗糖果了；
• 对于 i\in [u+1,v]，w_i 需要等于 2，因为如果 w_i=1 的话糖果 z 就不满足 a_x \gt a_y+a_z 了；
• 对于 i\in [v+1,n]，w_i 可以等于 1 或 2，因为它们都可以作为糖果 z。

同时，设 [1,x-1] 中满足 w_i=2 的 i 有 f 个，[x+1,y-1] 中满足 w_i=1 的 i 有 g 个，为了使遇到糖果 x 时剩下恰好一元钱，需要满足 x-1+f+g+1=m-1（加 1 是因为还要买糖果 y）。

对于 x 前面的糖果，相当于要从 y-2 颗糖果里选 m-x-1 颗，让它们的贡献加 1，一共有 {y-2} \choose {m-x-1} 种方案；对于 x 后面的糖果，[v+1,n] 中的每颗糖果都有两种方案，方案数为 2^{n-v}；将两部分相乘，可以得到此时的方案数为 {{y-2} \choose {m-x-1}} \cdot 2^{n-v}。注意跳过 y-2 \lt m-x-1 的情况。

于是我们只需要枚举 x 和 y，利用双指针求出 v 的值，计算出方案数并相加即可。

时间复杂度 \mathcal O(\sum n^2)。

:::

:::success[代码]

const int N=5005,mod=998244353;
int n,m,fac[N],infac[N],pw[N],ans;
ll a[N];
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return res;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int C(int n,int m){
    return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void init(){
    fac[0]=infac[0]=pw[0]=1;
    for(int i=1;i<N;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[N-1]=ksm(fac[N-1],mod-2);
    for(int i=N-2;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    for(int i=1;i<N;i++) pw[i]=2*pw[i-1]%mod;
}
void solve(){
    cin>>n>>m,ans=0,a[n+1]=0;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]=a[i]*2;
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    for(int x=1;x<min(m,n);x++){
        int y=x;
        while(y<n&&a[x]/2<a[y+1]) y++;
        int v=y;
        while(v<n&&a[x]-a[y]<=a[v+1]) v++;
        for(;a[y]<a[x];y--){
            while(v<n&&a[x]-a[y]<=a[v+1]) v++;
            int f=y-2,g=m-x-1;
            if(f<g) continue;
            add(ans,1ll*C(f,g)*pw[n-v]%mod);
        }
    }
    cout<<(pw[n]+mod-ans)%mod<<endl;
}

:::

ARC165E Random Isolation

:::info[题解]

由于每个点最多只会被删除一次，且每个连通块不会增大，所以可以将题意转化为：随机一个排列 p，从 1 到 n 依次考虑每个点 p_i，如果点 p_i 所处的连通块大小大于 k 则删除点 p_i，否则不进行操作，求期望删除次数。

设 P(G) 表示原树的子图 G 作为一个完整的连通块的出现概率。如果图 G 包含大于 k 个点，那么当图 G 作为一个完整的连通块出现时，一定会进行恰好一次删除操作。所以，期望删除次数就等于每个包含大于 k 个点的子图 G 作为一个完整的连通块的出现概率之和，即 \sum\limits_{|G|>k} P(G)。

接下来考虑怎么计算 P(G)。设图 G 包含 a 个点，原树中有 b 个点与图 G 中的点相连，那么要求只有这 b 个点在排列中的顺序均在这 a 个点前，所以 P(G) 等于 \dfrac{a!b!}{(a+b)!}。

于是可以进行树形 dp：设 f_{u,i,j} 表示，满足图 G 中深度最小的点为 u，包含 i 个点，以 u 为根的子树中有 j 个点与图 G 中的点相连的原树的子图 G 的数量。直接从儿子处转移即可。

时间复杂度 \mathcal O(n^4)。

:::

:::success[代码]

const int N=105,mod=998244353;
int n,k,siz[N],fac[N],infac[N],f[N][N][N],g[N][N],ans;
vector <int> ve[N];
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1;
        a=1ll*a*a%mod;
    }
    return res;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
void dfs(int u,int fa){
    f[u][1][0]=1,siz[u]=1;
    for(auto v:ve[u]){
        if(v==fa) continue;
        dfs(v,u);
        memset(g,0,sizeof g);
        for(int i=0;i<=siz[u];i++) for(int j=0;i+j<=siz[u];j++) for(int p=0;p<=siz[v];p++) for(int q=0;p+q<=siz[v];q++) add(g[i+p][j+q],1ll*f[u][i][j]*f[v][p][q]%mod); 
        siz[u]+=siz[v];
        for(int i=0;i<=siz[u];i++) for(int j=0;j<=siz[u];j++) f[u][i][j]=g[i][j];
    }
    f[u][0][1]=1;
}
void solve(){
    cin>>n>>k;
    for(int i=1,u,v;i<n;i++) cin>>u>>v,ve[u].pb(v),ve[v].pb(u);
    fac[0]=infac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    dfs(1,0);
    for(int u=1;u<=n;u++){
        for(int i=k+1;i<=siz[u];i++){
            for(int j=0;i+j<=siz[u];j++){
                int p=j+(u!=1);
                add(ans,1ll*f[u][i][j]*fac[i]%mod*fac[p]%mod*infac[i+p]%mod);
            }
        }
    }
    cout<<ans<<endl;
}

:::

ARC118E Avoid Permutations

:::info[题解]

直接做有点困难，因此考虑钦定一些尚未确定的障碍点在路径上。设被钦定的障碍点的集合为 T 时，满足条件的路径数为 c(T)，则根据容斥原理可知答案可以表示为 \sum_{T} (-1)^{|T|} c(T)。

设 f_{i,j,k,0/1,0/1} 表示，考虑到第 i 行第 j 列的格子，此时一共钦定了 k 个障碍点，第 i 行没有 / 有障碍点，第 j 列没有 / 有障碍点时的方案数。初始时 f_{0,0,0,1,1}=1。

设 x_i=0/1 表示第 i 行没有 / 有确定的障碍点，y_j=0/1 表示第 j 列没有 / 有确定的障碍点。对于 f_{i,j,k,a,b}，考虑转移：

• 如果 (i,j) 处有障碍点，则不做转移；
• 如果 (i,j) 处没有障碍点：
  • 如果 i \le n：
  • 不在 (i,j) 处钦定障碍点，f_{i+1,j,k,x_{i+1},b} \leftarrow f_{i+1,j,k,x_{i+1},b}+f_{i,j,k,a,b}。
  • 如果 a=0 且 b=0：在 (i,j) 处钦定障碍点，f_{i+1,j,k+1,x_{i+1},1} \leftarrow f_{i+1,j,k+1,x_{i+1},1}+f_{i,j,k,a,b}。
  • 如果 j \le n：
  • 不在 (i,j) 处钦定障碍点，f_{i,j+1,k,a,y_{j+1}} \leftarrow f_{i,j+1,k,a,y_{j+1}}+f_{i,j,k,a,b}。
  • 如果 a=0 且 b=0：在 (i,j) 处钦定障碍点，f_{i,j+1,k+1,1,y_{j+1}} \leftarrow f_{i,j+1,k+1,1,y_{j+1}}+f_{i,j,k,a,b}。

设 m 表示初始时 -1 的数量，答案即为：

其中乘 (m-k)! 是因为没有被钦定的 p 可以在剩余的 (m-k) 个位置任意排列。

时间复杂度 \mathcal O(n^3)。

:::

:::success[代码]

const int N=205,mod=998244353;
int n,m,a[N],fac[N],f[N][N][N][2][2],ans;
bool vis[N][N],x[N],y[N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n,fac[0]=1,f[0][0][0][1][1]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]!=-1) vis[i][a[i]]=1,x[i]=1,y[a[i]]=1;
        else m++;
    }
    for(int i=1;i<=m;i++) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=n+1;j++){
            if(vis[i][j]) continue;
            for(int k=0;k<=min(i,j);k++){
                for(int a=0;a<=1;a++){
                    for(int b=0;b<=1;b++){
                        if(i<=n){
                            add(f[i+1][j][k][x[i+1]][b],f[i][j][k][a][b]);
                            if(!a&&!b) add(f[i+1][j][k+1][x[i+1]][1],f[i][j][k][a][b]);
                        }
                        if(j<=n){
                            add(f[i][j+1][k][a][y[j+1]],f[i][j][k][a][b]);
                            if(!a&&!b) add(f[i][j+1][k+1][1][y[j+1]],f[i][j][k][a][b]);
                        }
                    }
                }
            }
        }
    }
    for(int k=0;k<=m;k++){
        if(k&1) add(ans,mod-1ll*f[n+1][n+1][k][0][0]*fac[m-k]%mod);
        else add(ans,1ll*f[n+1][n+1][k][0][0]*fac[m-k]%mod);
    }
    cout<<ans<<endl;
}

:::

ARC124E Pass to Next

:::info[题解]

设第 i 个人给下一个人传了 c_i 个球，第 i 个人的手中最终有 x_i 个球，则有 x_i=a_i-c_i+c_{i-1}，其中我们认为 c_0=c_n。显然，若 \min\limits_{i=1}^n c_i \gt 0 则可以通过使所有 c_i 都减去 1 的方式保持最终局面不变，而所有 \min\limits_{i=1}^n c_i=0 所形成的最终局面又两两不同，也就是说所有 \min\limits_{i=1}^n c_i=0 的操作序列 c 与最终局面 x 形成了双射。因此，我们考虑转化计数对象：对于所有 c_i \in [0,a_i] 且 \min\limits_{i=1}^n c_i=0 的数列 c，计算 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 的和。

先上一个经典手法，把所有 c_i \in [0,a_i] 且 \min\limits_{i=1}^n c_i=0 的数列 c 的 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和转化为，所有 c_i \in [0,a_i] 的数列 c 的 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和减去所有 c_i \in [1,a_i] 的数列 c 的 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和。

接下来尝试计算所有 c_i \in [0,a_i] 的数列 c 的 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和。考虑其组合意义：对于所有最终局面，从每个人手中选一个球的方案数。

设 f_i 表示考虑完前 i-1 个人且第 i 个人选择了自己的球的方案数，g_i 表示考虑完前 i 个人且第 i 个人选择了上一个人传来的球的方案数。这样设计状态是因为，若第 i 个人选择了自己的球，则其贡献需要在 f_i 向 f_{i+1} 或 g_{i+1} 转移时计算，而若第 i 个人选择了上一个人传来的球，则其贡献需要在 f_{i-1} 或 g_{i-1} 向 g_i 转移时计算。

转移方程为：

由于这是一个环，所以我们还需要枚举一下第 1 个人的状态：先初始化 f_1=1,g_1=0，dp 一轮，给答案加上 f_{n+1}；再初始化 f_1=0,g_1=1，重新 dp 一轮，给答案加上 g_{n+1}。

解决了 c_i \in [0,a_i] 的情况，c_i \in [1,a_i] 的情况是基本相同的，但由于要求每个人都要传递至少一个球，所以转移方程变为了：

其余部分都是一样的，按照上面的方法计算即可。

时间复杂度 \mathcal O(n)。

:::

:::success[代码]

const int N=3e5+5,mod=998244353,inv2=499122177,inv6=166374059;
int n,a[N],f[N],g[N];
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int s1(int x){
    return 1ll*x*(x+1)%mod*inv2%mod;
}
int s2(int x){
    return 1ll*x*(x+1)%mod*(x+x+1)%mod*inv6%mod;
}
int work(int x,int y){
    if(!x) f[1]=1,g[1]=0;
    else f[1]=0,g[1]=1;
    for(int i=1;i<=n;i++){
        f[i+1]=ad(1ll*f[i]*s1(a[i]-y)%mod,1ll*g[i]*(a[i]-y+1)%mod);
        g[i+1]=ad(1ll*f[i]*ad(1ll*a[i]*s1(a[i])%mod,mod-s2(a[i]))%mod,1ll*g[i]*s1(a[i])%mod);
    }
    if(!x) return f[n+1];
    else return g[n+1];
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<ad(ad(work(0,0),work(1,0)),mod-ad(work(0,1),work(1,1)))<<endl;
}

:::

ABC213G Connectivity 2

:::info[题解]

对于图 G=(V,E) 和集合 S \subseteq V，设 f_S 等于 G 的点集为 S 的连通子图的个数，g_S 等于 G 的点集为 S 的子图的个数，那么答案可以表示为：

接下来考虑怎么求 f_S 和 g_S。

证明：显然一个环中上升的边的长度之和与下降的边的长度之和相等，即 \sum\limits_{i=1}^n [p_i \gt i](p_i-i)=\sum\limits_{i=1}^n [p_i \lt i](p_i-i)，而左式与右式之和等于 \sum\limits_{i=1}^n |p_i-i|，因此原式成立。

于是，\sum\limits_{i=1}^n |p_i-i| \le 2m 可以转化为 \sum\limits_{i=1}^n [p_i \gt i](p_i-i) \le m。

性质：排列 p 是通过 n 次交换操作生成的，等价于排列 p 的置换环数量为偶数。

证明：初始时排列 p 的置换环数量的奇偶性与 n 的奇偶性相同，而每次交换操作都会使排列 p 的置换环数量改变 1，因此 n 次交换操作结束后排列 p 的置换环数量为偶数。

于是问题变成了，对 \sum\limits_{i=1}^n [p_i \gt i](p_i-i) \le m 且置换环数量为偶数的排列 p 计数。

考虑把每一对 (i,p_i) 看成从 i 到 p_i 的有向边，从小到大加入每一个 p_w。设 f_{i,j,k,x} 表示，考虑到 p_w=i，目前有 j 条链，总贡献为 k，且置换环数量奇偶性为 x 的方案数。把 (p_i-i) 的贡献拆到每一段 [v,v+1] 上，设 k'=k+j，转移考虑分类讨论：

初始化 f_{0,0,0,0}=1，答案即为 \sum\limits_{k=0}^m f_{n,0,k,0}。

性质：第二维是 \mathcal O(\sqrt m) 的。

证明：如果第二维的值超过了 \sqrt m，就算每次都合并一条链，均摊下来每条链也会造成至少 \sqrt m 的贡献，导致总贡献超过 m。

于是总时间复杂度为 \mathcal O(Tm+nm\sqrt m)。由于空间限制比较紧，需要使用滚动数组优化，并将所有询问离线处理。

:::

:::success[代码]

const int N=505,M=5005,S=72,mod=1e9+7;
int T,n,m,f[2][S][M][2],ans[M];
vector <pii> ve[N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>T;
    for(int i=1;i<=T;i++) cin>>n>>m,ve[n].pb({m,i});
    n=500,m=5000,f[0][0][0][0]=1;
    for(int i=1;i<=n;i++){
        int ii=i&1;
        memset(f[ii],0,sizeof f[ii]);
        for(int j=0;j<min(i,S);j++){
            for(int k=0,kk=j;kk<=m;k++,kk++){
                for(int x=0;x<2;x++){
                    if(!f[ii^1][j][k][x]) continue;
                    if(j+1<S) add(f[ii][j+1][kk][x],f[ii^1][j][k][x]);
                    add(f[ii][j][kk][1-x],f[ii^1][j][k][x]);
                    add(f[ii][j][kk][x],2ll*j*f[ii^1][j][k][x]%mod);
                    if(j) add(f[ii][j-1][kk][x],1ll*j*(j-1)*f[ii^1][j][k][x]%mod);
                    if(j) add(f[ii][j-1][kk][1-x],1ll*j*f[ii^1][j][k][x]%mod);
                }
            }
        }
        for(auto p:ve[i]) for(int k=0;k<=p.fi;k++) add(ans[p.se],f[ii][0][k][0]);
    }
    for(int i=1;i<=T;i++) cout<<ans[i]<<endl;
}

:::

ARC184D Erase Balls 2D

:::info[题解]

将所有球按照 X_i 排序，那么第 i 个球满足 X_i=i。显然选择的球的顺序并不重要，我们只需要明确哪些球被选了。为了方便，我们在 (0,n+1) 和 (n+1,0) 处各添加一个球，并强制选择这两个球。

设选择的球所组成的集合为 S=\{a_1,a_2,\dots,a_m\}\ (0=a_1 \lt a_2 \lt \dots \lt a_m=n+1)，那么显然有 Y_{a_1}\gt Y_{a_2}\gt \dots \gt Y_{a_m}。

设剩余的球所组成的集合为 f(S)：

• 对于 u \in f(S) 且 x \not\in f(S)，设 a_j \lt u \lt a_{j+1}，则显然有 Y_{a_j}\gt Y_u \gt Y_{a_{j+1}}；
• 对于 v \not\in f(S)，设 a_j \lt v \lt a_{j+1}，则显然有 Y_{a_j} \lt Y_v 或 Y_v \lt Y_{a_{j+1}}。

直接对本质不同的 f(S) 进行计数比较困难，因此可以转化计数对象，对选择的球所组成的集合 S 进行计数。

显然不漏容易做到，于是问题变成了如何做到不重。考虑把 f(S) 的贡献转化到满足下列条件的集合 T 上：

• 对于任意 u \not\in T，f\big(\{u\} \cup T\big) \ne f(S)；换句话说，即再选择任意一个球都会导致 f(T) 变化。

显然满足条件的集合 T 是唯一的，因为了第二个条件相当于要求了集合 T 是极大的。

于是现在只需要统计有多少个集合 T 满足上面的条件即可。设 f_i 表示考虑完前 i 个球且选择了第 i 个球的满足条件的集合 T 的数量。转移时枚举 0 \le j \lt i 且 Y_j \gt Y_i 的整数 j，表示上一个选择的球为 j，判断是否能从 j 转移到 i：

• 若存在 j \lt k \lt i，使得对于任意 j \lt u \lt k 都不满足 Y_i \lt Y_u \lt Y_k 且对于任意 k \lt v \lt i 都不满足 Y_k \lt Y_v \lt Y_j（即选择 k 不会导致 f(T) 变化），则不能从 j 转移到 i，否则可以从 j 转移到 i。

于是做一个二维前缀和即可 \mathcal O(n) 检验是否能从 j 转移到 i。总时间复杂度 \mathcal O(n^3)。

:::

:::success[代码]

const int N=305,mod=998244353;
int n,v[N],s[N][N],f[N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
bool check(int ax,int ay,int bx,int by){
    return s[ax][ay]-s[ax][by-1]-s[bx-1][ay]+s[bx-1][by-1]==1;
}
void solve(){
    cin>>n,s[1][n+2]++,s[n+2][1]++,v[1]=n+2,v[n+2]=1;
    for(int i=1,x,y;i<=n;i++) cin>>x>>y,x++,y++,v[x]=y,s[x][y]++;
    for(int x=1;x<=n+2;x++) for(int y=1;y<=n+2;y++) s[x][y]=s[x][y]+s[x-1][y]+s[x][y-1]-s[x-1][y-1];
    f[1]=1;
    for(int i=2;i<=n+2;i++){
        for(int j=i-1;j>=1;j--){
            if(v[j]<v[i]) continue; 
            bool flag=1;
            for(int k=j+1;k<i;k++){
                if(check(k,v[k],j,v[i])&&check(i,v[j],k,v[k])){
                    flag=0;
                    break;
                }
            }
            if(flag) add(f[i],f[j]);
        }
    }
    cout<<f[n+2]<<endl;
}

:::

UOJ310 黎明前的巧克力

:::info[题解]

设选出的两个集合分别为 S_1 和 S_2。

先忽略 S_1 和 S_2 不能均为空集的条件，考虑枚举 T=S_1 \cup S_2，那么 \bigoplus\limits_{i\in T} a_i 需要为 0，且每一个 i \in T 可以任选被分到 S_1 或 S_2 中，于是题意可以转化为：定义一个集合 S 的权值为 2^{|S|}，求所有满足 \bigoplus\limits_{i\in T} a_i=0 的 \{1,2,\dots,n\} 的子集 T 的权值之和。

设 f_i=2x^{a_i}+1，那么我们相当于要对所有 f_i 做一个异或卷积，求 [x^0]\prod\limits_{i=1}^n f_i。

接下来考虑怎么计算 \prod\limits_{i=1}^n\text{FWT}(f_i)。设 F_i=\text{FWT}(f_i)，G= \prod\limits_{i=1}^n F_i，V=2^{20}，由于 f_i 只有两项的值非 0，因此考虑手动把 \text{FWT}(f_i) 拆开：

于是我们发现，F_i 的每一项只会是 -1 或 3。设 x_j=\sum\limits_{i=1}^n [F_{i,j}=-1]，y_j=\sum\limits_{i=1}^n [F_{i,j}=3]，那么 G_j 就等于 (-1)^{x_j}\times3^{y_j}。

接着考虑怎么求 x_j 和 y_j。我们可以计算 H=\sum\limits_{i=1}^n F_i，这样就可以得到 3y_j-x_j=H_j；又因为 x_j+y_j=n，所以 x_j=\dfrac{3n-H_j}{4}，y_j=\dfrac{n+H_j}{4}。其中，根据 FWT 的线性性，H 可以通过计算 h_j=\sum\limits_{i=1}^n f_{i,j} 再计算 \text{FWT}(h) 得到。

对 G 做一个 IFWT 即可得到异或卷积的结果，取 \text{IFWT}(G) 的第 0 项即为答案。注意此时的答案包含了 S_1 和 S_2 均为空集的情况，需要给答案减去 1。

时间复杂度 \mathcal O(n+V\log V)。

:::

:::success[代码]

const int V=1<<20,N=V+5,mod=998244353;
int n,pw1[N],pw3[N],inv,f[N],h[N];
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
void FWT(int V,int *f){
    for(int k=1;k<V;k<<=1){
        for(int i=0;i<V;i++){
            if(i&k) continue;
            int x=f[i],y=f[i^k];
            f[i]=x+y,f[i^k]=x-y;
        }
    }
}
void IFWT(int V,int *f){
    for(int k=1;k<V;k<<=1){
        for(int i=0;i<V;i++){
            if(i&k) continue;
            int x=f[i],y=f[i^k];
            f[i]=ad(x,y),f[i^k]=ad(x,mod-y);
        }
    }
    for(int i=0;i<V;i++) f[i]=1ll*f[i]*inv%mod;
}
void solve(){
    cin>>n,f[0]=n;
    for(int i=1,a;i<=n;i++) cin>>a,f[a]+=2;
    FWT(V,f);
    pw1[0]=pw3[0]=1,inv=ksm(V,mod-2);
    for(int i=1;i<=n;i++) pw1[i]=-pw1[i-1],pw3[i]=3ll*pw3[i-1]%mod;
    for(int i=0;i<V;i++){
        int x=(3*n-f[i])/4,y=(n+f[i])/4;
        h[i]=1ll*(mod+pw1[x])*pw3[y]%mod;
    }
    IFWT(V,h);
    cout<<(h[0]+mod-1)%mod<<endl;
}

:::

P13272 [NOI2025] 序列变换

:::info[题解]

首先考虑第一问怎么做。

我们把对 (i,j) 的操作看成一个从 i 到 j 的箭头，那么每次操作后，箭头处的 a_j 会变成 a_j-a_i，箭尾处的 a_i 会变为 0。由于对 0 操作是没有意义的，所以每对 (i,j) 最多被操作一次。

显然，对于形如 l \rightarrow l+1 \rightarrow \cdots \rightarrow r-1 \rightarrow r 的箭头：

• 其操作顺序一定是从左往右的；
• 操作结束后 a_l \sim a_{r-1} 的值均为 0；
• 操作结束后 a_r 的值等于 [l,r] 中所有与 r 奇偶性相同的 i 所对应的 a_i 的和减去 [l,r] 中所有与 r 奇偶性不同的 i 所对应的 a_i 的和。

形如 l \leftarrow l+1 \leftarrow \cdots \leftarrow r-1 \leftarrow r 的箭头同理。

对于最终序列，如果 (i,i+1) 之间不存在箭头，我们就把它切开，这样切开后的每一段一定形如 l \rightarrow l+1 \rightarrow \cdots \rightarrow k-1 \rightarrow k \leftarrow k+1 \leftarrow \cdots \leftarrow r-1 \leftarrow r，其中：

接下来考虑区间 [l,r] 缩成的 k 有什么限制。令 val_{l,r} 等于 [l,r] 中所有奇数位置的和减去所有偶数位置的和，那么：

• 若 val_{l,r}\gt 0，则 k 需要为奇数；
• 若 val_{l,r}\lt 0，则 k 需要为偶数；
• 若 val_{l,r}=0，则 k 没有奇偶性的限制。

同时，操作过程中还不能出现负数。设以 i 为左端点向右操作最多可以操作到 pl_i，以 i 为右端点向左操作最多可以操作到 pr_i，则 k 需要位于 [pr_r,pl_l] 中。

于是可以设 f_i 表示前 i 个数的贡献的最大值，预处理一下 mb_{l,r,0/1} 表示 [l,r] 中偶数 / 奇数位置的 b_i 的最小值，sb_i 表示 b_1 \sim b_i 的和；初始化 f_0=0，f_i=-\inf，转移时枚举这一段的左端点 j\ (1 \le j \le i)，转移方程为：

答案即为 f_n。

接着考虑第二问怎么做，即如何做到不重。

第一问的做法可能会出现的问题是：对于区间 [l,r]，它可以被拆成 [l,m] 和 [m+1,r]，其中如果 val_{l,m}=0 且 [l,r] 缩成的 k 在 [m+1,r] 中，那么 [l,r] 所形成的最终序列就会和 [l,m] 与 [m+1,r] 拼起来所形成的最终序列一致。这启示我们修改一下 pl_i 和 pr_i 的定义，使其操作到 0 也停下，这样就可以做到不重了。

于是可以设 g_i 表示前 i 个数的贡献的和，预处理一下 sic_{l,r,0/1} 表示 [l,r] 中偶数 / 奇数位置的 {c_i}^{-1} 的和，pc_i 表示 c_1\sim c_i 的乘积，pic_i 表示 {pc_i}^{-1}；初始化 g_0=1，g_i=0，转移时枚举这一段的左端点 j\ (1 \le j \le i)，转移方程为：

答案即为 g_n。时间复杂度 \mathcal O(n^2)。

:::

:::success[代码]

const int N=5005,inf=1e9,mod=1e9+7;
int n,a[N],b[N],c[N],ic[N],pc[N],pic[N],l[N],r[N],tmp[N],mb[N][N][2],sic[N][N][2],g[N];
ll d[N],sb[N],f[N];
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n,pc[0]=pic[0]=1;
    for(int i=1;i<=n;i++) cin>>a[i],d[i]=d[i-1]+(i&1?a[i]:-a[i]);
    for(int i=1;i<=n;i++) cin>>b[i],sb[i]=sb[i-1]+b[i];
    for(int i=1;i<=n;i++) cin>>c[i],ic[i]=ksm(c[i],mod-2),pc[i]=1ll*pc[i-1]*c[i]%mod,pic[i]=1ll*pic[i-1]*ic[i]%mod;
    for(int i=1;i<=n;i++){
        l[i]=r[i]=i;
        for(int j=1;j<=n;j++) tmp[j]=a[j];
        while(l[i]<n&&tmp[l[i]]&&tmp[l[i]]<=tmp[l[i]+1]) tmp[l[i]+1]-=tmp[l[i]],l[i]++;
        for(int j=1;j<=n;j++) tmp[j]=a[j];
        while(r[i]>1&&tmp[r[i]]&&tmp[r[i]]<=tmp[r[i]-1]) tmp[r[i]-1]-=tmp[r[i]],r[i]--;
    }
    for(int i=1;i<=n;i++){
        mb[i][i-1][0]=mb[i][i-1][1]=inf;
        sic[i][i-1][0]=sic[i][i-1][1]=0;
        for(int j=i;j<=n;j++){
            mb[i][j][0]=mb[i][j-1][0];
            mb[i][j][1]=mb[i][j-1][1];
            mb[i][j][j&1]=min(mb[i][j][j&1],b[j]);
            sic[i][j][0]=sic[i][j-1][0];
            sic[i][j][1]=sic[i][j-1][1];
            add(sic[i][j][j&1],ic[j]);
        }
    }
    f[0]=0,g[0]=1;
    for(int i=1;i<=n;i++){
        f[i]=-1ll*inf*inf,g[i]=0;
        for(int j=1;j<=i;j++){
            if(l[j]<r[i]) continue;
            ll val=d[i]-d[j-1];
            int sgn=val>0,x=max(j,r[i]),y=min(i,l[j]);
            if(val==0){
                f[i]=max(f[i],f[j-1]+sb[i]-sb[j-1]);
                add(g[i],1ll*g[j-1]*pc[i]%mod*pic[j-1]%mod);
            }
            else{
                f[i]=max(f[i],f[j-1]+sb[i]-sb[j-1]-mb[x][y][sgn]);
                add(g[i],1ll*g[j-1]*pc[i]%mod*pic[j-1]%mod*sic[x][y][sgn]%mod);
            }
        }
    }
    cout<<f[n]<<' '<<g[n]<<endl;
}

:::

AGC020E Encoding Subsets

:::info[题解]

首先考虑对于一个确定的长度为 n 的 \texttt{01} 串 S，如何求 S 的编码方式数。

设 f_{l,r} 表示 S_l\sim S_r 的编码方式数，g_{l,r} 表示 S_l\sim S_r 缩成一个括号或单个字符的编码方式数。

对于 f_{l,r}，枚举 S_l\sim S_r 编码后第一个字符的来源，得到转移方程：

对于 g_{l,r}，枚举 S_l\sim S_r 的循环节 d，得到转移方程：

其中，len=r-l+1，若 d 为 S_l\sim S_r 的循环节则 w(d,l,r)=1，否则 w(d,l,r)=0。

直接计算即可得到 S 的编码方式数 f_{1,n}。

接下来考虑如何计算长度为 n 的 \texttt{01} 串 S 的所有子集的编码方式数之和。

同理，设 f_S 表示 S 的所有子集的编码方式数之和，g_S 表示 S 的所有子集的缩成一个括号或单个字符的编码方式数之和。

对于 f_S，仍然枚举 S 编码后第一个字符的来源，得到转移方程：

对于 g_S，同样枚举 S 的循环节 d，得到转移方程：

其中 c(S,d) 表示，把 S 分成长度为 d 的 \dfrac{n}{d} 个 \texttt{01} 串，每个 \texttt{01} 串按位与的结果。

记忆化搜索即可。有效状态数并不多，足以通过。

:::

:::success[代码]

const int mod=998244353;
string s;
map <string,int> f,g;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int G(string s);
int F(string s){
    if(s=="") return 1;
    if(f.count(s)) return f[s];
    int n=s.size(),ans=0;
    for(int i=1;i<=n;i++) add(ans,1ll*G(s.substr(0,i))*F(s.substr(i,n-i))%mod);
    return f[s]=ans;
}
int G(string s){
    if(s=="") return 1;
    if(s=="0") return 1;
    if(s=="1") return 2;
    if(g.count(s)) return g[s];
    int n=s.size(),ans=0;
    for(int d=1;d<n;d++){
        if(n%d!=0) continue;
        string t="";
        for(int i=0;i<d;i++){
            bool x=1;
            for(int j=i;j<n;j+=d) x&=(s[j]=='1');
            t+=x+'0';
        }
        add(ans,F(t));
    }
    return g[s]=ans;
}
void solve(){
    cin>>s;
    cout<<F(s)<<endl;
}

:::

P10813 【MX-S2-T4】 换

:::info[题解]

显然，序列 a 是否能通过操作排好序只和每个元素的相对大小有关，因此我们可以先求出将其离散化后的序列 b。对于序列 b，设其值域为 [1,w]，我们考虑序列 b 拆成 w+1 个 01 串 c_0,c_1,\dots,c_w，其中 c_{i,j}=[b_j \ge i]，那么序列 b 能通过操作排好序当且仅当它拆成的 w+1 个 01 串都能通过操作排好序。

我们可以暴力求出每个 01 串是否合法，并把每个序列 b 看成一个 00\cdots0 到 11\cdots1 的长度为 w 的路径，对合法的 01 串做一个 dp 即可得到合法的序列 b 的数量。具体地，设 f_{i,s} 表示，当前是路径上的第 i 个 01 串，其状态表示为 s，此时满足条件的序列 b 的数量。初始化 f_{0,0}，转移方程为：

其中，h_s=1 表示 s 合法，h_s=0 表示 s 不合法。由于每次转移至少要改变一位，所以转移方程中的 t 不能等于 s。可以使用高维前缀和优化，做到时间复杂度 \mathcal O(n^22^n)。

求出 f_{w,2^n-1} 后，只需要考虑如何把序列 b 转回序列 a 了。此时相当于要在 V 个数中选出 w 个数作为离散化前每个元素的值，方案数为 V \choose w，因此答案等于 \sum\limits_{w=1}^n f_{w,2^n-1} \cdot {V \choose w}，暴力计算即可。

时间复杂度 \mathcal O((n^2+m)2^n)。

:::

:::success[代码]

const int N=20,M=505,S=1<<18,mod=1e9+7;
int n,k,V,m,p[M],q[M],h[S],sum[S],f[N][S],ans;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int lowbit(int x){
    return x&-x;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod;
    }
    return res;
}
void solve(){
    cin>>n>>V>>m;
    for(int i=1;i<=m;i++) cin>>p[i]>>q[i],p[i]--,q[i]--;
    k=1<<n;
    for(int s=0;s<k;s++){
        int t=s;
        for(int i=1;i<=m;i++) if(((t>>p[i])&1)>((t>>q[i])&1)) t=t^(1<<p[i])^(1<<q[i]);
        if(lowbit(t)+t==k) h[s]=1;
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int s=0;s<k;s++) sum[s]=f[i-1][s];
        for(int p=1;p<k;p<<=1){
            for(int s=0;s<k;s++){
                if(s&p) continue;
                add(sum[s|p],sum[s]);
            }
        }
        for(int s=0;s<k;s++){
            if(h[s]==0) f[i][s]=0;
            else f[i][s]=ad(sum[s],mod-f[i-1][s]);
        }
    }
    for(int w=1;w<=n;w++){
        int pro=1;
        for(int i=V-w+1;i<=V;i++) pro=1ll*pro*i%mod;
        for(int i=1;i<=w;i++) pro=1ll*pro*ksm(i,mod-2)%mod;
        add(ans,1ll*pro*f[w][k-1]%mod);
    }
    cout<<ans<<endl;
}

:::

ARC160F Count Sorted Arrays

:::info[题解]

考虑把排列 p 拆成 n+1 个 01 串 c_0,c_2,\dots,c_n，其中 c_{i,j}=[p_j\ge i]，那么排列 p 能通过操作排好序当且仅当它拆成的 n+1 个 01 串都能通过操作排好序。

可以时刻维护每个 01 串是否合法，把每个排列 p 看成一个 00\cdots0 到 11\cdots1 的长度为 n 的路径，对合法的 01 串做一个 dp 即可得到合法的排列 p 的数量，时间复杂度 \mathcal O(nm2^n)。

感性理解，其实只有 \mathcal O(n^2) 个操作是有效的，而其他操作都不会影响 01 串的合法性。于是可以时刻维护 f_{i,j} 表示是否存在 01 串 c 满足 c_{\min(i,j)} \gt c_{\max(i,j)}，只有当询问的 f_{a_i,b_i} 为真时才重新 dp 并更新所有的 f_{a_i,j} 和 f_{b_i,j}，否则直接输出上一次询问的结果即可。

时间复杂度 \mathcal O(n^32^n)。

:::

:::success[代码]

const int N=15,W=1<<15;
int n,m,V,f[N][N],g[W],h[W];
ll dp[W],ans=1;
bool get(int s,int x,int y){
    return ((s>>x)&1)>((s>>y)&1);
}
void solve(){
    cin>>n>>m,V=1<<n;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) f[i][j]=1;
    for(int s=0;s<V;s++) g[s]=s;
    for(int i=0;i<=n;i++) h[((1<<i)-1)<<(n-i)]=1;
    for(int c=1;c<=m;c++){
        int x,y;
        cin>>x>>y;
        x=(x+ans)%n,y=(y+ans+ans)%n;
        if(x>y) swap(x,y);
        if(!f[x][y]){
            cout<<ans<<endl;
            continue;
        }
        for(int i=0;i<n;i++) f[x][i]=f[i][x]=f[y][i]=f[i][y]=0;
        for(int s=0;s<V;s++){
            if(get(g[s],x,y)) g[s]^=(1<<x)^(1<<y);
            for(int i=0;i<n;i++){
                if(get(g[s],min(i,x),max(i,x))) f[x][i]=f[i][x]=1;
                if(get(g[s],min(i,y),max(i,y))) f[y][i]=f[i][y]=1;
            }
        }
        for(int s=0;s<V;s++) dp[s]=0;
        dp[0]=1;
        for(int s=1;s<V;s++){
            if(!h[g[s]]) continue;
            for(int i=0;i<n;i++) if(s&(1<<i)) dp[s]+=dp[s^(1<<i)];
        }
        ans=dp[V-1];
        cout<<ans<<endl;
    }
}

:::

CF1603E A Perfect Problem

:::info[题解]

显然，一个序列是否是完美序列与序列中每个元素的顺序无关，因此不妨考虑对一个单调不降的序列 a 发掘性质。

性质 1：单调不降的序列 a 是完美序列，当且仅当其每个前缀都是好序列。

证明：对于序列 a 的子序列 a_{p_1},\dots,a_{p_m}，只要区间 a_{p_1}\sim a_{p_m} 是好的，由于 a_{p_1}a_{p_m}\ge\sum\limits_{i=p_1}^{p_m} a_i \ge \sum\limits_{i=1}^m a_{p_i}，子序列 a_{p_1},\dots,a_{p_m} 就是好的；而对于序列 a 的区间 a_l\sim a_r，只要前缀 a_1\sim a_r 是好的，由于 a_la_r \ge a_1a_r \ge \sum\limits_{i=1}^r a_i \ge \sum\limits_{i=l}^r a_i，区间 a_l\sim a_r 就是好的。

于是，判定一个序列是否是完美序列，只需要检查其排序后每个前缀是否是好序列即可。

不过计算一个单调不降的完美序列能对应多少个未排序的完美序列，还需要知道每个值在序列中的出现次数；因此我们可以从小到大枚举每个值 v 的出现次数，通过 dp 和组合数得到完美序列的数量。

具体地，设 f_{m,i,j,s} 表示，a_1 的值为 m，当前枚举到的值为 i，目前一共确定了 j 个数，确定了的数的和为 s 的方案数，则 f_{m,i,j,s} 有意义当且仅当 im \ge s。转移时枚举 i 的出现次数 k，转移方程为：

直接计算的时间复杂度是 \mathcal O(n^6) 的，不足以通过，考虑优化。

考虑对 a_1a_k \ge \sum\limits_{i=1}^k a_i 做一个变形，将其转化为 a_1(a_k-k) \ge \sum\limits_{i=1}^k (a_i-a_1)。由于 \sum\limits_{i=1}^n (a_i-a_1) \le a_1(a_n-n)\le a_1，所以 \sum\limits_{i=1}^k (a_i-a_1) 是 \mathcal O(n) 的，可以把它记录到状态里。

设 f_{m,i,j,s} 表示，a_1 的值为 m，当前枚举到的值为 i，目前一共确定了 j 个数，确定了的数的 a_k-a_1 的和为 s 的方案数，则 f_{m,i,j,s} 有意义当且仅当 m(i-j) \ge s。转移时枚举 i 的出现次数 k，转移方程为：

同时，因为 s 是 \mathcal O(n) 的，所以枚举 k 的时间复杂度是调和级数的，总时间复杂度为 \mathcal O(n^4 \log n)，不足以通过，还需要再次优化。

性质 2：m \ge n-2\sqrt n。

证明：因为对于任意不大于 n 的正整数 k 都满足 a_k \ge k，所以 m \ge \sum\limits_{i=1}^n (a_i-m) \ge \sum\limits_{i=1}^{n-m} (n-i+2-m) \ge \dfrac{(n-m+1)(n-m)}{2}，即 2m \ge (n-m)^2+(n-m)，显然当 m \lt n-2\sqrt n 时该式不成立。

于是，根据性质 2 可知，枚举 m 的复杂度是 \mathcal O(\sqrt n) 的，dp 过程中枚举 i 的复杂度也是 \mathcal O(\sqrt n) 的，于是总时间复杂度为 \mathcal O(n^3 \log n)，可以通过。

注意特判一些边界情况，例如值为 m 的数必须选至少一个。

:::

:::success[代码]

const int N=205,M=20;
int n,mod,f[N][N][N],C[N][N],ans;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>mod;
    for(int i=0;i<=n+1;i++) C[i][0]=1;
    for(int i=1;i<=n+1;i++) for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    for(int m=max(1,n-M);m<=n+1;m++){
        memset(f,0,sizeof f);
        f[m-1][0][0]=1;
        for(int i=m;i<=n+1;i++) for(int j=(i>m);j<i;j++) for(int s=0;s<=m;s++){
            if(!f[i-1][j][s]) continue;
            for(int k=0,jj=j,ss=s;jj<=i&&ss<=m;k++,jj++,ss+=i-m) if(m*(i-jj)>=ss) add(f[i][jj][ss],1ll*f[i-1][j][s]*C[n-j][k]%mod);
        }
        for(int s=0;s<=m;s++) add(ans,f[n+1][n][s]);
    }
    cout<<ans<<endl;
}

:::

AGC008E Next or Nextnext

:::info[题解]

设从 i 指向 p_i 所形成的图为 G_1，从 i 指向 a_i 所形成的图为 G_2，考虑考查 G_1 和 G_2 之间的关系。

显然 G_1 由若干个环组成，于是考虑 G_1 中的每一个环：

• 若环上的每一个点都满足 a_i=p_i，则 G_2 中有一个一模一样的环；
• 若环上的每一个点都满足 a_i=p_{p_i} 且环长为奇数，则 G_2 中有一个环长相同但不一样的环；
• 若环上的每一个点都满足 a_i=p_{p_i} 且环长为偶数，则 G_2 中有两个环长为该环长度一半的环；
• 若环上既存在满足 a_i=p_i 的点又存在满足 a_i=p_{p_i} 的点，则 G_2 中会存在一棵由一个环和若干条链组成的基环内向树。

接下来考虑 G_2 如何推回 G_1。

先考虑 G_2 中的环。设 G_2 中有 c_i 个长度为 i 的环，枚举要合并的环的数量 2j：

• 若 j \ne 0：
  • 从 cnt_i 个环中选出 2j 个环，方案数为 cnt_i \choose 2j；
  • 从 2j 个环中选出左侧的 j 个环，钦定左侧的环的顺序为 1\sim j，枚举右侧环的顺序，并去掉交换同一行两个环的方案，得到方案数为 \frac{{2j \choose j}j!}{2^j}；
  • 每对环有 i 种合并方式，方案数为 i^j；
• 若 i 为奇数且 i\ne1，则每个不被合并的环也有 2 种方案，方案数为 2^{cnt_i-2j}；

将每个步骤的方案数相乘即可得到这个部分的结果，将每个 j 的结果相加即可得到每种环长的答案。

再考虑 G_2 中的基环内向树。不妨设基环内向树的环上的点依次为 1,2,\dots,m，其中对于每个不大于 n 的正整数 i 都存在一条从 (i \bmod m)+1 指向 i 的边；设挂着链的点依次为 p_1,p_2,\dots,p_k，挂在 p_i 上的链的长度为 l_i，则我们需要将 l_i 插回 p_i 到 p_{(i \bmod k)+1} 之间。设 p_i 到 p_{(i \bmod m)+1} 之间有 e 条边：

• 若 e>l_i，则插回的方案数为 2；
• 若 e=l_i，则插回的方案数为 1；
• 若 e<l_i，则插回的方案数为 0。

将每条链插回的方案数相乘即可得到这部分的结果，答案即为每个环和每棵基环内向树的方案数的乘积。

朴素实现的时间复杂度为 \mathcal O(n \log n)，精细实现可以做到 \mathcal O(n)。

:::

:::success[代码]

const int N=1e5+5,mod=1e9+7;
int n,a[N],c[N],vis[N],ans=1,fac[N<<1],infac[N<<1];
vector <int> ve[N];
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1,a=1ll*a*a%mod; 
    }
    return res;
}
int C(int n,int m){
    return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void dfs(int u,bool f,int len){
    f|=(ve[u].size()!=1);
    vis[u]=1,len++;
    if(vis[a[u]]){
        if(!f) return c[len]++,void();
        vector <int> s,p,l;
        s.pb(u),vis[u]=2;
        int v=a[u];
        while(v!=u) s.pb(v),vis[v]=2,v=a[v];
        int m=s.size();
        for(int i=0;i<m;i++){
            int u=s[i];
            if(ve[u].size()==2){
                if(vis[ve[u][0]]==2) v=ve[u][1];
                else v=ve[u][0];
                int cnt=0;
                while(1){
                    vis[v]=1,cnt++;
                    if(ve[v].size()==2) cout<<0<<endl,exit(0);
                    if(ve[v].size()==0) break;
                    v=ve[v][0];
                }
                p.pb(i),l.pb(cnt);
            }
        }
        int k=p.size();
        for(int i=0;i<k;i++){
            int e;
            if(i==0) e=p[i]+m-p[k-1];
            else e=p[i]-p[i-1];
            if(e>l[i]) add(ans,ans);
            if(e<l[i]) cout<<0<<endl,exit(0);
        }
        return;
    }
    dfs(a[u],f,len);
}
void solve(){
    cin>>n;
    fac[0]=infac[0]=1;
    for(int i=1;i<=n+n;i++) fac[i]=1ll*i*fac[i-1]%mod;
    infac[n+n]=ksm(fac[n+n],mod-2);
    for(int i=n+n-1;i>0;i--) infac[i]=1ll*(i+1)*infac[i+1]%mod;
    for(int i=1;i<=n;i++) cin>>a[i],ve[a[i]].pb(i);
    for(int i=1;i<=n;i++) if(ve[i].size()>2) cout<<0<<endl,exit(0);
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        dfs(i,0,0);
    }
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=0;j+j<=c[i];j++){
            int res=1;
            if(j!=0) res=1ll*C(c[i],j+j)*C(j+j,j)%mod*fac[j]%mod*ksm((mod+1)/2,j)%mod*ksm(i,j)%mod;
            if((i&1)&&i!=1) res=1ll*res*ksm(2,c[i]-j-j)%mod;
            add(sum,res);
        }
        ans=1ll*ans*sum%mod;
    }
    cout<<ans<<endl;
}

:::

AGC027E ABBreviate

:::info[题解]

注意到，如果我们把 \texttt a 看作 1，\texttt b 看作 2，设 f(s) 表示字符串 s 中所有字符所对应的数字之和对 3 取模后的值，那么每次操作不会改变 f(s)。

首先考虑字符串 s 能不能变成单个字符 c（s \ne c）。此时显然需要满足：

只要 s 满足上述两个条件，那么就一定可以通过不断对 s 中相邻的相同字符进行操作的方式使 s 变成 c。

接下来考虑字符串 s 能不能变成字符串 t（s \ne t）。此时显然需要满足：

• 设 |t|=m，则 s 可以被分成 m+1 段子字符串 e_1,e_2,\dots,e_{m+1}，其中前 i 段均满足 f(e_i)=f(t_i)，第 m+1 段满足 f(e_{m+1})=0（e_{m+1} 可以为空串）。

同理，只要 s 满足上述三个条件，那么就一定可以通过相邻的相同字符调整 s 的每一段，使 e_i 变为 t_i 并消去 e_{m+1}。

可以在特判 s 中不存在相邻的相同字符后 dp：设 dp_{i} 表示 s[1,i] 能变成的字符串数量，nxt_{i,x}（1 \le x \le 2）表示最小的大于 i 的下标 j，满足 f\big(s[i,j-1]\big)=x。

初始化 f_1=1 和 nxt_{n+1,1}=nxt_{n+1,2}=n+2，则转移方程为 dp_{nxt_{i,1}} \leftarrow dp_{nxt_{i,1}}+dp_i 和 dp_{nxt_{i,2}} \leftarrow dp_{nxt_{i,2}}+dp_i，答案即为 \sum\limits_{i=2}^{n+1} dp_i \times \Big[f\big(s[i,n]\big)=0\Big]。

由于每个字符串 t 都恰好对 s 所能变成 t 的最短前缀处贡献了 1，所以这样做是不重不漏的。时间复杂度 \mathcal O(n)。

:::

:::success[代码]

const int N=1e5+5,mod=1e9+7;
int n,a[N],nxt[N][3],suf[N],dp[N],ans;
bool flag;
string s;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>s,n=s.size();
    for(int i=1;i<=n;i++) a[i]=s[i-1]=='a'?1:2,flag|=a[i]==a[i-1];
    if(!flag) return cout<<1<<endl,void();
    nxt[n+1][1]=nxt[n+1][2]=n+2,dp[1]=1;
    for(int i=n;i>=1;i--){
        suf[i]=(suf[i+1]+a[i])%3;
        if(a[i]==1) nxt[i][1]=i+1,nxt[i][2]=nxt[i+1][1];
        if(a[i]==2) nxt[i][1]=nxt[i+1][2],nxt[i][2]=i+1;
    }
    for(int i=1;i<=n;i++) add(dp[nxt[i][1]],dp[i]),add(dp[nxt[i][2]],dp[i]);
    for(int i=2;i<=n+1;i++) if(suf[i]==0) add(ans,dp[i]);
    cout<<ans<<endl;
}

:::

AGC020F Arcs on a Circle

:::info[题解]

将所有线段从短到长排序，考虑断环为链，以第 n 条线段即最长的线段的左端点作为起点，将问题转化为：最长的线段的左端点位于位置 0，其余线段的左端点在 [0,c] 上随机，求 [0,c] 都被覆盖的概率。其中，以最长的线段的左端点作为起点是为了防止存在另一条更长的线段 [x,c+y] 覆盖了 [x,c] 和 [0,y]，对 [x,c] 和 [a_n,y] 均造成贡献的情况出现。

虽然每条线段的左端点都是在实数范围内随机的，但我们其实只关心小数部分的相对大小关系，且可以认为小数部分两两不同，因此我们可以考虑直接枚举 1\sim n-1 的排列 p 表示前 n-1 条线段左端点小数部分的相对大小关系。于是我们现在得到了 nc 个整数坐标 0,1,\dots,nc-1，第 i 条线段的左端点只能放在 x \bmod n=p_i 的坐标 x 上，我们需要求出 [0,nc] 都被覆盖的概率。

考虑 dp：设 f_{i,j,S} 表示，当前考虑到坐标 i，前 j 个坐标都被覆盖了，当前使用了的线段的集合为 S 的方案数。设 i\bmod n=p_k，转移时选择使用或不使用第 k 条线段即可。由于总方案数为 c^{n-1}，所以此时覆盖 [0,nc) 的概率等于 \dfrac {f_{nc,nc,2^{n-1}-1}}{c^{n-1}}。又由于每种小数部分的相对大小关系的出现概率相等，所以答案即为每个 p 所对应的 \dfrac {f_{nc,nc,2^{n-1}-1}}{c^{n-1}} 的平均数。

直接计算即可。时间复杂度 \mathcal O(n!n^2c^22^n)。

:::

:::success[代码]

const int N=7,C=51;
int n,c,V,a[N],p[N],rk[N];
ll ans,dp[N*C][N*C][1<<N],cnt;
void solve(){
    cin>>n>>c,V=1<<(n-1);
    for(int i=1;i<=n;i++) cin>>a[i],p[i]=i;
    sort(a+1,a+n+1);
    while(1){
        memset(dp,0,sizeof dp);
        dp[0][a[n]*n][0]=1,cnt++;
        for(int i=1;i<n;i++) rk[p[i]]=i;
        for(int i=0;i<n*c;i++){
            for(int j=i;j<=n*c;j++){
                for(int s=0;s<V;s++){
                    int k=rk[i%n];
                    dp[i+1][j][s]+=dp[i][j][s];
                    if(k!=0&&(!(s&(1<<(k-1))))) dp[i+1][min(max(j,i+a[k]*n),c*n)][s|(1<<(k-1))]+=dp[i][j][s];
                }
            }
        }
        ans+=dp[n*c][n*c][V-1];
        if(!next_permutation(p+1,p+n)) break;
    }
    printf("%.18lf",ans*1.0/cnt/pow(c,n-1));
}

:::

P12558 [UOI 2024] Heroes and Monsters

:::info[题解]

我们把 a 和 b 按照从小到大的顺序排列，考虑刻画判定大小为 m 的集合 S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法的充要条件。为了满足条件，我们可以贪心，让 S 中的元素与 b_1 \sim b_m 配对，同时让不在 S 中的元素与 b_{m+1} \sim b_n 配对。

更具体地，集合 S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法，当且仅当：

• 设在 S 中的第 i 小的元素为 a_x，则有 a_x \gt b_i；
• 设不在 S 中的第 i 小的元素为 a_y，则有 a_y \lt b_{m+i}。

于是，当 m 确定时，我们可以设 dp_{i,j} 表示考虑完 a_1\sim a_i 且此时有 j 个元素被选入 S 中的方案数，枚举下一个元素是否选入 S 即可得到转移方程为：