QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94943 | #5576. Advertising ICPC | Nicolas125841 | RE | 3ms | 4016kb | C++14 | 2.6kb | 2023-04-08 14:05:00 | 2023-04-08 14:05:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 98244353;
vector<vector<ll>> dp(6561, vector<ll>(2, 0)), dpn(6561, vector<ll>(2, 0));
char mp[8][8];
char conv(int i){
if(i == 0)
return 'C';
else if(i == 1)
return 'I';
else
return 'P';
}
int main(){
cin.tie(NULL)->sync_with_stdio(false);
int n, m;
char tmp;
cin >> n >> m;
int m_max = pow(3, m+1);
int m_jmp = pow(3, m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> mp[i][j];
for(int i = 0; i < m_max; i++){
int ti = i, iv;
bool good = true;
for(int j = 0; j < m; j++){
iv = ti%3;
if(mp[0][j] != '?' && conv(iv) != mp[0][j])
good = false;
ti /= 3;
}
if(mp[1][0] != '?' && conv(ti) != mp[1][0])
good = false;
if(good)
dp[i][0] = 1;
}
for(int i = 1; i < n; i++){
for(int j = ((i == 1) ? 1 : 0); j < m; j++){
for(int k = 0; k < m_max; k++){
if(mp[i][j] == '?' || mp[i][j] == 'C'){
if(j > 0 && k%3 == 1 && (k/3)%3 == 0 && k/m_jmp == 2){
dpn[k/3][1] += dp[k][0] + dp[k][1];
dpn[k/3][1] %= mod;
}else{
dpn[k/3][0] += dp[k][0];
dpn[k/3][1] += dp[k][1];
dpn[k/3][0] %= mod;
dpn[k/3][1] %= mod;
}
}
if(mp[i][j] == '?' || mp[i][j] == 'I'){
dpn[k/3 + m_jmp][0] += dp[k][0];
dpn[k/3 + m_jmp][1] += dp[k][1];
dpn[k/3 + m_jmp][0] %= mod;
dpn[k/3 + m_jmp][1] %= mod;
}
if(mp[i][j] == '?' || mp[i][j] == 'P'){
dpn[k/3 + 2 * m_jmp][0] += dp[k][0];
dpn[k/3 + 2 * m_jmp][1] += dp[k][1];
dpn[k/3 + 2 * m_jmp][0] %= mod;
dpn[k/3 + 2 * m_jmp][1] %= mod;
}
}
for(int k = 0; k < m_max; k++){
dp[k][0] = dpn[k][0];
dp[k][1] = dpn[k][1];
dpn[k][0] = dpn[k][1] = 0;
}
}
}
ll ans = 0;
for(int i = 0; i < m_max; i++){
ans += dp[i][1];
ans %= mod;
}
cout << ans << "\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
input:
3 3 ??? ?I? ???
output:
243
result:
ok single line: '243'
Test #2:
score: 0
Accepted
time: 3ms
memory: 4016kb
input:
2 2 IC PC
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Runtime Error
input:
8 8 ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????????