QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#454168	#884. Joining Treasure Hunt	grass8cow^#	AC ✓	407ms	105704kb	C++17	2.7kb	2024-06-24 17:07:14	2024-06-24 17:07:14

Judging History

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

[2024-06-24 17:07:14]
评测

测评结果：AC
用时：407ms
内存：105704kb

查看

[2024-06-24 17:07:14]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,G=3,GI=(mod+1)/3;
int qpow(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
int lb[1<<23],L,wi[1<<23][2];
void init(int n){
    L=1;while(L<=n)L<<=1;
    for(int i=1;i<L;i++)lb[i]=(lb[i>>1]>>1)|((i&1)?(L>>1):0);
}
void NTT(int *a,int fl){
    for(int i=0;i<L;i++)if(i<lb[i])swap(a[i],a[lb[i]]);
    for(int o=1;o<L;o<<=1){
        for(int i=0;i<L;i+=(o<<1))for(int j=0;j<o;j++){
            int x=a[i+j],y=1ll*wi[j+o][fl]*a[i+j+o]%mod;
            a[i+j]=x+y;if(a[i+j]>=mod)a[i+j]-=mod;
            a[i+j+o]=x+mod-y;if(a[i+j+o]>=mod)a[i+j+o]-=mod;
        }
    }
}
int n,m;
mt19937 rnd(time(0));
int has[32];
int gs[(1<<23)+10],a[2001000],b[2001000];
int p[(1<<23)+10],q[(1<<23)+10];
int main(){
    for(int t=0;t<2;t++)for(int o=1;o<(1<<23);o<<=1){
		int Wn=qpow(t?G:GI,(mod-1)/(o<<1)),w=1;
		for(int i=0;i<o;i++)wi[i+o][t]=w,w=1ll*w*Wn%mod;
	}
    for(int i=0;i<28;i++)has[i]=rnd()%mod;
    scanf("%d%d",&n,&m);
    init(n+m+2);char C[2];
    for(int i=0;i<n;i++){
        scanf("%s",C);
        if(C[0]=='?');
        else{
            char c=C[0];
            int x,y;scanf("%d",&y);y--;
            if(c=='n')x=0;if(c=='s')x=1;
            if(c=='e')x=2;if(c=='w')x=3;
            a[i]=has[y*4+x];
        }
    }
    for(int i=0;i<m;i++){
        scanf("%s",C);
        if(C[0]=='?');
        else{
            char c=C[0];
            int x,y;scanf("%d",&y);y--;
            if(c=='n')x=0;if(c=='s')x=1;
            if(c=='e')x=2;if(c=='w')x=3;
            b[i]=has[y*4+x];
        }
    }
    n--,m--;
    swap(n,m),swap(a,b);
    reverse(a,a+n+1);
    for(int i=0;i<L;i++)p[i]=q[i]=0;
    for(int i=0;i<=n;i++)if(a[i])p[i]=1ll*a[i]*a[i]%mod*a[i]%mod;
    for(int i=0;i<=m;i++)q[i]=b[i];NTT(p,1);NTT(q,1);
    for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;NTT(p,0);
    for(int i=n;i<=m;i++)gs[i]=p[i];
    //---
    for(int i=0;i<L;i++)p[i]=q[i]=0;
    for(int i=0;i<=n;i++)p[i]=a[i];
    for(int i=0;i<=m;i++)if(b[i])q[i]=1ll*b[i]*b[i]%mod*b[i]%mod;NTT(p,1);NTT(q,1);
    for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;NTT(p,0);
    for(int i=n;i<=m;i++){gs[i]+=p[i];if(gs[i]>=mod)gs[i]-=mod;}
    //---
    for(int i=0;i<L;i++)p[i]=q[i]=0;
    for(int i=0;i<=n;i++)if(a[i])p[i]=mod-2ll*a[i]*a[i]%mod;
    for(int i=0;i<=m;i++)if(b[i])q[i]=1ll*b[i]*b[i]%mod;NTT(p,1);NTT(q,1);
    for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;NTT(p,0);
    int ans=0;
    for(int i=n;i<=m;i++){
        gs[i]+=p[i];if(gs[i]>=mod)gs[i]-=mod;
        gs[i]=(gs[i]+mod)%mod;
        if(!gs[i])ans++;
    }
    printf("%d",ans);
    return 0;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 70ms

memory: 89404kb

input:

4 3
n 4
e 1
?
s 5
?
e 1
?

output:

result:

ok answer is '2'

Test #2:

score: 0

Accepted

time: 71ms

memory: 90592kb

input:

4 3
n 4
e 1
w 3
s 5
?
e 1
?

output:

result:

ok answer is '1'

Test #3:

score: 0

Accepted

time: 407ms

memory: 105704kb

input:

400000 200000
?
?
e 7
e 7
?
?
?
e 7
e 7
?
?
e 7
?
e 7
e 7
?
e 7
?
?
?
e 7
?
?
e 7
?
?
?
?
e 7
?
e 7
?
?
e 7
?
?
e 7
e 7
e 7
?
?
?
?
?
?
e 7
?
e 7
?
?
?
?
?
?
?
?
?
?
e 7
e 7
?
?
e 7
?
e 7
e 7
?
?
e 7
e 7
e 7
?
e 7
e 7
?
?
?
?
?
?
e 7
e 7
?
?
e 7
?
?
?
?
e 7
?
?
?
e 7
?
e 7
?
e 7
?
?
?
?
?
e 7
?
?
?
...

output:

result:

ok answer is '133037'

Test #4:

score: 0

Accepted

time: 146ms

memory: 96052kb

input:

200000 10000
e 1
s 1
w 1
n 2
e 2
s 2
w 2
n 3
e 3
s 3
w 3
n 4
e 4
s 4
w 4
n 5
e 5
s 5
w 5
n 6
e 6
s 6
w 6
n 7
e 7
s 7
w 7
n 1
e 1
s 1
w 1
n 2
e 2
s 2
w 2
n 3
e 3
s 3
w 3
n 4
e 4
s 4
w 4
n 5
e 5
s 5
w 5
n 6
e 6
s 6
w 6
n 7
e 7
s 7
w 7
n 1
e 1
s 1
w 1
n 2
e 2
s 2
w 2
n 3
e 3
s 3
w 3
n 4
e 4
s 4
w 4
n 5...

output:

result:

ok answer is '6786'

Test #5:

score: 0

Accepted

time: 148ms

memory: 91904kb

input:

200000 10000
e 1
s 1
w 1
n 2
e 2
?
w 2
n 3
e 3
s 3
w 3
n 4
e 4
s 4
w 4
n 5
e 5
s 5
w 5
n 6
e 6
s 6
w 6
n 7
e 7
s 7
w 7
?
e 1
s 1
w 1
n 2
e 2
s 2
w 2
?
e 3
s 3
w 3
n 4
e 4
s 4
w 4
n 5
e 5
s 5
w 5
n 6
e 6
s 6
w 6
n 7
e 7
s 7
w 7
n 1
e 1
s 1
w 1
n 2
e 2
s 2
w 2
n 3
e 3
s 3
w 3
n 4
e 4
s 4
w 4
n 5
e 5
s...

output:

result:

ok answer is '6786'

Test #6:

score: 0

Accepted

time: 146ms

memory: 95484kb

input:

100000 50000
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1
n 1...

output:

result:

ok answer is '523'

Test #7:

score: 0

Accepted

time: 154ms

memory: 91828kb

input:

200000 4
s 3
e 2
?
n 5
s 2
e 2
e 5
w 2
w 6
w 5
w 2
n 4
e 3
?
n 5
e 4
n 5
?
s 2
w 1
e 4
s 3
?
?
n 1
e 3
w 7
n 5
w 5
e 1
?
w 3
s 6
e 7
e 4
e 5
n 5
w 3
w 7
e 2
s 2
w 2
e 1
s 3
s 4
w 7
n 3
w 6
e 4
s 7
w 5
n 5
?
?
s 2
e 1
s 3
?
s 1
e 6
n 6
e 7
?
s 6
s 3
w 6
w 2
e 7
e 3
w 3
e 6
e 4
n 2
n 7
w 3
s 5
w 7
n 2...

output:

result:

ok answer is '52'

Test #8:

score: 0

Accepted

time: 232ms

memory: 99624kb

input:

200000 100000
?
e 6
e 7
n 5
e 5
w 4
w 1
e 3
e 3
n 6
n 6
w 1
e 2
e 6
s 4
s 2
e 4
s 6
w 6
e 6
n 2
e 1
n 5
s 5
e 3
e 4
w 7
n 1
s 6
n 6
n 5
s 6
s 2
w 7
e 6
e 4
e 4
n 1
?
w 2
n 1
n 3
e 2
w 1
e 1
s 6
w 7
s 1
e 2
e 3
e 3
e 7
s 1
e 2
w 1
w 6
s 1
s 7
e 4
e 1
s 1
w 5
?
s 5
n 4
w 2
?
e 3
n 6
n 2
s 4
s 1
n 7
n ...

output:

result:

ok answer is '0'

Test #9:

score: 0

Accepted

time: 221ms

memory: 97696kb

input:

200000 100000
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e 7
e ...

output:

result:

ok answer is '100001'