QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#751492#9625. 魔弹LittleXi#WA 1ms7880kbC++202.5kb2024-11-15 19:06:072024-11-15 19:06:09

Judging History

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

  • [2024-11-15 19:06:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7880kb
  • [2024-11-15 19:06:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
#define MAXN 100100
#define ll long long
ll n, a[MAXN], b[MAXN], inv[MAXN], ans[MAXN], anss, ansss, sum[MAXN], che[MAXN], len[MAXN], dp[MAXN], cntd, cheinv[MAXN];
char s[MAXN];
const ll mod = 998244353;
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i] == 'L')
        {
            sum[i] = sum[i-1] + 1;
        }
        else{
            sum[i] = sum[i-1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i] == 'L') a[i] = a[i-1] + 1;
        else a[i] = 0;
    }
    for(int i=n;i>=1;i--)
    {
        if(s[i] == 'R') b[i] = b[i+1] + 1;
        else b[i] = 0;
    }
    inv[0] = inv[1] = 1;
    che[0] = che[1] = 1;
    cheinv[0] = cheinv[1] = 1;
    for(int i=2;i<=n;i++)
    {
        inv[i] = (mod - mod/i) * inv[mod%i] % mod;
        che[i] = che[i-1] * i % mod;
        cheinv[i] = cheinv[i-1] * inv[i] % mod;
    }
    dp[0] = 0;
    len[0] = 0;
    cntd = 0;
    for(int i=n;i>=1;i--)
    {
        if(s[i] == 'R')
        {
            if(i > 1 && s[i-1] != 'L') continue;
            cntd++;
            len[cntd] = n-i+1;
            dp[cntd] = (len[cntd-1] * dp[cntd-1] % mod * b[i] % mod * inv[len[cntd]-len[cntd-1]] % mod * che[len[cntd]-1] % mod * cheinv[len[cntd-1]] % mod + b[i] * che[len[cntd]-1] % mod) % mod;
            ans[i] = dp[cntd];
            // printf("%d %d\n",i,dp[cntd]);
        }
    }
    cntd = 0;
    for(int i=1;i<=n;i++)
    {
        if(s[i] == 'L')
        {
            if(i < n && s[i+1] != 'R') continue;
            cntd++;
            len[cntd] = i;
            dp[cntd] = (len[cntd-1] * dp[cntd-1] % mod * a[i] % mod * inv[len[cntd]-len[cntd-1]] % mod * che[len[cntd]-1] % mod * cheinv[len[cntd-1]] % mod + a[i] * che[len[cntd]-1] % mod) % mod;
            ans[i] = dp[cntd];
            // printf("%d %d\n",i,dp[cntd]);
        }
    }
    ans[0] = ans[n+1] = 1;
    for(int i=1;i<=n;i++)
    {
        if(s[i] == 'L')
        {
            if(i < n && s[i+1] != 'R')
            {
                printf("0 ");
                continue;
            }
            else printf("%lld ",ans[i] * ans[i+1] % mod * che[n] % mod * cheinv[i] % mod * cheinv[n-i] % mod);
        }
        else{
            if(i > 1 && s[i-1] != 'L') printf("0 ");
            else printf("%lld ",ans[i] * ans[i-1] % mod * che[n] % mod * cheinv[i-1] % mod * cheinv[n-i+1] % mod);
        }
    }
    cout<<endl;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7880kb

input:

2
RL

output:

1 1 

result:

ok single line: '1 1 '

Test #2:

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

input:

4
LLRR

output:

0 24 24 0 

result:

ok single line: '0 24 24 0 '

Test #3:

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

input:

4
RLRL

output:

9 6 6 9 

result:

ok single line: '9 6 6 9 '

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 5968kb

input:

10
LRLRLLRRRR

output:

873600 873600 604800 604800 0 1814400 1814400 0 0 0 

result:

wrong answer 1st lines differ - expected: '1088640 1088640 604800 604800 0 1935360 1935360 0 0 0', found: '873600 873600 604800 604800 0 1814400 1814400 0 0 0 '