CSES - Putka Open 2020 – 2/5

Submission details
Task:	Planeetat
Sender:	Gomhog
Submission time:	2020-09-25 23:45:18 +0300
Language:	C++ (C++11)
Status:	READY
Result:	49

Feedback
group	verdict	score
#1	ACCEPTED	24
#2	ACCEPTED	25
#3	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3	details
#2	ACCEPTED	0.01 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.01 s	1, 2, 3	details
#7	ACCEPTED	0.01 s	1, 2, 3	details
#8	ACCEPTED	0.01 s	1, 2, 3	details
#9	ACCEPTED	0.01 s	1, 2, 3	details
#10	ACCEPTED	0.01 s	1, 2, 3	details
#11	ACCEPTED	0.01 s	2, 3	details
#12	ACCEPTED	0.02 s	2, 3	details
#13	ACCEPTED	0.05 s	2, 3	details
#14	TIME LIMIT EXCEEDED	--	3	details
#15	TIME LIMIT EXCEEDED	--	3	details
#16	TIME LIMIT EXCEEDED	--	3	details
#17	TIME LIMIT EXCEEDED	--	3	details
#18	TIME LIMIT EXCEEDED	--	3	details
#19	TIME LIMIT EXCEEDED	--	3	details
#20	TIME LIMIT EXCEEDED	--	3	details
#21	TIME LIMIT EXCEEDED	--	3	details
#22	TIME LIMIT EXCEEDED	--	3	details
#23	TIME LIMIT EXCEEDED	--	3	details
#24	TIME LIMIT EXCEEDED	--	3	details
#25	TIME LIMIT EXCEEDED	--	3	details

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) {
	vector<ll> a1=a;
	vector<ll> a2=a;
	vector<ll> a3=a;
	vector<ll> a4=a;
	vector<ll> b1=b;
	vector<ll> b2=b;
	vector<ll> b3=b;
	vector<ll> b4=b;
	for (int i=0;i<=si;i++) {
		a1[i]%=mod1;
		a2[i]%=mod2;
		a3[i]%=mod3;
		a4[i]%=mod4;
		b1[i]%=mod1;
		b2[i]%=mod2;
		b3[i]%=mod3;
		b4[i]%=mod4;
	}
	vector<ll> c1=conv(a1,b1);
	vector<ll> c2=conv(a2,b2);
	vector<ll> c3=conv(a3,b3);
	vector<ll> c4=conv(a4,b4);
	for (int i=0;i<=si;i++) {
		c1[i]%=mod1;
		c2[i]%=mod2;
		c3[i]%=mod3;
		c4[i]%=mod4;
	}
	vector<ll> cc;
	for (int i=0;i<=si;i++) cc.push_back(rema(c1[i],c2[i],c3[i],c4[i]));
	return cc;
}

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` view save

correct output
`1` view save

user output
`1` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2` view save

correct output
`3 1` view save

user output
`3 1` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3` view save

correct output
`17 9 1` view save

user output
`17 9 1` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`4` view save

correct output
`142 95 18 1` view save

user output
`142 95 18 1` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5` view save

correct output
`1569 1220 305 30 1` view save

user output
`1569 1220 305 30 1` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`6` view save

correct output
`21576 18694 5595 745 45 ...` view save

user output
`21576 18694 5595 745 45 ...` view save

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`7` view save

correct output
`355081 334369 113974 18515 1540 ...` view save

user output
`355081 334369 113974 18515 1540 ...` view save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`8` view save

correct output
`6805296 6852460 2581964 484729 49840 ...` view save

user output
`6805296 6852460 2581964 484729 49840 ...` view save

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
`9` view save

correct output
`148869153 158479488 64727522 13591116 1632099 ...` view save

user output
`148869153 158479488 64727522 13591116 1632099 ...` view save

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
`10` view save

correct output
`660215659 85349908 783995053 409987640 55545735 ...` view save

user output
`660215659 85349908 783995053 409987640 55545735 ...` view save

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
`20` view save

correct output
`8033007 474885151 998010619 720259168 345757330 ...` view save

user output
`8033007 474885151 998010619 720259168 345757330 ...` Truncated

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
`50` view save

correct output
`637699856 613177596 194234103 50828885 988168359 ...` view save

user output
`637699856 613177596 194234103 50828885 988168359 ...` Truncated

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
`100` view save

correct output
`894456323 406549429 962038245 430640330 61348310 ...` view save

user output
`894456323 406549429 962038245 430640330 61348310 ...` Truncated

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`666` view save

correct output
`189730587 968711879 553374698 53051125 139917248 ...` view save

user output
(empty)

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`3333` view save

correct output
`79235821 455292218 627100211 591681254 695866885 ...` view save

user output
(empty)

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4991` view save

correct output
`482116496 245260697 151422537 180441123 318466624 ...` view save

user output
(empty)

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4992` view save

correct output
`141010647 787351178 684701591 872974815 631476284 ...` view save

user output
(empty)

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4993` view save

correct output
`504034249 588971460 281533415 928250892 416697844 ...` view save

user output
(empty)

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4994` view save

correct output
`266134603 90079109 544661648 812099750 17249410 ...` view save

user output
(empty)

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4995` view save

correct output
`833898560 663839791 109127071 321675160 86285359 ...` view save

user output
(empty)

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4996` view save

correct output
`721158645 167929822 115103278 491345159 114397872 ...` view save

user output
(empty)

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4997` view save

correct output
`691405606 436947443 82656395 514529009 783319673 ...` view save

user output
(empty)

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4998` view save

correct output
`829675470 688714502 189351950 956110193 20883331 ...` view save

user output
(empty)

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4999` view save

correct output
`343936737 47032567 190931571 827280581 160866637 ...` view save

user output
(empty)

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`5000` view save

correct output
`364064601 633559852 352848841 666954216 428009512 ...` view save

user output
(empty)

Putka Open 2020 – 2/5

Planeetat

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Tasks

Submissions (Gomhog)