QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#737895#9120. Huge Segment Treeucup-team134TL 1993ms131028kbC++176.3kb2024-11-12 17:05:272024-11-12 17:05:27

Judging History

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

  • [2024-11-12 17:05:27]
  • 评测
  • 测评结果：TL
  • 用时：1993ms
  • 内存：131028kb
查看
  • [2024-11-12 17:05:27]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#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);}
namespace fft{
const int maxn=(1<<21);
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(", ");
	}
}

using int128=__int128_t;
vector<int> mul(vector<int> a,vector<int> b){
	if(sz(a)<400||sz(b)<400){
		vector<int128> ans(sz(a)+sz(b));
		vector<int>ret(sz(a)+sz(b));
		for(int i=0;i<sz(a);i++){
			for(int j=0;j<sz(b);j++){
				ans[i+j]+=(ll)a[i]*b[j];
			}
		}
		for(int i=0;i<(int)sz(a)+(int)sz(b)-1;i++){
            ret[i]=ans[i]%mod;
		}
		return ret;
	}
    int sz=1;
    while(sz<a.size()+b.size())sz*=2;
    a.resize(sz);
    b.resize(sz);
    fft::fft(a,false);
    fft::fft(b,false);
    for(int i=0;i<sz;i++)a[i]=mul(a[i],b[i]);
    fft::fft(a,true);
    while(a.size() && a.back()==0)a.pop_back();
    return a;
}
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> mul2(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> mul2(vector<int> a,int b){
    for(int i=0;i<sz(a);i++)a[i]=mul(a[i],b);
    return a;
}
vector<int> add2(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> add(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()
{

    ///freopen("test.txt","r",stdin);
	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;
	int inv2=invv(2);
	int fl=2;
	int s;
	auto trans1=[&](){
		np0=add(mul(p0,{1,1}),{0,1,-1});
		np1=mul(p1,{1,1});
		move(p0,s,0);
		move(p1,s,0);
		auto p00=mul2(p0,p0);
		auto p01=mul2(p0,p1);
		auto p11=mul2(p1,p1);
		move(p0,s,1);
		move(p1,s,1);
		move(p01,s,1);
		move(p00,s,1);
		move(p11,s,1);

		nf0=add(p00,add(mul(f0,{2}),{0,1,-1}));
		nf1=add(mul(p01,{2}),mul(f1,{2}));
		nf2=add(p11,mul(f2,{2}));
		fl=add(fl,fl);
		p0=np0;p1=np1;f0=nf0;f1=nf1;f2=nf2;
	};
	auto trans2=[&](){
		divp0=add(divx(p0),add(p0,{0,-1}));
		divp1=divx(p1);

		auto xx=add(p0,{0,-1});
		move(p0,s,0);
		move(p1,s,0);
		move(divp1,s,0);
		move(divp0,s,0);
		move(f0,s,0);
		move(f1,s,0);
		move(f2,s,0);
		move(xx,s,0);
		
		np0=add2(mul2(p0,divp1),add2(mul2(p1,xx),p0));
		move(np0,s,1);

		divp1=add2(divp1,p1);
		
		np1=mul2(p1,divp1);
		move(np1,s,1);

		auto f1divp0=mul2(f1,divp0);
		auto f2divp02=mul2(f2,mul2(divp0,divp0));
		auto p0p0=mul2(p0,p0);
		auto f1divp1=mul2(f1,divp1);
		auto f2divp0divp1=mul2(f2,mul2(divp0,divp1));
		auto p0p1=mul2(p0,p1);
		auto f2divp1divp1=mul2(f2,mul2(divp1,divp1));
		auto p1p1=mul2(p1,p1);
		
		move(f1,s,1);
		move(f2,s,1);
		
		move(f1divp1,s,1);
		move(f2divp0divp1,s,1);
		move(p0p1,s,1);
		move(f2divp1divp1,s,1);
		move(p1p1,s,1);
		
		nf0=add2(f0,add2(f1divp0,add2(f2divp02,add2(mul2(f0,fl),mul2(p0p0,mul(fl,inv2))))));
		move(nf0,s,1);
		nf0=add(nf0,{0,0,-mul(fl,inv2)});

		nf1=add(f1divp1,
		add(mul({2},f2divp0divp1),
		add(mul({fl},f1),
		mul({fl},p0p1)
		)));

		nf2=add(f2divp1divp1,
		add(mul({fl},f2),
		mul({mul(fl,inv2)},p1p1)
		));

		p0=np0;p1=np1;f0=nf0;f1=nf1;f2=nf2;
		fl=mul(fl,fl);
	};
	int iter=0;
	function<void(int)> rec=[&](int t){
		if(t==1)return;
		if(t%2==0){
			rec(t/2);
			s=1;
			while(s<2*t-1)s*=2;
			ll start=clock();
			trans2();
			//if(k>10)printf("Iter %i: %lld ms\n",iter++,clock()-start);
		}
		else{
			rec(t/2);
			ll start=clock();
			s=1;
			while(s<2*t-1)s*=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();
			//if(k>10)printf("Iter %i: %lld ms\n",iter++,clock()-start);
		}
	};
	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");
	}*/
	//if(k<=10){
	vector<int> ans=add(f0,add(add(f1,{0,fl}),f2));
	for(int i=0;i<2*k-2;i++){
		printf("%i ",ans[i+1]);
	}
	printf("\n");
	//}
	return 0;
}
源文件, 语言: C++17

詳細信息

Test #1:

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

input:

2

output:

7 3

result:

ok 2 tokens

Test #2:

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

input:

3

output:

15 14 6 1

result:

ok 4 tokens

Test #3:

score: 0
Accepted
time: 3ms
memory: 12104kb

input:

4

output:

31 43 36 19 6 1

result:

ok 6 tokens

Test #4:

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

input:

5

output:

63 110 132 114 70 30 8 1

result:

ok 8 tokens

Test #5:

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

input:

6

output:

127 255 384 448 400 272 136 47 10 1

result:

ok 10 tokens

Test #6:

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

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: 7ms
memory: 12136kb

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: 12408kb

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: 12104kb

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: 11ms
memory: 12112kb

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: 0
Accepted
time: 1993ms
memory: 131028kb

input:

500000

output:

390220183 534638705 182393715 303662724 176884209 76063846 314206329 970463075 138271132 869076105 902568877 121426660 599330372 720576343 535733058 609095360 499854676 427738345 789967637 850801793 767689169 103101879 573005863 597231280 725469375 299015007 178535851 966708332 305629 940093777 7830...

result:

ok 999998 tokens

Test #12:

score: 0
Accepted
time: 590ms
memory: 38092kb

input:

72787

output:

863191949 852718765 363831665 964981186 487891193 263854743 37522806 18985671 265243835 698211861 413341848 452649596 684165069 41891590 781946347 633808644 213891845 90859042 654886506 681500079 853399752 536402628 160278411 189221861 144879826 449123001 395247186 477700669 245829076 740028721 3991...

result:

ok 145572 tokens

Test #13:

score: 0
Accepted
time: 137ms
memory: 18720kb

input:

29621

output:

625188972 186328126 837166229 677006047 662339899 556164288 627678499 464879587 574719635 860749906 37224574 952205162 612486418 67731480 127518779 222659320 311864904 739493528 441208728 656349279 675863661 193365665 871786422 429030382 542544944 65332274 279132780 886986640 23673291 260179258 1458...

result:

ok 59240 tokens

Test #14:

score: -100
Time Limit Exceeded

input:

287834

output:

result:
English 繁體中文 简体中文

伺服器時間: 2024-12-12 04:15:53 | 開源專案