QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#279949#7873. Since A Lightzhouhuanyi51 723ms50060kbC++203.3kb2023-12-09 12:45:342023-12-09 12:45:35

Judging History

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

  • [2023-12-09 12:45:35]
  • 评测
  • 测评结果:51
  • 用时:723ms
  • 内存:50060kb
  • [2023-12-09 12:45:34]
  • 提交

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

output:


result: