QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#407044#8552. SticksSampsonYWAC ✓93ms47896kbC++142.0kb2024-05-07 21:39:542024-05-07 21:39:54

Judging History

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

  • [2024-05-07 21:39:54]
  • 评测
  • 测评结果:AC
  • 用时:93ms
  • 内存:47896kb
  • [2024-05-07 21:39:54]
  • 提交

answer

#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 3005
#define P 998244353
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
  int s = 1;
  while(n) {
    if(n & 1) s = 1ll * s * p % P;
    p = 1ll * p * p % P, n >>= 1;
  }
  return s;
}
il void chkmin(int &x, int y) {(x > y) && (x = y);}
int n;
string str[N];
int dp[N][N];
bool F[N]; int C[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  FOR(i, 1, n) cin >> str[i], str[i] = "1" + str[i];
  dp[0][0] = 1;
  FOR(i, 0, n) C[i] = 1;
  FOR(i, 1, n) {
    bool f = 0; int c, s = 0;
    FOR(j, 0, n) {
      if(str[i][j] == '0') f = 1;
      if(str[i][j] == '1') {
        if(f) c = 0; else c = 1;
      }
      if(str[i][j] == '?' && !f) ++c;
      addr(dp[i][j], 1ll * c * dp[i - 1][j] % P);
      if(!f) {
        if(F[j]) addr(dp[i][j], 1ll * C[j] * s % P);
        else addr(dp[i][j], 1ll * (C[j] - 1) * s % P);
      }
      s = add(1ll * s * C[j] % P, dp[i - 1][j]);
      if(str[i][j] == '0') F[j] = 1;
      if(str[i][j] == '1') {
        if(F[j]) C[j] = 0; else C[j] = 1;
      }
      if(str[i][j] == '?' && !F[j]) ++C[j];
    }
  }
  int s = 0;
  FOR(j, 0, n) s = add(1ll * s * C[j] % P, dp[n][j]);
  cout << s;
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
  return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3952kb

input:

2
??
??

output:

14

result:

ok 1 number(s): "14"

Test #2:

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

input:

5
??1??
?1??0
??0??
???1?
??1??

output:

3144

result:

ok 1 number(s): "3144"

Test #3:

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

input:

10
0000000000
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????

output:

361458985

result:

ok 1 number(s): "361458985"

Test #4:

score: 0
Accepted
time: 62ms
memory: 47864kb

input:

3000
??????????????????????????????????????????????????????????0?????????????????????0??????????????????????????????????????????????????????????????????????????????????????0???????????????????????????????????????????0???????????????????????????????????????????????????????????????????????????????????...

output:

56427841

result:

ok 1 number(s): "56427841"

Test #5:

score: 0
Accepted
time: 57ms
memory: 47836kb

input:

3000
????????????????????????????????????????0??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

145247225

result:

ok 1 number(s): "145247225"

Test #6:

score: 0
Accepted
time: 57ms
memory: 47824kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

925248762

result:

ok 1 number(s): "925248762"

Test #7:

score: 0
Accepted
time: 48ms
memory: 47828kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

845505610

result:

ok 1 number(s): "845505610"

Test #8:

score: 0
Accepted
time: 68ms
memory: 47836kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

123028256

result:

ok 1 number(s): "123028256"

Test #9:

score: 0
Accepted
time: 64ms
memory: 47896kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????1???1??????????????????????????????????????????????????????????????????????1????????????????????????????????????????????????????????????????...

output:

242286033

result:

ok 1 number(s): "242286033"

Test #10:

score: 0
Accepted
time: 68ms
memory: 47880kb

input:

3000
??????????????????????????1????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

448817936

result:

ok 1 number(s): "448817936"

Test #11:

score: 0
Accepted
time: 58ms
memory: 47860kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

621258555

result:

ok 1 number(s): "621258555"

Test #12:

score: 0
Accepted
time: 60ms
memory: 47888kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

552098298

result:

ok 1 number(s): "552098298"

Test #13:

score: 0
Accepted
time: 57ms
memory: 47884kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

190431651

result:

ok 1 number(s): "190431651"

Test #14:

score: 0
Accepted
time: 54ms
memory: 47828kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 63ms
memory: 47824kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

641634738

result:

ok 1 number(s): "641634738"

Test #16:

score: 0
Accepted
time: 75ms
memory: 47880kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

434138343

result:

ok 1 number(s): "434138343"

Test #17:

score: 0
Accepted
time: 71ms
memory: 47856kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

70334815

result:

ok 1 number(s): "70334815"

Test #18:

score: 0
Accepted
time: 74ms
memory: 47808kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

26692788

result:

ok 1 number(s): "26692788"

Test #19:

score: 0
Accepted
time: 54ms
memory: 47892kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

513359183

result:

ok 1 number(s): "513359183"

Test #20:

score: 0
Accepted
time: 60ms
memory: 47868kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

144382583

result:

ok 1 number(s): "144382583"

Test #21:

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

input:

1
0

output:

1

result:

ok 1 number(s): "1"

Test #22:

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

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #23:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

2
10
01

output:

0

result:

ok 1 number(s): "0"

Test #24:

score: 0
Accepted
time: 84ms
memory: 47864kb

input:

3000
1???11111??1???1?1?1111?1111??11?11?????11?1?1?1?1?1???111???111???11?1???11?11??1?11???1??111???11??1????1??1?111??1111?1??1?1?1?1111?1??11?111?1?1??11???11?1?1111??11???????1????1???1?1??111?11?1??1111?1111?1????11?11?1??1?1???1????11?1111?1?1?1??1111???1?11?111?1????1?1?11?11???1???????111?1...

output:

354584112

result:

ok 1 number(s): "354584112"

Test #25:

score: 0
Accepted
time: 93ms
memory: 47828kb

input:

3000
111?1111??11??1?1??1???1?????111???1?11111??1?111?1??1?1????11?11111??1??1?11??11????1??11??11?1???1111???1?11?111?11?1???1?11?11?111?11??1???????1?1??11?1111??????1?1??1111????111111111???1?111??1???111???1?11??11?1??1?11??1?1?111?????1??11?1????1???11??1?11?11111?1111??1?1?1?1???1?11111?1?111...

output:

46093564

result:

ok 1 number(s): "46093564"

Test #26:

score: 0
Accepted
time: 73ms
memory: 47864kb

input:

3000
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #27:

score: 0
Accepted
time: 58ms
memory: 47892kb

input:

3000
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Extra Test:

score: 0
Extra Test Passed