题解：P12467 『FCRT / 1 - 4』Century

CJZJC · 2025-05-11 00:04:05 · 题解

可以先看一下这个：https://oi-wiki.org/dp/number/

直接开正解。

我们令 f_{i,j,k,lim} 表示当前考虑到 i 行 j 列，这 m 列形成的数是否顶到上界的状态为 k，当前这一行是否顶到上界的状态为 lim。

转移见下：

int kk=k,limm=llim&(num==lim2);
if((kk&(1<<(y-1)))&&(num!=lim1)){
    kk^=(1<<(y-1));
}
f[x][y][kk][limm]=(f[x][y][kk][limm]+1ll*maxn*f[i][j][k][lim]%mod)%mod;

其中，x，y 为考虑完 i，j 后的下一个位置。当当前位置为当前行的最后一列时，llim \leftarrow1，否则 llim\leftarrow lim，num 为当前枚举到的数字，lim1 和 lim2 为当前列，行的数字大小限制。

此时的复杂度可以做到 O(nm2^m\times \Sigma)，其中 \Sigma 为数字集合大小。

加上滚动数组优化会得到 80 分的成绩。

考虑优化，可以发现不同的 num 最多只会对应两种下一次要转移的状态，分别是 num 没有顶到和顶到上界的情况，可以一次性计算，会省去一个 O(\Sigma) 的复杂度。

这一部分代码如下，其中 maxn 为上界：

if(maxn!=0){
    int num=0;
    int kk=k,limm=llim&(num==lim2);
    if((kk&(1<<(y-1)))&&(num!=lim1)){
        kk^=(1<<(y-1));
    }
    f[x&1][y][kk][limm]=(f[x&1][y][kk][limm]+1ll*maxn*f[i&1][j][k][lim]%mod)%mod;
}
int num=maxn;
int kk=k,limm=llim&(num==lim2);
if((kk&(1<<(y-1)))&&(num!=lim1)){
    kk^=(1<<(y-1));
}
f[x&1][y][kk][limm]=(f[x&1][y][kk][limm]+f[i&1][j][k][lim])%mod;

此时时间复杂度为 O(nm2^m)，空间复杂度为 O(m2^m)，可以通过。

完整代码：

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define N 19
const int mod=998244353;
int n,m,r[N][N],c[N][N],f[2][N][1<<18][2];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        long long tmp,tot=m;
        cin>>tmp;
        while(tmp){
            r[i][tot--]=tmp%10;
            tmp/=10;
        }
    }
    for(int i=1;i<=m;i++){
        long long tmp,tot=n;
        cin>>tmp;
        while(tmp){
            c[tot--][i]=tmp%10;
            tmp/=10;
        }
    }
    f[0][m][(1<<m)-1][1]=1;
    for(int i=0;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<(1<<m);k++){
                f[1^(i&1)][j][k][0]=0,f[1^(i&1)][j][k][1]=0;
            }
        }
        for(int j=1;j<=m;j++){
            if(i==0&&j!=m){
                continue;
            }
            for(int k=0;k<(1<<m);k++){
                for(int lim=0;lim<=1;lim++){
                    int x=i,y=j+1;
                    if(y==m+1){
                        x++;
                        y=1;
                    }
                    int lim1=(k&(1<<(y-1)))?c[x][y]:9;
                    int lim2=lim?r[x][y]:9;
                    int llim=lim;
                    if(y==1){
                        lim2=r[x][y];
                        llim=1;
                    }
                    int maxn=min(lim1,lim2);
                    if(maxn!=0){
                        int num=0;
                        int kk=k,limm=llim&(num==lim2);
                        if((kk&(1<<(y-1)))&&(num!=lim1)){
                            kk^=(1<<(y-1));
                        }
                        f[x&1][y][kk][limm]=(f[x&1][y][kk][limm]+1ll*maxn*f[i&1][j][k][lim]%mod)%mod;
                    }
                    int num=maxn;
                    int kk=k,limm=llim&(num==lim2);
                    if((kk&(1<<(y-1)))&&(num!=lim1)){
                        kk^=(1<<(y-1));
                    }
                    f[x&1][y][kk][limm]=(f[x&1][y][kk][limm]+f[i&1][j][k][lim])%mod;
                }
            }
        }
    }
    int ans=0;
    for(int k=0;k<(1<<m);k++){
        for(int lim=0;lim<=1;lim++){
            ans=(ans+f[n&1][m][k][lim])%mod;
        }
    }
    cout<<ans;
}