专栏文章

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

CCJZJC
P12467题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipcch3z
此快照首次捕获于
2025/12/03 09:41
3 个月前
此快照最后确认于
2025/12/03 09:41
3 个月前
查看原文
可以先看一下这个：https://oi-wiki.org/dp/number/
直接开正解。
我们令 fi,j,k,limf_{i,j,k,lim} 表示当前考虑到 ii 行 jj 列，这 mm 列形成的数是否顶到上界的状态为 kk，当前这一行是否顶到上界的状态为 limlim。
转移见下：
CPP
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;
其中，xx，yy 为考虑完 ii，jj 后的下一个位置。当当前位置为当前行的最后一列时，llim←1llim \leftarrow1，否则 llim←limllim\leftarrow lim，numnum 为当前枚举到的数字，lim1lim1 和 lim2lim2 为当前列，行的数字大小限制。
此时的复杂度可以做到 O(nm2m×Σ)O(nm2^m\times \Sigma)，其中 Σ\Sigma 为数字集合大小。
加上滚动数组优化会得到 8080 分的成绩。
考虑优化，可以发现不同的 numnum 最多只会对应两种下一次要转移的状态，分别是 numnum 没有顶到和顶到上界的情况，可以一次性计算，会省去一个 O(Σ)O(\Sigma) 的复杂度。
这一部分代码如下，其中 maxnmaxn 为上界：
CPP
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(nm2m)O(nm2^m)，空间复杂度为 O(m2m)O(m2^m)，可以通过。
完整代码：
CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...