QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#751492 | #9625. 魔弹 | LittleXi# | WA | 1ms | 7880kb | C++20 | 2.5kb | 2024-11-15 19:06:07 | 2024-11-15 19:06:09 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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 '