自动搬运

查看原文

来自洛谷，原作者为

	Wonder_Fish AFO.

搬运于2025-08-24 23:15:55，当前版本为作者最后更新于2025-05-13 10:06:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

学到了一个比较好的做法，遂记录一下。

问题转化

本题要求 $\sum_p \prod_{i=1}^n (\min_{j=1}^m p_{j,i})$，考虑其组合意义：对于每个由 $m$ 个排列组成的排列组 $p$，为每一列 $i$ 分配一个数 $val_i$ 满足 $\forall 1\leq j \leq m,val_i \leq p_{j,i}$，求所有排列组分配 $val$ 的方案数之和。

对 $p$ 计算 $val$ 的方案需要容斥，较为复杂，考虑对每组 $val$，计算其对于多少排列组 $p$ 是合法的。

考虑从小到大枚举 $i$，确定 $val=i$ 的列并填入每个排列值为 $i$ 的位置。注意到排列的 $i$ 只能填入 $val \leq i$ 的列，所以每次先插入列，恰好可以在插入后计算填入排列的 $i$ 的方案，并且这两部分几乎是独立的。

特殊性质 $q=0$

考虑根据上述转化设计 dp，设 $f_{i,j}$ 表示考虑到数值 $i$，已经有 $j$ 列的 $val$ 被确定的所有方案，其填完所有排列 $\leq i$ 的位置的方案数之和。

枚举 $i$，转移分为两部分：

• 枚举 $val=i$ 的列数 $k$，插入前的列数 $j$，然后加入这 $k$ 列。转移需要乘上一个组合数。对于每个 $i$ 这部分复杂度 $O(n^2)$

• 枚举插入完后的列数 $j$，填入所有排列的 $i$。对 $f_{i,j}$ 乘上填 $i$ 的方案数，此时每行剩下的能填的空位数都是 $j-i+1$，所以方案数是 $(j-i+1)^m$。这部分复杂度 $O(n)$

最终答案为 $f_{n,n}$。时间复杂度 $O(n^3)$。

满分做法

确定值的存在，影响了对方案数的计算。对于 $f_{i,j}$，其代表的所有方案的填法数不一定相同了。

下面称存在确定值的行为特殊行，列为特殊列，其余为普通行，列。

注意到 $q\leq 10$，说明存在确定值的行和列都不多，考虑状压。设 $f_{i,j,S}$ 表示考虑到 $i$，已经有 $j$ 个普通列和集合 $S$ 中的特殊列的 $val$ 被确定了，填完所有排列 $\leq i$ 的位置的方案数之和。

转移依然可以分成两部分：

• 插入 $val=i$ 的列，这部分可以继续分为插入普通列和特殊列，并且这两部分相对独立，可以分开考虑。对于普通列，固定 $S$，其余和特殊性质的部分相似，复杂度是 $O(n^22^q)$。对于特殊列，固定 $j$，剩余部分相当于高维前缀和，可以做到 $O(nq2^q)$。

• 计算填入排列的方案数，同样继续分为普通行和特殊行的方案数。普通行每行空位是 $j+popcnt(S)-i+1$，特殊行需要考虑是否有特殊位置的值为 $i$，若有表示已经确定位置，方案数为 1；否则空位数是普通行空位数减去这行值 $>i$ 的特殊位置个数。这部分是 $O(nq2^q)$ 的。

综上，总复杂度是 $O(n^22^q(n+q))$ 的。

Code

代码写的比较丑 QAQ

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define mod 998244353
#define N 60
#define pii pair<int,int>
#define fi first
#define sc second
#define mp make_pair
#define int long long
#define il inline
int n,m,k,h,q,a[N],b[N],cnt[1<<10],f[N][N][1<<10],c[N][N];
int s[N],t[N],v[N],d[N]; pii p[N];
il void madd(int &x,int y){
    x=(x+y>=mod)?(x+y-mod):(x+y); return ;
}
il int qpow(int a,int b){
    int res=1;
    while(b){if(b&1) res=res*a%mod;a=a*a%mod,b>>=1;}
    return res;
}
signed main(){
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=0;i<=n;++i) c[i][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    for(int i=1;i<=q;++i){
        scanf("%lld%lld%lld",&p[i].fi,&p[i].sc,&v[i]);
        a[i]=p[i].sc,b[i]=p[i].fi,++s[v[i]];
    }
    sort(a+1,a+q+1),k=unique(a+1,a+q+1)-a-1;
    for(int i=1;i<=q;++i){
        p[i].sc=lower_bound(a+1,a+k+1,p[i].sc)-a-1;
        t[v[i]]|=(1<<p[i].sc);
    }
    sort(b+1,b+q+1),h=unique(b+1,b+q+1)-b-1;
    for(int i=1;i<=q;++i)
        p[i].fi=lower_bound(b+1,b+h+1,p[i].fi)-b;
    for(int S=1;S<(1<<k);++S) cnt[S]=cnt[S>>1]+(S&1);
    f[0][0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=n-k;++j)
            for(int S=0;S<(1<<k);++S) if(f[i-1][j][S])
                for(int l=0;j+l<=n-k;++l)
                    f[i][j+l][S]=(f[i][j+l][S]+f[i-1][j][S]*c[n-k-j][l])%mod;
        for(int j=0;j<=n-k;++j)
            for(int l=0;l<k;++l)
                for(int S=0;S<(1<<k);++S)
                    if(S&(1<<l)) madd(f[i][j][S],f[i][j][S^(1<<l)]);
        for(int j=0;j<=n-k;++j)
            for(int S=0;S<(1<<k);++S){
                if((S&t[i])!=t[i]||j+cnt[S]<i) f[i][j][S]=0;
                if(!f[i][j][S]) continue;
                memset(d,0,(h+1)<<3);
                for(int l=1;l<=q;++l) if(S&(1<<p[l].sc)){
                    if(v[l]==i) d[p[l].fi]=-inf; if(v[l]>i) ++d[p[l].fi];
                }
                f[i][j][S]=f[i][j][S]*qpow(j+cnt[S]-i+1,m-h)%mod;
                for(int l=1;l<=h;++l) if(d[l]>=0)
                    f[i][j][S]=f[i][j][S]*(j+cnt[S]-i+1-d[l])%mod;
            }
    }
    printf("%lld\n",f[n][n-k][(1<<k)-1]);
    return 0;
}