QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#720079 | #8552. Sticks | Estelle_N | WA | 0ms | 3604kb | C++14 | 1.5kb | 2024-11-07 10:33:29 | 2024-11-07 10:33:29 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 3005;
const int mod = 998244353;
int n, ans, a[N][N], f[N][N], tag[N], val[N];
char S[N];
signed main()
{
scanf("%lld", &n);
for(int i = 1; i <= n; ++ i)
{
scanf("%s", S + 1);
a[i][0] = 1;
for(int j = 1; j <= n; ++ j)
{
if(S[j] != '?')
a[i][j] = S[j] - '0';
else
a[i][j] = 2;
}
}
for(int j = 1; j <= n; ++ j)
val[j] = tag[j] = 1;
f[0][0] = 1;
for(int i = 1; i <= n; ++ i)
{
int flag = 1, lenth = 1, sum = 0;
for(int j = 0; j <= n; ++ j)
{
if(a[i][j] == 0)
flag = 0;
else if(a[i][j] == 1)
lenth = flag;
else if(flag)
++ lenth;
f[i][j] = (f[i][j] + f[i - 1][j] * lenth) % mod;
if(flag)
f[i][j] = (f[i][j] + sum * (val[j] - tag[j])) % mod;
sum = (sum * val[j] + f[i - 1][j]) % mod;
}
for(int j = 1; j <= n; ++ j)
{
if(a[i][j] == 0)
tag[j] = 0;
else if(a[i][j] == 1)
val[j] = tag[j];
else if(tag[j])
++ val[j];
}
}
for(int i = 1; i <= n; ++ i)
ans = (ans * val[i] + f[n][i]) % mod;
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3604kb
input:
2 ?? ??
output:
5
result:
wrong answer 1st numbers differ - expected: '14', found: '5'