QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #306200 | #5519. Count Hamiltonian Cycles | ushg8877 | WA | 24ms | 13288kb | C++14 | 587b | 2024-01-16 15:11:49 | 2024-01-16 15:11:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MOD=998244353;
const int MAXN=2e6+5;
int n;string s;
int t[MAXN];
void solve(){
cin>>n>>s;s=" "+s,n*=2;
for(int i=1;i<=n;i++){
t[i]=t[i-1]+(s[i]=='W'?1:-1);
}
ll ans=1;
for(int i=1;i<=n;i++){
if(t[i]==0) ans=ans*2%MOD;
else if((s[i]=='W')^(t[i]>0)){
ans=max(abs(t[i-1])*(abs(t[i-1])-1),2)%MOD*ans%MOD;
}
}
cout<<ans*(MOD+1)/4%MOD<<endl;
}
int main(){
ios::sync_with_stdio(false);
int _;cin>>_;
while(_--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3912kb
input:
3 2 WWBB 3 WBWBWB 7 WWWWBWBBWWBBBB
output:
1 2 62208
result:
ok 3 number(s): "1 2 62208"
Test #2:
score: 0
Accepted
time: 24ms
memory: 13196kb
input:
1 1000000 BWBWBBBWWWBWBBBWBBWWWBWBBWWBWBWWWBBBBWBBWWBWBBBWBBBWWBWWBBBBWWWWBWBBWWBBWWWWBBBBWWBWWWWBBBWWBWBWWWBWWBWWBWWBWWBWWWWBWBWWWWWWBWWBWWBWBWBWBWWWBWBBBWBBBWWWBBBWBBBWBBWBWWBBBWWBWBWWWBBBBWBBBWWWBWBBBWBBWWBWBWWBBBWWWWBBWBBBWBBBBBBWBWBWBBBWBBBBBWBBBWWBWBWWBBWWWWBBBBBBBBBWBWWBBBWBWWBBBWBBBBWWBWWBWW...
output:
3254448
result:
ok 1 number(s): "3254448"
Test #3:
score: -100
Wrong Answer
time: 24ms
memory: 13288kb
input:
1 1000000 BWBBWBBWWBBBBWWBWWWBWWBWWBBWWWBBBBBWBBBBBWBWBBBBWBBWBWBBWWWWBWWWBBBWWWBBBWWWBBBWWWBWBBBBWWBWBWBBWBWBBBWWWWBWWBWWBWWWBWBWWWWBWWBBWWBWWBBWBBBWBWBBWWBBBWWWWBBWBWBBBWWWWBWWWWWBWBWWBWWBWWBWWWWBBBBWBBWWBBBBBBBBWBBBWBBBWWBWBWWBBWBWWBWWWWBWWBBBWBWWWWWWWWBWBWWBBBWWBWWWBWWWWBWWBBBBWBBBWBBBBWWBBBBBBB...
output:
926326639
result:
wrong answer 1st numbers differ - expected: '427204463', found: '926326639'