QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#391195#8543. Periodic Sequence275307894aAC ✓1526ms717012kbC++141.7kb2024-04-16 14:37:192024-04-16 14:37:19

Judging History

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

  • [2024-04-16 14:37:19]
  • 评测
  • 测评结果:AC
  • 用时:1526ms
  • 内存:717012kb
  • [2024-04-16 14:37:19]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=2e5+5,M=2000+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-8;const ll INF=1e18+7;mt19937 rnd(181766);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,p,B;ll ans[N],f[455][N];
void work(int i){
	static ll f[N];
	Me(f,0);f[0]=1;ans[i]++;
	ll tot=0,sum=1;
	for(int j=1;j<=n-i;j++){
		tot+=f[j-1];
		if(j>i) tot-=f[j-i-1];
		f[j]=tot%p;
		sum+=f[j];
		ans[j+i]+=sum%p;
	}
}
void Solve(){
	int i,j;scanf("%d%d",&n,&p);B=sqrt(n)+5;
	for(i=1;i<=B;i++) work(i);
	for(i=B+1;i<=n;i++) for(j=i;j<=n;j+=i) f[j/i-1][j]=(j/i&1?1:p-1);
	for(i=B;~i;i--){
		ll tot=0;
		for(j=0;j<=n;j++){
			if(j) tot+=f[i][j-1];
			f[i][j]=(f[i][j]+tot)%p;
			if(i) f[i-1][j]=(f[i-1][j]+tot)%p;
		}
	}
	for(i=1;i<=n;i++) f[0][i]=(f[0][i]+f[0][i-1])%p,printf("%lld ",(ans[i]+f[0][i])%p);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7704kb

input:

5 1000000007

output:

1 3 6 11 19 

result:

ok 5 number(s): "1 3 6 11 19"

Test #2:

score: 0
Accepted
time: 1508ms
memory: 715580kb

input:

200000 567894337

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 195106662 344669981 35619335 477103886 79913732 147415830 329955039 273123672 546045352 337527455 443978690 4597...

result:

ok 200000 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 70692kb

input:

2000 1000000009

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 480458646 875091002 588152874 869906045 159506110 218346934 346224469 716986623 864678016 300921504 68...

result:

ok 2000 numbers

Test #4:

score: 0
Accepted
time: 1500ms
memory: 716720kb

input:

200000 998244853

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 482213802 878601314 596928654 887457605 196364386 290308330 486636949 990790959 401755743 350504783 12...

result:

ok 200000 numbers

Test #5:

score: 0
Accepted
time: 1526ms
memory: 716364kb

input:

200000 1000000009

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 480458646 875091002 588152874 869906045 159506110 218346934 346224469 716986623 864678016 300921504 68...

result:

ok 200000 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 7684kb

input:

1 998244853

output:

1 

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 687ms
memory: 454984kb

input:

114514 1009999999

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 470458656 855091022 538152924 769906145 959506319 818347343 556225268 166988182 844681063 390927468 51...

result:

ok 114514 numbers

Test #8:

score: 0
Accepted
time: 1507ms
memory: 717012kb

input:

199998 500000003

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 263000996 480458649 375091005 88152886 369906072 159506173 218347057 346224709 216987088 364678928 300923295 688...

result:

ok 199998 numbers

Extra Test:

score: 0
Extra Test Passed