求助ABC G优化方法

存下来的有效状态在列数不同时不一样，难道每一列都要开一个数组记录吗，而且这样还要多一个 O(\min\{n,m\}\times 3^{\min\{n,m\}}) 的复杂度。

#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
const int N=205,mod=998244353,C=4783000;
ll n,m,dp[2][C],now,nxt=1,ans;
char ch[N][N],a[N];
ll po[20],p[C],cnt;
inline int get(int x,int y){return x*3%po[m]+y;}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    po[0]=1;
    for(int i=1;i<=17;i++)  po[i]=po[i-1]*3;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)   cin>>ch[i][j];
    }
    if(n>=m){
        int tmp=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)   a[++tmp]=ch[i][j];
        }
    }else{
        int tmp=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++)   a[++tmp]=ch[j][i];
        }
        swap(n,m);
    }
    dp[now][0]=1;
    for(int S=0;S<po[m];S++){
        int tmp=S/3,lst=S%3,flag=2;
        while(tmp)  flag-=(tmp%3==lst),lst=tmp%3,tmp/=3;
        if(flag)
            p[++cnt]=S;
    }
    for(int i=1;i<=n*m;i++){
//      cerr<<i<<": "<<a[i]<<"   ";
        for(int S=1;S<=cnt;S++) dp[nxt][p[S]]=0;
        for(int j=1;j<=cnt;j++){
            int S=p[j];
            if(a[i]!='?'){
                if((((a[i]^48)-1!=S%3)||(i%m==1)||m==1)&&(((a[i]^48)-1!=(S/po[m-1]))||i<=m))    dp[nxt][get(S,(a[i]^48)-1)]=(dp[nxt][get(S,(a[i]^48)-1)]+dp[now][S])%mod;   
            }else{
                for(int j=0;j<3;j++){
                    if(((j!=S%3)||(i%m==1)||m==1)&&((j!=S/po[m-1])||i<=m))  dp[nxt][get(S,j)]=(dp[nxt][get(S,j)]+dp[now][S])%mod;
                }
            }
//          cerr<<dp[now][S]<<" ";
        }
//      for(int S=0;S<po[m];S++)    cerr<<dp[now][S]<<" ";
//      cerr<<"\n";
        swap(now,nxt);
    }
//  for(int S=0;S<po[m];S++)    cerr<<dp[now][S]<<" ";
//  cerr<<"\n";
    for(int S=0;S<po[m];S++)    ans=(ans+dp[now][S])%mod;
    cout<<ans<<"\n";
}