QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#720079#8552. SticksEstelle_NWA 0ms3604kbC++141.5kb2024-11-07 10:33:292024-11-07 10:33:29

Judging History

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

  • [2024-11-07 10:33:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3604kb
  • [2024-11-07 10:33:29]
  • 提交

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'