Task: | Planeetat |
Sender: | Gomhog |
Submission time: | 2020-09-26 00:45:36 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 49 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 24 |
#2 | ACCEPTED | 25 |
#3 | TIME LIMIT EXCEEDED | 0 |
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.01 s | 2, 3 | details |
#13 | ACCEPTED | 0.04 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) { 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: TIME LIMIT EXCEEDED
input |
---|
666 |
correct output |
---|
189730587 968711879 553374698 53051125 139917248 ... |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
3333 |
correct output |
---|
79235821 455292218 627100211 591681254 695866885 ... |
user output |
---|
(empty) |
Test 16
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4991 |
correct output |
---|
482116496 245260697 151422537 180441123 318466624 ... |
user output |
---|
(empty) |
Test 17
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4992 |
correct output |
---|
141010647 787351178 684701591 872974815 631476284 ... |
user output |
---|
(empty) |
Test 18
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4993 |
correct output |
---|
504034249 588971460 281533415 928250892 416697844 ... |
user output |
---|
(empty) |
Test 19
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4994 |
correct output |
---|
266134603 90079109 544661648 812099750 17249410 ... |
user output |
---|
(empty) |
Test 20
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4995 |
correct output |
---|
833898560 663839791 109127071 321675160 86285359 ... |
user output |
---|
(empty) |
Test 21
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4996 |
correct output |
---|
721158645 167929822 115103278 491345159 114397872 ... |
user output |
---|
(empty) |
Test 22
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4997 |
correct output |
---|
691405606 436947443 82656395 514529009 783319673 ... |
user output |
---|
(empty) |
Test 23
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4998 |
correct output |
---|
829675470 688714502 189351950 956110193 20883331 ... |
user output |
---|
(empty) |
Test 24
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
4999 |
correct output |
---|
343936737 47032567 190931571 827280581 160866637 ... |
user output |
---|
(empty) |
Test 25
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
5000 |
correct output |
---|
364064601 633559852 352848841 666954216 428009512 ... |
user output |
---|
(empty) |