QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736094#9120. Huge Segment Treeucup-team134TL 11ms12304kbC++175.5kb2024-11-12 00:29:282024-11-12 00:29:29

Judging History

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

  • [2024-11-12 00:29:29]
  • 评测
  • 测评结果：TL
  • 用时：11ms
  • 内存：12304kb
查看
  • [2024-11-12 00:29:28]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;

mt19937 rng(time(NULL));
const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=(1<<21);
namespace fft{
int proot=step(3,7*17*4);
int prekw[maxn];
bool isprek=false;
void prek(){
    if(isprek)return;
    isprek=true;
    prekw[0]=1;
    for(int i=1;i<maxn;i++){
        prekw[i]=mul(prekw[i-1],proot);
    }
}
void fft(vector<int>&a,bool invert){

    prek();

    int n=a.size();
    int j=0;
    for(int i=1;i<n;i++){
        int bit=n>>1;
        for(;bit&j;bit>>=1)j^=bit;
        j^=bit;
        if(i<j)swap(a[i],a[j]);
    }

    for(int len=2;len<=n;len<<=1){
        int hlen=len>>1;
        for(int i=0;i<n;i+=len){
            int curr=0;
            int d=maxn/len;
            if(invert)d=maxn-d;
            for(int j=0;j<hlen;j++){
                int pom1=a[i+j];
                int pom2=mul(a[i+j+hlen],prekw[curr]);

                a[i+j]=add(pom1,pom2);
                a[i+j+hlen]=sub(pom1,pom2);

                curr+=d;
                if(curr>=maxn)curr-=maxn;
            }
        }
    }

    if(invert){
        int invn=invv(n);
        for(int i=0;i<n;i++)a[i]=mul(a[i],invn);
    }

}

}

void print(vector<int> a){
	printf("[ ");
	for(int i=0;i<sz(a);i++){
		printf("%i",a[i]);
		if(i==sz(a)-1)printf(" ]");
		else printf(", ");
	}
}
void move(vector<int> &v,int s,bool smer){
	if(!smer)
	v.resize(s);
	fft::fft(v,smer);
	if(smer){
		while(sz(v)&&v.back()==0)v.pop_back();
	}
}
vector<int> mul(vector<int> a,vector<int> b){
    for(int i=0;i<sz(a);i++)a[i]=mul(a[i],b[i]);
    return a;
}
vector<int> add(vector<int> a,vector<int> b){
	for(int i=0;i<sz(a);i++)a[i]=add(a[i],b[i]);
    return a;
}
vector<int> add2(vector<int> a,vector<int> b){
	vector<int> c(max(sz(a),sz(b)));
	for(int i=0;i<sz(a);i++)c[i]=add(c[i],a[i]);
	for(int i=0;i<sz(b);i++)c[i]=add(c[i],b[i]);
    return c;
}
vector<int> divx(vector<int> &a){
	vector<int> c(sz(a)-1);
	for(int i=1;i<sz(a);i++)c[i-1]=a[i];
	return c;
}
int main()
{
	int k;
	cin >> k;
	vector<int> p0={0,1},p1={0,1};
	vector<int> f0={0,1},f1={0,0},f2={0,0};
	vector<int> np0,np1,nf0,nf1,nf2;
	vector<int> divp0,divp1;
	vector<int> v11={1,1};
	vector<int> v01m1={0,1,-1};
	vector<int> v0m1={0,-1};
	vector<int> v00m1={0,0,-1};
	vector<int> v2={2};
	int inv2=invv(2);
	vector<int> vinv2={inv2};
	vector<int> fl={2};
	
	auto trans1=[&](){
		int s=1;
		while(s<2*max({sz(p0),sz(p1),sz(f0),sz(f1),sz(f2)})){
			s*=2;
		}
		move(p0,s,0);
		move(v11,s,0);
		move(v01m1,s,0);
		move(p1,s,0);
		move(f0,s,0);
		move(f1,s,0);
		move(f2,s,0);
		move(v2,s,0);
		move(fl,s,0);
		np0=add(mul(p0,v11),v01m1);
		np1=mul(p1,v11);
		nf0=add(mul(p0,p0),add(mul(f0,v2),v01m1));
		nf1=add(mul(mul(p0,p1),v2),mul(f1,v2));
		nf2=add(mul(p1,p1),mul(f2,v2));
		fl=add(fl,fl);
		p0=np0;p1=np1;f0=nf0;f1=nf1;f2=nf2;
		move(p0,s,1);
		move(v11,s,1);
		move(v01m1,s,1);
		move(p1,s,1);
		move(f0,s,1);
		move(f1,s,1);
		move(f2,s,1);
		move(v2,s,1);
		move(fl,s,1);
	};
	auto trans2=[&](){
		divp0=add2(divx(p0),add2(p0,v0m1));
		divp1=divx(p1);
		int s=1;
		while(s<2*max({sz(p0),sz(p1),sz(f0),sz(f1),sz(f2)})){
			s*=2;
		}
		
		move(p0,s,0);
		move(v11,s,0);
		move(v01m1,s,0);
		move(p1,s,0);
		move(f0,s,0);
		move(f1,s,0);
		move(f2,s,0);
		move(v2,s,0);
		move(fl,s,0);
		move(divp0,s,0);
		move(divp1,s,0);
		move(vinv2,s,0);
		move(v00m1,s,0);
		move(v0m1,s,0);
		
		np0=add(add(mul(p0,divp1),p0), mul(p1,add(p0,v0m1)));
		
		divp1=add(divp1,p1);
		np1=mul(p1,divp1);
		
		nf0=add(f0,
		add(mul(f1,divp0),
		add(mul(f2,mul(divp0,divp0)),
		add(mul(f0,fl),
		mul(add(mul(p0,p0),v00m1),mul(fl,vinv2))
		))));
		
		nf1=add(mul(f1,divp1),
		add(mul(mul(f2,v2),mul(divp0,divp1)),
		add(mul(f1,fl),
		mul(mul(p0,p1),fl)
		)));
		
		nf2=add(mul(f2,mul(divp1,divp1)),
		add(mul(f2,fl),
		mul(mul(p1,p1),mul(fl,vinv2))
		));
		
		p0=np0;p1=np1;f0=nf0;f1=nf1;f2=nf2;
		fl=mul(fl,fl);
		
		move(p0,s,1);
		move(v11,s,1);
		move(v01m1,s,1);
		move(p1,s,1);
		move(f0,s,1);
		move(f1,s,1);
		move(f2,s,1);
		move(v2,s,1);
		move(fl,s,1);
		move(divp0,s,1);
		move(divp1,s,1);
		move(vinv2,s,1);
		move(v00m1,s,1);
		move(v0m1,s,1);
	};
	function<void(int)> rec=[&](int t){
		if(t==1)return;
		if(t%2==0){
			rec(t/2);
			trans2();
		}
		else{
			rec(t/2);
			trans2();
			//printf("p0: ");print(p0);printf("\np1: ");print(p1);printf("\nf0: ");print(f0);printf("\nf1: ");print(f1);printf("\nf2: ");print(f2);printf("\n");
			trans1();
		}
	};
	rec(k);
	/*for(int i=1;i<k;i++){
		trans1();
		//printf("p0: ");print(p0);printf("\np1: ");print(p1);printf("\nf0: ");print(f0);printf("\nf1: ");print(f1);printf("\nf2: ");print(f2);printf("\n");
	}*/
	for(int i=0;i<2*k-2;i++){
		int x=add(f0[i+1],add(f1[i+1],f2[i+1]));
		if(i==0)x=add(x,fl[0]);
		printf("%i ",x);
	}
	printf("\n");
	return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 12032kb

input:

2

output:

7 3

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 10ms
memory: 12036kb

input:

3

output:

15 14 6 1

result:

ok 4 tokens

Test #3:

score: 0
Accepted
time: 10ms
memory: 12084kb

input:

4

output:

31 43 36 19 6 1

result:

ok 6 tokens

Test #4:

score: 0
Accepted
time: 11ms
memory: 11988kb

input:

5

output:

63 110 132 114 70 30 8 1

result:

ok 8 tokens

Test #5:

score: 0
Accepted
time: 10ms
memory: 11984kb

input:

6

output:

127 255 384 448 400 272 136 47 10 1

result:

ok 10 tokens

Test #6:

score: 0
Accepted
time: 7ms
memory: 11960kb

input:

7

output:

255 558 978 1401 1610 1478 1066 589 240 68 12 1

result:

ok 12 tokens

Test #7:

score: 0
Accepted
time: 10ms
memory: 12044kb

input:

8

output:

511 1179 2292 3803 5250 5987 5576 4183 2482 1137 388 93 14 1

result:

ok 14 tokens

Test #8:

score: 0
Accepted
time: 7ms
memory: 11976kb

input:

9

output:

1023 2438 5088 9398 14896 20038 22632 21250 16406 10282 5144 2006 588 122 16 1

result:

ok 16 tokens

Test #9:

score: 0
Accepted
time: 7ms
memory: 12052kb

input:

10

output:

2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1

result:

ok 18 tokens

Test #10:

score: 0
Accepted
time: 10ms
memory: 12304kb

input:

11

output:

4095 10070 22782 48209 92140 156292 232068 298744 330926 313422 252186 171122 97008 45368 17200 5155 1176 192 20 1

result:

ok 20 tokens

Test #11:

score: -100
Time Limit Exceeded

input:

500000

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-11 15:44:11 | OpenSource Project