QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #545629 | #7559. Bocchi the Rock | hank55663 | WA | 4ms | 101776kb | C++14 | 9.7kb | 2024-09-03 15:44:27 | 2024-09-03 15:44:28 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define pdd pair<double,double>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define mp make_pair
#define LL long long
#define ULL unsigned long long
#define sqr(x) ((x)*(x))
#define pi acos(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
using namespace std;
const int mod=998244353;
int P=998244353,root=3,MAXNUM=1<<23;
// Remember coefficient are mod P
/*
p=a*2^n+1 degree(poly) <= 2^n
n 2^n p a root
16 65536 65537 1 3
20 1048576 7340033 7 3
23 998244353 119 3
*/
int bigmod(long long a,int b){
if(b==0)return 1;
return (bigmod((a*a)%P,b/2)*(b%2?a:1ll))%P;
}
int inv(int a,int b){
if(a==1)return 1;
return (((long long)(a-inv(b%a,a))*b+1)/a)%b;
}
std::vector<long long> ps(MAXNUM);
std::vector<int> rev(MAXNUM);
LL f_pow(unsigned int a,LL b){
LL res=1,temp=a;
while(b){
if(b&1)res=res*temp%P;
temp=temp*temp%P;
b>>=1;
}
return res;
}
struct poly{
std::vector<unsigned int> co;
int n;//polynomial degree = n
poly(){n=0;co.clear();}
poly(int d){n=d;co.resize(n+1,0);}
void ntt(int NN){
int r=0,st,N;
unsigned int a,b;
//while((1<<r)<(NN>>1))++r;//inv:r=0
//for(N=2;N<=NN;N<<=1,--r){
for(N=NN;N>1;N>>=1,r++){
for(st=0;st<NN;st+=N){
int i,ss=st+(N>>1);
for(i=(N>>1)-1;i>=0;--i){
a=co[st+i];// b=(ps[i<<r]*co[ss+i])%P;
b=co[ss+i];
co[st+i]=a+b; if(co[st+i]>=P)co[st+i]-=P;
///co[ss+i]=a+P-b; if(co[ss+i]>=P)co[ss+i]-=P;
co[ss+i]=((a+P-b)*ps[i<<r])%P;
}
}
}
}
void ntt_inv(int NN){
int r=0,st,N;
unsigned int a,b;
while((1<<r)<(NN>>1))++r;//inv:r=0
for(N=2;N<=NN;N<<=1,--r){
//inv for(N=NN;N>1;N>>=1,r++){
for(st=0;st<NN;st+=N){
int i,ss=st+(N>>1);
for(i=(N>>1)-1;i>=0;--i){
a=co[st+i]; b=(ps[i<<r]*co[ss+i])%P;
//inv b=co[ss+i];
co[st+i]=a+b; if(co[st+i]>=P)co[st+i]-=P;
co[ss+i]=a+P-b; if(co[ss+i]>=P)co[ss+i]-=P;
//inv co[ss+i]=((a+P-b)*ps[i<<r])%P;
}
}
}
}
poly operator*(const poly& _b)const{
poly a=*this,b=_b;
int k=n+b.n,i,N=1;
while(N<=k)N*=2;
a.co.resize(N,0); b.co.resize(N,0);
int r=bigmod(root,(P-1)/N),Ni=inv(N,P);
ps[0]=1;
for(i=1;i<N;++i)ps[i]=(ps[i-1]*r)%P;
a.ntt(N);b.ntt(N);
for(i=0;i<N;++i)a.co[i]=((long long)a.co[i]*b.co[i])%P;
r=inv(r,P);
for(i=1;i<N/2;++i)std::swap(ps[i],ps[N-i]);
a.ntt_inv(N);
for(i=0;i<N;++i)a.co[i]=((long long)a.co[i]*Ni)%P;
a.n=n+_b.n; return a;
}
};
char c[2000005];
vector<pair<poly,int> > dc(int l,int r){
if(r-l<=1000){
int dp[2][2][2005],dp2[2][2][2005];
MEM(dp);
MEM(dp2);
if(c[l*2]!='Y')dp[0][0][1000]++;
if(c[l*2]!='R')dp[1][1][1000]++;
for(int i = l*2+2;i<=r*2;i+=2){
if(c[i]!='Y'){
for(int j = 0;j<2;j++){
for(int k = 0;k<2;k++){
if(k==0){
for(int a=0;a<=2000;a++){
if(c[i-1]=='?')
dp2[j][0][a]+=dp[j][k][a]*2%mod;
else dp2[j][0][a]+=dp[j][k][a];
dp2[j][0][a]%=mod;
}
}
else{
if(c[i-1]!='P')
for(int a=0;a<=2000;a++){
dp2[j][0][a]+=dp[j][k][a];
dp2[j][0][a]%=mod;
}
if(c[i-1]!='G'){
for(int a=1;a<=2000;a++){
dp2[j][0][a-1]+=dp[j][k][a];
dp2[j][0][a-1]%=mod;
}
}
}
}
}
}
if(c[i]!='R'){
for(int j = 0;j<2;j++){
for(int k = 0;k<2;k++){
if(k==1){
for(int a=0;a<=2000;a++){
if(c[i-1]=='?')
dp2[j][1][a]+=dp[j][k][a]*2%mod;
else dp2[j][1][a]+=dp[j][k][a];
dp2[j][1][a]%=mod;
}
}
else{
if(c[i-1]!='P')
for(int a=0;a<=2000;a++){
dp2[j][1][a]+=dp[j][k][a];
dp2[j][1][a]%=mod;
}
if(c[i-1]!='G'){
for(int a=0;a<=1999;a++){
dp2[j][1][a+1]+=dp[j][k][a];
dp2[j][1][a+1]%=mod;
}
}
}
}
}
}
for(int a=0;a<2;a++){
for(int b=0;b<2;b++){
for(int c=0;c<=2000;c++){
dp[a][b][c]=dp2[a][b][c];
dp2[a][b][c]=0;
// if(dp[a][b][c])
// printf("%d %d %d %d %d\n",i,a,b,c-100,dp[a][b][c]);
}
}
}
}
vector<pair<poly,int> > v;
for(int a=0;a<2;a++){
for(int b=0;b<2;b++){
int st=-1;
poly p(0);
p.co.clear();
for(int c=0;c<=2000;c++){
if(dp[a][b][c]&&st==-1){
st=c;
}
if(st!=-1)p.co.push_back(dp[a][b][c]);
}
while(p.co.size()&&p.co.back()==0)p.co.pop_back();
if(p.co.empty())p.co.pb(0),st=1000;
p.n=p.co.size()-1;
v.pb(mp(p,st-1000));
}
}
return v;
}
else{
int mid=(l+r)/2;
auto v1=dc(l,mid);
auto v2=dc(mid+1,r);
vector<pair<poly,int> > v(4);
for(int i = 0;i<4;i++){
for(int j = 0;j<4;j++){
int x1=i>>1,x2=i&1;
int y1=j>>1,y2=j&1;
poly p=v1[i].x*v2[j].x;
LL a1=0,a2=0,a3=0;
int d=v1[i].y+v2[j].y;
int q=x1*2+y2;
reverse(v[q].x.co.begin(),v[q].x.co.end());
while(d<v[q].y){
v[q].y--;
v[q].x.co.pb(0);
v[q].x.n++;
}
reverse(v[q].x.co.begin(),v[q].x.co.end());
LL a4=0;
if(c[mid*2+1]!='P')
for(int i = 0;i<p.co.size();i++){
while(v[q].x.co.size()<=i+d-v[q].y)v[q].x.co.pb(0),v[q].x.n++;
v[q].x.co[i+d-v[q].y]+=p.co[i];
v[q].x.co[i+d-v[q].y]%=mod;
}
if(c[mid*2+1]!='G'){
if(x2==0&&y1==1)d++;
if(x2==1&&y1==0)d--;
reverse(v[q].x.co.begin(),v[q].x.co.end());
while(d<v[q].y){
v[q].y--;
v[q].x.co.pb(0);
v[q].x.n++;
}
reverse(v[q].x.co.begin(),v[q].x.co.end());
for(int i = 0;i<p.co.size();i++){
while(v[q].x.co.size()<=i+d-v[q].y)v[q].x.co.pb(0),v[q].x.n++;
v[q].x.co[i+d-v[q].y]+=p.co[i];
v[q].x.co[i+d-v[q].y]%=mod;
}
}
// printf("%d %d\n",v[q].x.n,p.n);
}
}
/* printf("ans: %d %d\n ",l,r);
for(int i = 0;i<4;i++){
printf("%d\n",v[i].y);
for(auto it:v[i].x.co)printf("%d ",it);
printf("\n");
}*/
return v;
}
}
void solve(int T){
int n;
scanf("%d",&n);
scanf("%s",c);
// for(int i = 0;i<2*n;i++)c[i]='?';
auto p=dc(0,n-1);
LL ans=0;
for(int i = 0;i<2;i++){
for(int j = 0;j<2;j++){
int q=i*2+j;
if(i==j){
if(c[2*n-1]!='P'){
int need=-p[q].y;
if(p[q].x.co.size()>need&&need>=0)ans+=p[q].x.co[need];
}
if(c[2*n-1]!='G'){
int need=-p[q].y;
if(p[q].x.co.size()>need&&need>=0)ans+=p[q].x.co[need];
}
}
else{
if(c[2*n-1]!='P'){
int need=-p[q].y;
if(p[q].x.co.size()>need&&need>=0)ans+=p[q].x.co[need];
}
if(c[2*n-1]!='G'){
int need=-p[q].y;
if(j==0&&i==1)need--;
if(j==1&&i==0)need++;
if(p[q].x.co.size()>need&&need>=0)ans+=p[q].x.co[need];
}
}
}
}
printf("%lld\n",ans%mod);
}
int main(){
int t=1;0000;
for(int i = 1;i<=t;i++){
solve(i);
}
return 0;
}
/*
1543904 3707852 107840
1 23
JAY'S SON JA$ON
3 4
1 2 1 3
1 3 1 5
1 2 2 2
1 3 3 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 101716kb
input:
2 ????
output:
12
result:
ok 1 number(s): "12"
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 101776kb
input:
3 ??YR?B
output:
14
result:
wrong answer 1st numbers differ - expected: '4', found: '14'