Submission #54678108

---

Source Code Expand

// LUOGU_RID: 162468012
#include <bits/stdc++.h>
using namespace std;
const int P = 998244353; 

inline void add(int &x, int k) { x += k; x -= x >= P ? P : 0; }

int n; 
char a[305]; 
int dp[305][305][305]; // 保留后缀 [i + 1, n]
bool ok[305][305][305]; 

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> a + 1; n = strlen(a + 1); 
    ok[0][0][0] = 1; 
    for (int i = 1; i <= n; ++i) for (int j = n; j >= 0; --j) for (int k = n; k >= 0; --k) {
        ok[i][j][k] |= ok[i - 1][j][k] | ok[i][j + 1][k] | ok[i][j][k + 1]; // 自己干掉自己，放在序列开头
        if (j && i >= 2 && (a[i] == '0' || a[i - 1] == '0')) ok[i][j][k] |= ok[i - 2][j - 1][k]; 
        if (k && i >= 2 && (a[i] == '1' || a[i - 1] == '1')) ok[i][j][k] |= ok[i - 2][j][k - 1]; 
        if (j && a[i] == '0') ok[i][j][k] |= ok[i - 1][j - 1][k + 1]; // 另一种是 ok[i - 1][j][k]
        if (k && a[i] == '1') ok[i][j][k] |= ok[i - 1][j + 1][k - 1]; 
    }
    dp[n][0][0] = 1; 
    for (int i = n; i >= 1; --i) for (int j = 0; j <= n; ++j) for (int k = 0; k <= n; ++k) if (dp[i][j][k]) {
        add(dp[i - 1][j][k], dp[i][j][k]); 
        if (a[i] == '1') add(dp[i][j + 1][k], dp[i][j][k]); 
        else add(dp[i][j][k + 1], dp[i][j][k]); 
    }
    int ans = -1; // 空串不算
    for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k <= n; ++k) add(ans, ok[i][j][k] ? dp[i][j][k] : 0); 
    cout << (ans + P) % P << "\n"; 
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:15:14: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   15 |     cin >> a + 1; n = strlen(a + 1);
      |            ~~^~~

Judge Result