QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94865#5576. Advertising ICPCNicolas125841TL 2ms3648kbC++142.5kb2023-04-08 01:28:372023-04-08 01:28:39

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 01:28:39]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3648kb
  • [2023-04-08 01:28:37]
  • 提交

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];

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

/*
3 3
???
?I?
???
*/

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;

        vector<int> j_vals;

        for(int l = 0; l < m; l++){
            j_vals.push_back(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;

                vector<int> j_vals, k_vals;

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

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

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

                    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: 3648kb

input:

3 3
???
?I?
???

output:

243

result:

ok single line: '243'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

2 2
IC
PC

output:

1

result:

ok single line: '1'

Test #3:

score: -100
Time Limit Exceeded

input:

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

output:


result: