QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#274211#7881. Computational ComplexityzhouhuanyiTL 223ms552536kbC++146.2kb2023-12-03 12:54:132023-12-03 12:54:14

Judging History

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

  • [2023-12-03 12:54:14]
  • 评测
  • 测评结果：TL
  • 用时：223ms
  • 内存：552536kb
查看
  • [2023-12-03 12:54:13]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#define N 5000000
#define W 200000000
#define M 10000
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,type;
	bool operator < (const reads &t)const
	{
		return num!=t.num?num<t.num:type<t.type;
	}
};
struct node
{
	reads num;
	long long data;
};
node tong[M+1],tong2[M+1];
reads operator * (reads a,int b)
{
	return (reads){a.num*b,!a.type};
}
int T,length,length2,lg[M+1];
long long A[N+1],B[N+1],F[7*N+1],G[7*N+1],mod;
map<reads,long long>dp;
map<long long,__int128>DSP;
map<long long,__int128>DSP2;
set<reads>s;
void bfs()
{
	reads top;
	s.insert((reads){1,0}),dp[(reads){1,0}]=1;
	while (!s.empty())
	{
		top=*s.begin(),s.erase(top),tong[++length]=(node){top,dp[top]};
		if (!top.type)
		{
			if ((top*2).num<=W) dp[top*2]+=dp[top],s.insert(top*2);
			if ((top*3).num<=W) dp[top*3]+=dp[top],s.insert(top*3);
			if ((top*5).num<=W) dp[top*5]+=dp[top],s.insert(top*5);
			if ((top*7).num<=W) dp[top*7]+=dp[top],s.insert(top*7);
		}
		else
		{
			if ((top*2).num<=W) dp[top*2]+=dp[top],s.insert(top*2);
			if ((top*3).num<=W) dp[top*3]+=dp[top],s.insert(top*3);
			if ((top*4).num<=W) dp[top*4]+=dp[top],s.insert(top*4);
			if ((top*5).num<=W) dp[top*5]+=dp[top],s.insert(top*5);
		}
	}
	s.clear(),dp.clear(),s.insert((reads){1,1}),dp[(reads){1,1}]=1;
	while (!s.empty())
	{
		top=*s.begin(),s.erase(top),tong2[++length2]=(node){top,dp[top]};
		if (!top.type)
		{
			if ((top*2).num<=W) dp[top*2]+=dp[top],s.insert(top*2);
			if ((top*3).num<=W) dp[top*3]+=dp[top],s.insert(top*3);
			if ((top*5).num<=W) dp[top*5]+=dp[top],s.insert(top*5);
			if ((top*7).num<=W) dp[top*7]+=dp[top],s.insert(top*7);
		}
		else
		{
			if ((top*2).num<=W) dp[top*2]+=dp[top],s.insert(top*2);
			if ((top*3).num<=W) dp[top*3]+=dp[top],s.insert(top*3);
			if ((top*4).num<=W) dp[top*4]+=dp[top],s.insert(top*4);
			if ((top*5).num<=W) dp[top*5]+=dp[top],s.insert(top*5);
		}
	}
	return;
}
long long getA(long long x)
{
	if (x<=N) return A[x]%mod;
	if (DSP.find(x)!=DSP.end()) return DSP[x]%mod;
	int ps=0;
	long long l=(x+7*N-1)/(7*N),r=(x-1)/N;
	__int128 res=0;
	for (int i=lg[length];i>=0;--i)
		if (ps+(1<<i)<=length&&tong[ps+(1<<i)].num.num<l)
			ps+=(1<<i);
	ps++;
	for (int i=ps;i<=length&&tong[i].num.num<=r;i+=8)
	{
		res+=((!tong[i].num.type)?(__int128)(F[x/tong[i].num.num])*tong[i].data:(__int128)(G[x/tong[i].num.num])*tong[i].data);
		if (i+1<=length&&tong[i+1].num.num<=r) res+=((!tong[i+1].num.type)?(__int128)(F[x/tong[i+1].num.num])*tong[i+1].data:(__int128)(G[x/tong[i+1].num.num])*tong[i+1].data);
		if (i+2<=length&&tong[i+2].num.num<=r) res+=((!tong[i+2].num.type)?(__int128)(F[x/tong[i+2].num.num])*tong[i+2].data:(__int128)(G[x/tong[i+2].num.num])*tong[i+2].data);
		if (i+3<=length&&tong[i+3].num.num<=r) res+=((!tong[i+3].num.type)?(__int128)(F[x/tong[i+3].num.num])*tong[i+3].data:(__int128)(G[x/tong[i+3].num.num])*tong[i+3].data);
		if (i+4<=length&&tong[i+4].num.num<=r) res+=((!tong[i+4].num.type)?(__int128)(F[x/tong[i+4].num.num])*tong[i+4].data:(__int128)(G[x/tong[i+4].num.num])*tong[i+4].data);
		if (i+5<=length&&tong[i+5].num.num<=r) res+=((!tong[i+5].num.type)?(__int128)(F[x/tong[i+5].num.num])*tong[i+5].data:(__int128)(G[x/tong[i+5].num.num])*tong[i+5].data);
		if (i+6<=length&&tong[i+6].num.num<=r) res+=((!tong[i+6].num.type)?(__int128)(F[x/tong[i+6].num.num])*tong[i+6].data:(__int128)(G[x/tong[i+6].num.num])*tong[i+6].data);
		if (i+7<=length&&tong[i+7].num.num<=r) res+=((!tong[i+7].num.type)?(__int128)(F[x/tong[i+7].num.num])*tong[i+7].data:(__int128)(G[x/tong[i+7].num.num])*tong[i+7].data);
	}
	DSP[x]=res;
	return res%mod;
}
long long getB(long long x)
{
	if (x<=N) return B[x]%mod;
	if (DSP2.find(x)!=DSP2.end()) return DSP2[x]%mod;
	int ps=0;
	long long l=(x+7*N-1)/(7*N),r=(x-1)/N;
	__int128 res=0;
	for (int i=lg[length2];i>=0;--i)
		if (ps+(1<<i)<=length2&&tong2[ps+(1<<i)].num.num<l)
			ps+=(1<<i);
	ps++;
	for (int i=ps;i<=length2&&tong2[i].num.num<=r;i+=8)
	{
		res+=((!tong2[i].num.type)?(__int128)(F[x/tong2[i].num.num])*tong2[i].data:(__int128)(G[x/tong2[i].num.num])*tong2[i].data);
		if (i+1<=length2&&tong2[i+1].num.num<=r) res+=((!tong2[i+1].num.type)?(__int128)(F[x/tong2[i+1].num.num])*tong2[i+1].data:(__int128)(G[x/tong2[i+1].num.num])*tong2[i+1].data);
		if (i+2<=length2&&tong2[i+2].num.num<=r) res+=((!tong2[i+2].num.type)?(__int128)(F[x/tong2[i+2].num.num])*tong2[i+2].data:(__int128)(G[x/tong2[i+2].num.num])*tong2[i+2].data);
		if (i+3<=length2&&tong2[i+3].num.num<=r) res+=((!tong2[i+3].num.type)?(__int128)(F[x/tong2[i+3].num.num])*tong2[i+3].data:(__int128)(G[x/tong2[i+3].num.num])*tong2[i+3].data);
		if (i+4<=length2&&tong2[i+4].num.num<=r) res+=((!tong2[i+4].num.type)?(__int128)(F[x/tong2[i+4].num.num])*tong2[i+4].data:(__int128)(G[x/tong2[i+4].num.num])*tong2[i+4].data);
		if (i+5<=length2&&tong2[i+5].num.num<=r) res+=((!tong2[i+5].num.type)?(__int128)(F[x/tong2[i+5].num.num])*tong2[i+5].data:(__int128)(G[x/tong2[i+5].num.num])*tong2[i+5].data);
		if (i+6<=length2&&tong2[i+6].num.num<=r) res+=((!tong2[i+6].num.type)?(__int128)(F[x/tong2[i+6].num.num])*tong2[i+6].data:(__int128)(G[x/tong2[i+6].num.num])*tong2[i+6].data);
		if (i+7<=length2&&tong2[i+7].num.num<=r) res+=((!tong2[i+7].num.type)?(__int128)(F[x/tong2[i+7].num.num])*tong2[i+7].data:(__int128)(G[x/tong2[i+7].num.num])*tong2[i+7].data);
	}
	DSP2[x]=res;
	return res%mod;
}
int main()
{
	long long x;
	for (int i=2;i<=M;++i) lg[i]=lg[i>>1]+1;
	bfs(),A[0]=read(),B[0]=read(),T=read(),mod=read();
	for (int i=1;i<=N;++i)
	{
		A[i]=max((long long)(i),B[i/2]+B[i/3]+B[i/5]+B[i/7]);
		B[i]=max((long long)(i),A[i/2]+A[i/3]+A[i/4]+A[i/5]);
	}
	for (int i=1;i<=7*N;++i)
	{
		if (i/2<=N) F[i]+=B[i/2];
		if (i/3<=N) F[i]+=B[i/3];
		if (i/5<=N) F[i]+=B[i/5];
		if (i/7<=N) F[i]+=B[i/7];
	}
	for (int i=1;i<=5*N;++i)
	{
		if (i/2<=N) G[i]+=A[i/2];
		if (i/3<=N) G[i]+=A[i/3];
		if (i/4<=N) G[i]+=A[i/4];
		if (i/5<=N) G[i]+=A[i/5];
	}
	while (T--) x=read(),printf("%lld %lld\n",getA(x),getB(x));
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 139ms
memory: 551404kb

input:

1958 920 10 100000000000
0
1
2
3
10
100
200
1000
19580920
20232023

output:

1958 920
3680 7832
10592 9554
17504 11276
50294 64826
784112 893714
1894550 1905470
12057866 12979424
71481494756 48626708512
28127864908 7251681354

result:

ok 20 numbers

Test #2:

score: 0
Accepted
time: 144ms
memory: 551488kb

input:

0 0 10 100000000000
0
1
2
3
4
10
20
30
40
100

output:

0 0
1 1
2 2
3 3
4 4
11 12
25 26
41 41
55 58
162 172

result:

ok 20 numbers

Test #3:

score: 0
Accepted
time: 143ms
memory: 551388kb

input:

2023 2023 10 2023
0
1
2
3
4
5
6
7
8
9

output:

0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

result:

ok 20 numbers

Test #4:

score: 0
Accepted
time: 158ms
memory: 551784kb

input:

36092 30559 2149 729566623185
909730017626
961811467628
978809456383
494310140318
760462959632
726343527430
220697276132
366336227300
456813204361
569783542145
13854148170
51526515764
564416233246
876430686824
862897449267
956440673661
512777546436
728860125927
799238602356
978766770799
47962348351
...

output:

192287632545 510282654057
513694515018 658644741565
90751152870 6088748556
138070013247 301112114677
224113421002 105290451187
630454127249 196841848259
546918129568 526274849982
226761501362 157889210040
135623074930 620463814922
78467045157 602244472172
51639549042 411354142414
329188915935 306494...

result:

ok 4298 numbers

Test #5:

score: 0
Accepted
time: 223ms
memory: 552536kb

input:

46012 72474 6895 931299293479
635558333906
151352929427
186830308154
201652909474
130684521091
862625793178
335372663856
565394770762
609752364488
636658378167
568072145317
23602174799
74849827839
567735061723
964475612065
721588322843
526921882143
141483206690
794896616456
923141155683
443983986019...

output:

737640936783 269480550026
785950579990 586907405473
274405996613 356240054012
164145774405 803378519477
613956922400 426121843045
509646717167 788278629379
95131481441 672600899832
720839818877 52329269906
131977527669 257593035330
737640936783 269480550026
202443098753 171133839273
188615102144 605...

result:

ok 13790 numbers

Test #6:

score: -100
Time Limit Exceeded

input:

4625 65696 87448 104757899185
324541097749
340894391228
353710640194
913290645927
500906082550
994613091630
486893604015
755863379632
795242109754
670982629049
89739557323
995677833835
622128974870
291590021762
74643709454
491030939322
504220665415
590951839890
749414110824
908656060298
831415689095...

output:

24017028596 61020984279
90036018081 8518714361
4807132724 94915889679
60642395760 99169995073
45912197521 30663794937
26807208137 73005099296
31855861883 38442189712
61377861921 69296474844
15633158436 24561226404
83188091024 101278210525
92283972576 51782451279
22904017080 27746280119
46615471334 7...

result:
English 繁體中文 简体中文

Server Time: 2024-12-03 23:24:35 | OpenSource Project