QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#232358 | #7634. Cards | zhouhuanyi | AC ✓ | 6873ms | 177804kb | C++23 | 4.9kb | 2023-10-30 11:38:45 | 2023-10-30 11:38:45 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 100000
#define M 1048576
#define K 20
#define g 3
#define mod 998244353
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,m,length,ans=1,sx[N+1],num[M+1],F[N+1],A[M+1],B[M+1],rev[M+1],s[M+1],wn[K+1][M+1],wn2[K+1][M+1],dp[N+1][2],delta[N+1],delta2[N+1],delta3[N+1],delta4[N+1],delta5[N+1];
int fast_pow(int a,int b)
{
int res=1,mul=a;
while (b)
{
if (b&1) res=1ll*res*mul%mod;
mul=1ll*mul*mul%mod,b>>=1;
}
return res;
}
int MD(int x)
{
return x>=mod?x-mod:x;
}
int MD2(int x)
{
return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
x+=d;
if (x>=mod) x-=mod;
return;
}
void Adder2(int &x,int d)
{
x+=d;
if (x<0) x+=mod;
return;
}
void NTT(int limit,int *s,int type)
{
int s1,s2;
for (int i=1;i<limit;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?limit>>1:0);
for (int i=1;i<limit;++i)
if (rev[i]>i)
swap(s[i],s[rev[i]]);
if (type==1)
{
for (int i=2;i<=limit;i<<=1)
for (int j=0;j+i-1<limit;j+=i)
for (int k=j;k<j+(i>>1);++k)
s1=s[k],s2=1ll*s[k+(i>>1)]*wn[num[i]][k-j]%mod,s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
}
else
{
for (int i=2;i<=limit;i<<=1)
for (int j=0;j+i-1<limit;j+=i)
for (int k=j;k<j+(i>>1);++k)
s1=s[k],s2=1ll*s[k+(i>>1)]*wn2[num[i]][k-j]%mod,s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
s1=fast_pow(limit,mod-2);
for (int i=0;i<=limit;++i) s[i]=1ll*s[i]*s1%mod;
}
return;
}
vector<int>operator * (vector<int>a,vector<int>b)
{
vector<int>c(a.size()+b.size()-1);
int limit=1;
while (limit<=c.size()) limit<<=1;
for (int i=0;i<=limit;++i) A[i]=B[i]=0;
for (int i=0;i<a.size();++i) A[i]=a[i];
for (int i=0;i<b.size();++i) B[i]=b[i];
NTT(limit,A,1),NTT(limit,B,1);
for (int i=0;i<=limit;++i) A[i]=1ll*A[i]*B[i]%mod;
NTT(limit,A,-1);
for (int i=0;i<c.size();++i) c[i]=A[i];
return c;
}
vector<int>revs(vector<int>a)
{
reverse(a.begin(),a.end());
return a;
}
vector<int>calc(vector<int>a,int b)
{
vector<int>c;
for (int i=(int)(a.size()>>1)-b;i<=(int)(a.size()>>1)+b;++i) c.push_back(a[i]);
return c;
}
struct seg
{
struct node
{
int l,r;
vector<int>data;
};
node tree[(N<<2)+1];
void push_up(int k)
{
tree[k].data=tree[k<<1].data*tree[k<<1|1].data;
return;
}
void build(int k,int l,int r)
{
tree[k].l=l,tree[k].r=r;
if (l==r)
{
tree[k].data={sx[1],sx[2],sx[3],sx[4],sx[5]};
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
return;
}
void solve(int k,vector<int>res)
{
while (res.size()>((tree[k].r-tree[k].l+1)<<2)+1) res=calc(res,(tree[k].r-tree[k].l+1)<<1);
if (tree[k].l==tree[k].r)
{
for (int i=0;i<=4;++i) Adder(F[tree[k].l],1ll*res[i]*sx[i+1]%mod);
return;
}
solve(k<<1,res),solve(k<<1|1,res*revs(tree[k<<1].data));
return;
}
};
seg T;
void get(int x)
{
for (int i=0;i<=m;++i) F[i]=0;
if (x<-(m<<1)||x>(m<<1)) return;
vector<int>p((m<<2)+1);
p[x+(m<<1)]=1,T.solve(1,p);
return;
}
void solve(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1;
vector<int>a(mid-l+1);
vector<int>b(mid-l+1);
vector<int>c(r-l+1);
vector<int>d(r-l+1);
vector<int>e(r-l+1);
vector<int>st1;
vector<int>st2;
vector<int>st3;
vector<int>st4;
vector<int>st5;
solve(l,mid);
for (int i=l;i<=mid;++i) a[i-l]=dp[i][0],b[i-l]=dp[i][1];
for (int i=1;i<=r-l;++i) c[i]=delta[i-1],d[i]=delta2[i-1],e[i]=delta3[i-1];
st1=a*c,st2=a*d,st3=b*c,st4=b*d,st5=a*e;
for (int i=mid+1;i<=r;++i)
{
Adder2(dp[i][0],-1ll*st1[i-l]*sx[2]%mod);
Adder2(dp[i][0],-1ll*st2[i-l]*sx[1]%mod);
Adder2(dp[i][0],-1ll*st3[i-l]*sx[1]%mod);
Adder2(dp[i][1],-1ll*st2[i-l]*sx[2]%mod);
Adder2(dp[i][1],-1ll*st5[i-l]*sx[1]%mod);
Adder2(dp[i][1],-1ll*st4[i-l]*sx[1]%mod);
}
solve(mid+1,r);
return;
}
int main()
{
int rst=0;
for (int i=2,w;i<=M;i<<=1)
{
num[i]=++length,w=fast_pow(g,(mod-1)/i);
for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*w%mod) wn[num[i]][j]=res;
w=fast_pow(g,(mod-1)/i*(i-1));
for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*w%mod) wn2[num[i]][j]=res;
}
n=read(),m=read();
if (!m)
{
puts("1");
return 0;
}
for (int i=1;i<=5;++i) sx[i]=read(),Adder(rst,sx[i]);
for (int i=1;i<=5;++i) sx[i]=1ll*sx[i]*fast_pow(rst,mod-2)%mod;
T.build(1,1,m);
get(1);
for (int i=1;i<=m;++i) delta[i]=F[i];
get(2);
for (int i=1;i<=m;++i) delta2[i]=F[i];
get(3);
for (int i=1;i<=m;++i) delta3[i]=F[i];
get(-n),delta4[0]=(n==0);
for (int i=1;i<=m;++i) delta4[i]=F[i];
get(-n+1),delta5[0]=(n==1);
for (int i=1;i<=m;++i) delta5[i]=F[i];
for (int i=0;i<=m;++i) dp[i][0]=delta4[i],dp[i][1]=delta5[i];
solve(0,m);
for (int i=0;i<=m-1;++i)
{
Adder2(ans,-1ll*dp[i][0]*sx[2]%mod);
Adder2(ans,-1ll*dp[i][0]*sx[1]%mod);
Adder2(ans,-1ll*dp[i][1]*sx[1]%mod);
}
printf("%d\n",ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 112664kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 6797ms
memory: 164012kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 6763ms
memory: 170748kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 6793ms
memory: 164300kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 15ms
memory: 113440kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 3024ms
memory: 151160kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 11ms
memory: 114256kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 6743ms
memory: 165324kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 6873ms
memory: 165068kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 6787ms
memory: 169336kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 6823ms
memory: 164156kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 6744ms
memory: 177804kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 6721ms
memory: 170380kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 8ms
memory: 106252kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 338ms
memory: 117732kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 345ms
memory: 137344kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 343ms
memory: 117984kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed