QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#279949 | #7873. Since A Light | zhouhuanyi | 51 | 723ms | 50060kb | C++20 | 3.3kb | 2023-12-09 12:45:34 | 2023-12-09 12:45:35 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#define N 100000
#define M 262144
#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 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;
}
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;
}
int MD(int x)
{
return x>=mod?x-mod:x;
}
int MD2(int x)
{
return x<0?x+mod:x;
}
int n,d,ans,length,cl[6][6],A[M+1],B[M+1],wn[K+1][M+1],wn2[K+1][M+1],rev[M+1],num[M+1];
struct matrix
{
vector<int>p[6][6];
};
matrix e,nw,dres,c,zero;
vector<int>zro;
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=0;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)
{
if (a.size()<b.size()) swap(a,b);
for (int i=0;i<b.size();++i) Adder(a[i],b[i]);
return a;
}
vector<int>operator * (vector<int>a,vector<int>b)
{
if (a.empty()||b.empty()) return zro;
int limit=1;
vector<int>cs(min((int)(a.size()+b.size()-1),d));
while (limit<=a.size()+b.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<cs.size();++i) cs[i]=A[i];
return cs;
}
matrix operator * (matrix a,matrix b)
{
c=zero;
for (int k=0;k<6;++k)
for (int i=0;i<6;++i)
for (int j=0;j<6;++j)
c.p[i][j]=c.p[i][j]+a.p[i][k]*b.p[k][j];
return c;
}
matrix fast_pows(matrix a,int b)
{
matrix res=e,mul=a;
while (b)
{
if (b&1) res=res*mul;
mul=mul*mul,b>>=1;
}
return res;
}
int main()
{
int rst;
for (int i=2;i<=M;i<<=1)
{
num[i]=++length,rst=fast_pow(g,(mod-1)/i);
for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*rst%mod) wn[num[i]][j]=res;
rst=fast_pow(g,(mod-1)/i*(i-1));
for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*rst%mod) wn2[num[i]][j]=res;
}
for (int i=0;i<6;++i) e.p[i][i]={1};
n=read(),d=read();
for (int op=0;op<=1;++op)
for (int op2=0;op2<=1;++op2)
for (int op3=0;op3<=1-op;++op3)
for (int op4=0;op4<=1-op2;++op4)
nw.p[(op<<1)+op2][(op3<<1)+op4].resize((!op&&!op3)+(!op2&&!op4)+1),nw.p[(op<<1)+op2][(op3<<1)+op4].back()=1;
nw.p[1][4]=nw.p[4][4]=nw.p[4][5]=nw.p[5][4]={1},dres=fast_pows(nw,n);
for (int i=0;i<=3;++i)
if (d-1<dres.p[i][4].size())
Adder(ans,dres.p[i][4][d-1]);
printf("%d\n",ans);
return 0;
}
详细
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 3ms
memory: 48932kb
input:
1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 4ms
memory: 48908kb
input:
2 1
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 4ms
memory: 44804kb
input:
3 2
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 4ms
memory: 47124kb
input:
4 4
output:
5
result:
ok single line: '5'
Test #5:
score: 0
Accepted
time: 0ms
memory: 47132kb
input:
5 7
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 4ms
memory: 46936kb
input:
6 4
output:
41
result:
ok single line: '41'
Test #7:
score: 0
Accepted
time: 0ms
memory: 46904kb
input:
7 11
output:
2
result:
ok single line: '2'
Test #8:
score: 0
Accepted
time: 4ms
memory: 44792kb
input:
8 8
output:
175
result:
ok single line: '175'
Test #9:
score: 0
Accepted
time: 0ms
memory: 45148kb
input:
9 10
output:
298
result:
ok single line: '298'
Test #10:
score: 0
Accepted
time: 4ms
memory: 46836kb
input:
10 3
output:
392
result:
ok single line: '392'
Test #11:
score: 0
Accepted
time: 3ms
memory: 47060kb
input:
11 8
output:
3785
result:
ok single line: '3785'
Test #12:
score: 0
Accepted
time: 6ms
memory: 46856kb
input:
12 15
output:
1422
result:
ok single line: '1422'
Test #13:
score: 0
Accepted
time: 3ms
memory: 46848kb
input:
13 17
output:
2008
result:
ok single line: '2008'
Test #14:
score: 0
Accepted
time: 3ms
memory: 45092kb
input:
14 16
output:
21508
result:
ok single line: '21508'
Test #15:
score: 0
Accepted
time: 5ms
memory: 44800kb
input:
15 1
output:
1596
result:
ok single line: '1596'
Test #16:
score: 0
Accepted
time: 3ms
memory: 47116kb
input:
16 28
output:
29
result:
ok single line: '29'
Test #17:
score: 0
Accepted
time: 4ms
memory: 48976kb
input:
17 6
output:
98086
result:
ok single line: '98086'
Test #18:
score: 0
Accepted
time: 4ms
memory: 46852kb
input:
18 11
output:
1478534
result:
ok single line: '1478534'
Test #19:
score: 0
Accepted
time: 3ms
memory: 48896kb
input:
19 25
output:
250068
result:
ok single line: '250068'
Test #20:
score: 0
Accepted
time: 3ms
memory: 44808kb
input:
20 27
output:
355418
result:
ok single line: '355418'
Test #21:
score: 0
Accepted
time: 0ms
memory: 44748kb
input:
21 23
output:
13517834
result:
ok single line: '13517834'
Test #22:
score: 0
Accepted
time: 0ms
memory: 46892kb
input:
22 4
output:
315460
result:
ok single line: '315460'
Test #23:
score: 0
Accepted
time: 0ms
memory: 46860kb
input:
23 37
output:
18428
result:
ok single line: '18428'
Test #24:
score: 0
Accepted
time: 0ms
memory: 49152kb
input:
24 18
output:
647287901
result:
ok single line: '647287901'
Test #25:
score: 0
Accepted
time: 3ms
memory: 44876kb
input:
25 40
output:
136655
result:
ok single line: '136655'
Subtask #2:
score: 7
Accepted
Test #26:
score: 7
Accepted
time: 8ms
memory: 46976kb
input:
380 59
output:
718355613
result:
ok single line: '718355613'
Test #27:
score: 0
Accepted
time: 8ms
memory: 48972kb
input:
164 46
output:
353450103
result:
ok single line: '353450103'
Test #28:
score: 0
Accepted
time: 12ms
memory: 44960kb
input:
206 144
output:
910367339
result:
ok single line: '910367339'
Test #29:
score: 0
Accepted
time: 10ms
memory: 44948kb
input:
270 127
output:
78796015
result:
ok single line: '78796015'
Test #30:
score: 0
Accepted
time: 10ms
memory: 49200kb
input:
157 87
output:
705420296
result:
ok single line: '705420296'
Subtask #3:
score: 10
Accepted
Test #31:
score: 10
Accepted
time: 15ms
memory: 49244kb
input:
413 652
output:
170600118
result:
ok single line: '170600118'
Test #32:
score: 0
Accepted
time: 33ms
memory: 49248kb
input:
724 979
output:
677376486
result:
ok single line: '677376486'
Test #33:
score: 0
Accepted
time: 79ms
memory: 47820kb
input:
1667 1699
output:
147640784
result:
ok single line: '147640784'
Test #34:
score: 0
Accepted
time: 61ms
memory: 47220kb
input:
1980 517
output:
276583672
result:
ok single line: '276583672'
Test #35:
score: 0
Accepted
time: 82ms
memory: 50060kb
input:
2000 2000
output:
265422351
result:
ok single line: '265422351'
Subtask #4:
score: 14
Accepted
Test #36:
score: 14
Accepted
time: 253ms
memory: 49020kb
input:
4495 4498
output:
375585699
result:
ok single line: '375585699'
Test #37:
score: 0
Accepted
time: 178ms
memory: 47892kb
input:
4968 2196
output:
844161053
result:
ok single line: '844161053'
Test #38:
score: 0
Accepted
time: 175ms
memory: 48732kb
input:
3967 3143
output:
496535114
result:
ok single line: '496535114'
Test #39:
score: 0
Accepted
time: 151ms
memory: 46964kb
input:
2406 4205
output:
599052202
result:
ok single line: '599052202'
Test #40:
score: 0
Accepted
time: 174ms
memory: 46544kb
input:
3942 3259
output:
110001226
result:
ok single line: '110001226'
Subtask #5:
score: 19
Accepted
Test #41:
score: 19
Accepted
time: 19ms
memory: 48968kb
input:
158314621 32
output:
465741961
result:
ok single line: '465741961'
Test #42:
score: 0
Accepted
time: 41ms
memory: 46900kb
input:
456573367 93
output:
310185347
result:
ok single line: '310185347'
Test #43:
score: 0
Accepted
time: 19ms
memory: 46888kb
input:
638787498 62
output:
467767457
result:
ok single line: '467767457'
Test #44:
score: 0
Accepted
time: 24ms
memory: 46936kb
input:
752253598 48
output:
110045639
result:
ok single line: '110045639'
Test #45:
score: 0
Accepted
time: 42ms
memory: 48944kb
input:
992442354 76
output:
330338775
result:
ok single line: '330338775'
Subtask #6:
score: 0
Time Limit Exceeded
Test #46:
score: 36
Accepted
time: 614ms
memory: 45576kb
input:
812922977 1762
output:
927995257
result:
ok single line: '927995257'
Test #47:
score: 0
Accepted
time: 723ms
memory: 47404kb
input:
661518393 1247
output:
469311509
result:
ok single line: '469311509'
Test #48:
score: 0
Accepted
time: 582ms
memory: 47640kb
input:
562238351 1811
output:
157645249
result:
ok single line: '157645249'
Test #49:
score: 0
Accepted
time: 25ms
memory: 48984kb
input:
985149295 62
output:
137919742
result:
ok single line: '137919742'
Test #50:
score: -36
Time Limit Exceeded
input:
983061012 3695
output:
result:
Subtask #7:
score: 0
Time Limit Exceeded
Test #51:
score: 0
Time Limit Exceeded
input:
320076133 78121