|
| Code Submission Evaluation System |
Login |
HIIT Open 2016
|
Start: | 2016-05-28 11:00:00 |
End: | 2016-05-28 16:00:00 |
|
|
Tasks | Messages | Scoreboard | Statistics
CSES - HIIT Open 2016 - ResultsHistory |
---|
2016-05-28 15:04:41 | ✓ |
Task: | Kaaleppi's puzzle |
Sender: | Game of Nolife |
Submission time: | 2016-05-28 15:04:41 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
Test results
test | verdict | time (s) | |
#1 | ACCEPTED | 0.06 / 5.00 | details |
#2 | ACCEPTED | 0.06 / 5.00 | details |
#3 | ACCEPTED | 0.05 / 5.00 | details |
Code
#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
const ll M=1e9+7;
ll f[1010];
ll g[1010];
ll a[1010],b[1010];
const ll i2=5e8+4;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
a[2]=2;
b[2]=0;
g[2]=2;
for (int i=3;i<=1000;i++) {
a[i]=(b[i-1]*i2)%M;
b[i]=(2*a[i-1]+2*b[i-1])%M;
g[i]=(a[i]+b[i])%M;
}
// for (int i=2;i<=6;i++) cout<<g[i]<<endl;
// cout<<"--"<<endl;
f[1]=1;
f[2]=0;
f[3]=0;
for (ll i=4;i<=1000;i++) {
f[i]=((i-2)*f[i-1])%M;
for (ll k=2;k<i;k++) {
ll hlp=(g[k]*(i-k)-2)%M;
hlp*=f[i-k];
hlp%=M;
f[i]+=hlp;
f[i]%=M;
}
}
// for (int i=1;i<=6;i++) cout<<f[i]<<endl;
int t;
cin>>t;
for (int i=0;i<t;i++) {
int n;
cin>>n;
cout<<f[n]<<"\n";
}
}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
... |
correct output |
---|
1
0
0
2
14
90
646
5242
47622
479306
5296790
63779034
831283558
661506141
203183149
878035968
456796197
911763426
428159996
654286749
... |
user output |
---|
1
0
0
2
14
90
646
5242
47622
479306
5296790
63779034
831283558
661506141
203183149
878035968
456796197
911763426
428159996
654286749
... |
Test 2
Verdict: ACCEPTED
input |
---|
20
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
... |
correct output |
---|
436438246
92806357
21003215
151460560
326076265
424575830
228692865
201160758
157874096
500271360
735748839
456205691
368613063
327270428
147787261
753800152
993342525
445553830
110101472
711794305
... |
user output |
---|
436438246
92806357
21003215
151460560
326076265
424575830
228692865
201160758
157874096
500271360
735748839
456205691
368613063
327270428
147787261
753800152
993342525
445553830
110101472
711794305
... |
Test 3
Verdict: ACCEPTED
input |
---|
20
352
478
99
92
723
608
491
441
38
12
905
907
42
558
218
960
555
381
518
... |
correct output |
---|
552481822
246955132
94569313
829032275
94621650
839827603
628162266
795849857
836338597
63779034
646544931
898906053
521761952
479901674
111527011
499723151
220091149
904428111
159152418
190829541
... |
user output |
---|
552481822
246955132
94569313
829032275
94621650
839827603
628162266
795849857
836338597
63779034
646544931
898906053
521761952
479901674
111527011
499723151
220091149
904428111
159152418
190829541
... |