CSES - Putka Open 2020 – 2/5 - Results
Submission details
Task:Planeetat
Sender:Gomhog
Submission time:2020-09-26 00:45:36 +0300
Language:C++ (C++11)
Status:READY
Result:49
Feedback
groupverdictscore
#1ACCEPTED24
#2ACCEPTED25
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s1, 2, 3details
#11ACCEPTED0.01 s2, 3details
#12ACCEPTED0.01 s2, 3details
#13ACCEPTED0.04 s2, 3details
#14--3details
#15--3details
#16--3details
#17--3details
#18--3details
#19--3details
#20--3details
#21--3details
#22--3details
#23--3details
#24--3details
#25--3details

Code

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second
typedef __int128 lll;

using namespace std;
typedef complex<ld> co;
const ld PI = atan2((ld)0,(ld)-1);

const ll M = 1e9+7;

const ll mod1 = 1e6+3;
const ll mod2 = 1e6+33;
const ll mod3 = 1e6+37;
const ll mod4 = 1e6+39;

int si;
ll fact[5010];
ll com[5050];
ll dp[5010][5010];



void fft(vector<co>&a, int n, int k) {
	vector<co> ww(n);
	ww[1]=co(1, 0);
	for (int t=0;t<k-1;t++) {
		co c=polar((ld)1, PI/n*(1<<(k-1-t)));
		int p2=(1<<t),p3=p2*2;
		for (int j=p2;j<p3;j++) ww[j*2+1]=(ww[j*2]=ww[j])*c;
	}
	for (int i=0;i<n;i++) {
		int u=0;
		for (int j=1;j<n;j*=2) {u*=2;if (i&j) u++;}
		if (i<u) swap(a[i], a[u]);
	}
	for (int l=1;l<n;l*=2) {
		for (int i=0;i<n;i+=l) {
			for (int it=0,j=i+l,w=l;it<l;it++,i++,j++) {
				co t=a[j]*ww[w++];
				a[j]=a[i]-t;
				a[i]=a[i]+t;
			}
		}
	}
}
vector<ll> conv(const vector<ll>& a, const vector<ll>& b) {
	int as=a.size(), bs=b.size();
	if (as*bs==0) return {};
	int k=0;
	while ((1<<k)<as+bs-1) k++;
	int n=1<<k;
	vector<co> c(n+1);
	for (int i=0;i<n;i++) {
		if (i<as) c[i]=a[i];
		if (i<bs) c[i]={c[i].real(), (ld)b[i]};
	}
	fft(c, n, k);
	c[n]=c[0];
	for (int i=0;i<=n-i;i++) {
		c[i]=conj(c[i]*c[i]-conj(c[n-i]*c[n-i]))*co(0,(ld)1/n/4);
		c[n-i]=conj(c[i]);
	}
	fft(c, n, k);
	vector<ll> r(as+bs-1);
	for (int i=0;i<as+bs-1;i++) r[i]=round(c[i].real());
	return r;
}

ll modPow(ll a, ll e, ll mod) {
	ll res=1;
	if (e==-1) return modPow(a,mod-2,mod);
	while (e>0) {
		if (e%2!=0) {
			res*=a;
			res%=mod;
		}
		a*=a;
		a%=mod;
		e/=2;
	}
	return res;
}

ll inv(ll a) {
	return modPow(a,M-2,M);
}

lll rema(lll a1, lll a2, lll a3, lll a4) {
	lll mmod= ((lll)mod1)*mod2*mod3*mod4;
	lll aa1=a1*(modPow((mod2*mod3*mod4)%mod1,mod1-2,mod1))*mod2*mod3*mod4;
	aa1%=mmod;
	lll aa2=a2*(modPow((mod1*mod3*mod4)%mod2,mod2-2,mod2))*mod1*mod3*mod4;
	aa2%=mmod;
	lll aa3=a3*modPow((mod1*mod2*mod4)%mod3,mod3-2,mod3)*mod1*mod2*mod4;
	aa3%=mmod;
	lll aa4=a4*modPow((mod1*mod2*mod3)%mod4,mod4-2,mod4)*mod1*mod2*mod3;
	aa4%=mmod;
	lll res=(aa1+aa2+aa3+aa4)%mmod;
	return res%M;
}

vector<ll> conv2(const vector<ll>& a, const vector<ll> b) {
	int n = a.size();
	if (n==0) return {};
	if (n==1) return {(a[0]*b[0])%M};
	int n1=n/2;
	int n2=n-n1;
	vector<ll> a1(n1);
	vector<ll> a2(n2);
	vector<ll> b1(n1);
	vector<ll> b2(n2);
	vector<ll> a3(n2);
	vector<ll> b3(n2);
	for (int i=0;i<n;i++) {
		if (i<n1) {
			a1[i]=a[i];
			b1[i]=b[i];
		} else {
			a2[i-n1]=a[i];
			a3[i-n1]=a[i];
			b2[i-n1]=b[i];
			b3[i-n1]=b[i];
		}
	}
	for (int i=0;i<n1;i++) {
		a3[i]+=a[i];
		b3[i]+=b[i];
		a3[i]%=M;
		b3[i]%=M;
	}
	vector<ll> c1=conv2(a1,b1);
	vector<ll> c2=conv2(a2,b2);
	vector<ll> c3=conv2(a3,b3);
	for (int i=0;i<2*n1-1;i++) {
		c3[i]-=c1[i];
	}
	for (int i=0;i<2*n2-1;i++) {
		c3[i]-=c2[i];
		while (c3[i]<0) c3[i]+=M;
	}
	vector<ll> c(2*n-1);
	for (int i=0;i<2*n1-1;i++) c[i]+=c1[i];
	for (int i=0;i<2*n2-1;i++) {
		c[i+n1]+=c3[i];
		c[i+n1]%=M;
	}
	for (int i=0;i<2*n2-1;i++) {
		c[i+2*n1]+=c2[i];
		c[i+2*n1]%=M;
	}
	return c;
}

void init() {
	fact[0]=1;
	for (int k=1;k<=si;k++) {
		fact[k]=(k*fact[k-1])%M;
		for (int j=1;j<=k;j++) {
			com[k]+=(modPow(k,k-j,M)*inv(fact[k-j]))%M;
			com[k]%=M;
		}
	}
	dp[0][0]=1;
	vector<ll> bb;
	for (int i=0;i<=si;i++) bb.push_back(com[i]);
	for (int j=1;j<=si;j++) {
		vector<ll> aa;
		for (int i=0;i<=si;i++) aa.push_back(dp[j-1][i]);
		vector<ll> cc=conv2(aa,bb);
		for (int i=0;i<=si;i++) dp[j][i]=(cc[i]*inv(i))%M;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>si;
	init();
	for (int j=1;j<=si;j++) cout<<(dp[j][si]*fact[si])%M<<"\n";
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
1

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
2

correct output
3
1

user output
3
1

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
3

correct output
17
9
1

user output
17
9
1

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
4

correct output
142
95
18
1

user output
142
95
18
1

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
5

correct output
1569
1220
305
30
1

user output
1569
1220
305
30
1

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
6

correct output
21576
18694
5595
745
45
...

user output
21576
18694
5595
745
45
...

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
7

correct output
355081
334369
113974
18515
1540
...

user output
355081
334369
113974
18515
1540
...

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
8

correct output
6805296
6852460
2581964
484729
49840
...

user output
6805296
6852460
2581964
484729
49840
...

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
9

correct output
148869153
158479488
64727522
13591116
1632099
...

user output
148869153
158479488
64727522
13591116
1632099
...

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
10

correct output
660215659
85349908
783995053
409987640
55545735
...

user output
660215659
85349908
783995053
409987640
55545735
...

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
20

correct output
8033007
474885151
998010619
720259168
345757330
...

user output
8033007
474885151
998010619
720259168
345757330
...
Truncated

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
50

correct output
637699856
613177596
194234103
50828885
988168359
...

user output
637699856
613177596
194234103
50828885
988168359
...
Truncated

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
100

correct output
894456323
406549429
962038245
430640330
61348310
...

user output
894456323
406549429
962038245
430640330
61348310
...
Truncated

Test 14

Group: 3

Verdict:

input
666

correct output
189730587
968711879
553374698
53051125
139917248
...

user output
(empty)

Test 15

Group: 3

Verdict:

input
3333

correct output
79235821
455292218
627100211
591681254
695866885
...

user output
(empty)

Test 16

Group: 3

Verdict:

input
4991

correct output
482116496
245260697
151422537
180441123
318466624
...

user output
(empty)

Test 17

Group: 3

Verdict:

input
4992

correct output
141010647
787351178
684701591
872974815
631476284
...

user output
(empty)

Test 18

Group: 3

Verdict:

input
4993

correct output
504034249
588971460
281533415
928250892
416697844
...

user output
(empty)

Test 19

Group: 3

Verdict:

input
4994

correct output
266134603
90079109
544661648
812099750
17249410
...

user output
(empty)

Test 20

Group: 3

Verdict:

input
4995

correct output
833898560
663839791
109127071
321675160
86285359
...

user output
(empty)

Test 21

Group: 3

Verdict:

input
4996

correct output
721158645
167929822
115103278
491345159
114397872
...

user output
(empty)

Test 22

Group: 3

Verdict:

input
4997

correct output
691405606
436947443
82656395
514529009
783319673
...

user output
(empty)

Test 23

Group: 3

Verdict:

input
4998

correct output
829675470
688714502
189351950
956110193
20883331
...

user output
(empty)

Test 24

Group: 3

Verdict:

input
4999

correct output
343936737
47032567
190931571
827280581
160866637
...

user output
(empty)

Test 25

Group: 3

Verdict:

input
5000

correct output
364064601
633559852
352848841
666954216
428009512
...

user output
(empty)