2022NAC Advertising ICPC

给出一个 \(n\times m\) 的矩阵，每个格子是 C, I, P, ? 中的一种，问最少有多少个可能的矩阵包含

I C

P C

\(1\leq n,m\leq 8\)

取模 \(998244353\)

从范围很小以及前一行的状态是重要的可以看出是一个状压 dp .

需要注意的点是因为是一个 \(2\times 2\) 的矩阵，所以需要保存前 \(m+1\) 个格子，并且避免重复，需要多花一位 \(0/1\) 表示是否存在过目标小矩阵。

还需要注意的点，列 \(0\) 作为右下角是没办法组成一个合法小矩阵的。

时间复杂度: \(O(nm3^{m+1})\)

空间复杂度: \(O(nm3^{m+1})\)

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m;
char s[10][10];
int Map[70],pw3[10],dp[70][20005][2];
void solv_pw3(){pw3[0]=1;for(int i=1;i<10;i++)pw3[i]=pw3[i-1]*3;
}
bool chk(int state){for(int i=0;i<=m;i++){	if(Map[i]!=-1&&state%3!=Map[i])return false;state/=3;
//		cerr<<i<<endl;} return true;
}
vector<int>get_list(int state){vector<int>result;for(int i=0;i<m+1;i++){result.push_back(state%3);state/=3;}
//    reverse(result.begin(),result.end());return result;
}
int main(){cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>s[i][j];for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(s[i][j]=='I')Map[i*m+j]=0;if(s[i][j]=='C')Map[i*m+j]=1;if(s[i][j]=='P')Map[i*m+j]=2;if(s[i][j]=='?')Map[i*m+j]=-1;}
//    for(int i=0;i<n*m;i++)cerr<<Map[i]<<" ";cerr<<endl; if(n<2||m<2){cout<<0<<endl;return 0;}solv_pw3();
//   cerr<<pw3[m+1]<<endl;
//	chk(5);for(int i=0;i<pw3[m+1];i++)if(chk(i)){
//    	cerr<<i<<endl;dp[1*m][i][0]=1;}for(int i=m;i<n*m-1;i++){for(int state=0;state<pw3[m+1];state++)for(int tp=0;tp<2;tp++){if(dp[i][state][tp]==0)continue;
//            if(tp==1)cerr<<i<<","<<state<<","<<tp<<":"<<dp[i][state][tp]<<endl;vector<int>v=get_list(state);
//			if(tp==1){
//				for(auto elem:v)cerr<<elem<<" ";cerr<<endl; 
//			}
//            cerr<<tmp<<endl;	for(int nxt=0;nxt<3;nxt++)if(Map[i+1]==-1||nxt==Map[i+1]){if(v[0]==0&&v[1]==1&&v[m]==2&&nxt==1&&(i+1)%m!=0){dp[i+1][state/3+nxt*pw3[m]][1]+=dp[i][state][tp];dp[i+1][state/3+nxt*pw3[m]][1]%=mod;}else{dp[i+1][state/3+nxt*pw3[m]][tp]+=dp[i][state][tp];dp[i+1][state/3+nxt*pw3[m]][tp]%=mod;}}}}   int ans=0;for(int state=0;state<pw3[m+1];state++){ans+=dp[n*m-1][state][1];ans%=mod;} cout<<ans<<endl;return 0;
}
/*
2 3
???
???
*/ 
/*
3 3
???
???
???
*/ 
/*
3 2
??
??
??
*/ 
/*
2 4 
????
????
*/ 
/*
3 2
I?
??
??
*/
/*
3 2
I?
I?
??
*/
/*
2 2
I?
I?
*/ 
/*
8 8
????????
????????
????????
????????
????????
????????
????????
????????
*/

时隔接近4年重新写中文blog，果真 oi 还是当作爱好的时候才是最开心的。

上大学真的累死了，每天都活人微死，作业怎么这么多，上课怎么这么快，王者荣耀匹配机制怎么这么烂！！！