QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94870#5576. Advertising ICPCNicolas125841TL 2ms3596kbC++142.5kb2023-04-08 02:21:342023-04-08 02:21:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-08 02:21:35]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3596kb
  • [2023-04-08 02:21:34]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 98244353;

ll dp[8][6561][2];
int mp[8][8], j_vals[8], k_vals[8];


int conv(char c){
    if(c == 'C')
        return 0;
    else if(c == 'I')
        return 1;
    else if(c == 'P')
        return 2;
    else
        return -1;
}

int main(){
    cin.tie(NULL)->sync_with_stdio(false);

    int n, m;
    char tmp;

    cin >> n >> m;

    int m_max = pow(3, m);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> tmp;

            mp[i][j] = conv(tmp);
        }
    }

    for(int j = 0; j < m_max; j++){
        bool good = true;
        int tj = j;

        for(int l = 0; l < m; l++){
            j_vals[l] = tj%3;

            if(mp[0][l] != -1 && mp[0][l] != j_vals[l])
                good = false;

            tj /= 3;
        }

        if(good)
            dp[0][j][0] = 1;
        else
            dp[0][j][0] = 0;
        
        dp[0][j][1] = 0;
    }
    
    for(int i = 1; i < n; i++){
        for(int j = 0; j < m_max; j++){
            dp[i][j][0] = 0;
            dp[i][j][1] = 0;

            for(int k = 0; k < m_max; k++){
                bool good = true;
                bool match = false;
                int tj = j;
                int tk = k;

                for(int l = 0; l < m; l++){
                    j_vals[l] = tj%3;
                    k_vals[l] = tk%3;

                    if(mp[i][l] != -1 && mp[i][l] != j_vals[l]){
                        good = false;
                        break;
                    }

                    if(l > 0 && j_vals[l] == 0 && j_vals[l-1] == 2 && k_vals[l] == 0 && k_vals[l-1] == 1){
                        match = true;
                        break;
                    }

                    tj /= 3;
                    tk /= 3;
                }

                if(good){
                    if(match){
                        dp[i][j][1] += dp[i-1][k][0] + dp[i-1][k][1];
                    }else{
                        dp[i][j][0] += dp[i-1][k][0];
                        dp[i][j][1] += dp[i-1][k][1];
                    }

                    dp[i][j][0] %= mod;
                    dp[i][j][1] %= mod;
                }else{
                    break;
                }
            }                   
        }
    }

    ll ans = 0;
    
    for(int i = 0; i < m_max; i++){
        ans += dp[n-1][i][1];
        ans %= mod;
    }

    cout << ans << "\n";
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3592kb

input:

3 3
???
?I?
???

output:

243

result:

ok single line: '243'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

2 2
IC
PC

output:

1

result:

ok single line: '1'

Test #3:

score: -100
Time Limit Exceeded

input:

8 8
????????
????????
????????
????????
????????
????????
????????
????????

output:


result: