QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94927#5576. Advertising ICPCNicolas125841TL 2ms3628kbC++143.4kb2023-04-08 12:44:092023-04-08 12:44:13

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 12:44:13]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3628kb
  • [2023-04-08 12:44:09]
  • 提交

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

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++){
        vector<vector<int>> adds(7, vector<int>());
        ll sum0 = 0, sum1 = 0;

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

            sum0 += dp[i-1][j][0];
            sum1 += dp[i-1][j][1];

            sum0 %= mod;
            sum1 %= mod;

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

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

            if(good){
                for(int l = 0; l < m-1; l++){
                    if(j_vals[l] == 1 && j_vals[l+1] == 0)
                        adds[l].push_back(j);
                }                
            }
        }

        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[i][l] != -1 && mp[i][l] != j_vals[l])
                    good = false;
                                
                tj /= 3;
            }

            unordered_set<int> matches;

            dp[i][j][0] = dp[i][j][1] = 0;

            if(good){
                for(int l = 0; l < m-1; l++){
                    if(j_vals[l] == 2 && j_vals[l+1] == 0){
                        for(int v : adds[l]){
                            matches.insert(v);
                        }
                    }
                }  

                ll tsum0 = sum0;
                ll tsum1 = sum1;

                for(int v : matches){
                    tsum0 -= dp[i-1][v][0];
                    tsum1 -= dp[i-1][v][1];
                    dp[i][j][1] += dp[i-1][v][0] + dp[i-1][v][1];

                    tsum0 %= mod;
                    tsum1 %= mod;

                    if(tsum0 < 0)
                        tsum0 += mod;

                    if(tsum1 < 0)
                        tsum1 += mod;

                    dp[i][j][1] %= mod;
                }   

                dp[i][j][0] += tsum0;
                dp[i][j][1] += tsum1;           
            }
        }
    }

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

input:

3 3
???
?I?
???

output:

243

result:

ok single line: '243'

Test #2:

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

input:

2 2
IC
PC

output:

1

result:

ok single line: '1'

Test #3:

score: -100
Time Limit Exceeded

input:

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

output:


result: