Submission #2382368
Source Code Expand
# include <bits/stdc++.h>
# define x first
# define y second
# define mp make_pair
// everything go according to my plan
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1 Y_U_NO_y1
# define left Y_U_NO_left
# define right Y_U_NO_right
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef long double ld;
const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
unsigned int seed;
asm ("rdtsc" : "=A"(seed));
srand (seed);
}
void files (string problem) {
if (fopen ((problem + ".in").c_str(),"r")) {
freopen ((problem + ".in").c_str(),"r",stdin);
freopen ((problem + ".out").c_str(),"w",stdout);
}
}
void localInput(const char in[] = "s") {
if (fopen (in, "r")) {
freopen (in, "r", stdin);
}
else
cerr << "Warning: Input file not found" << endl;
}
const int N = 4000 + 1;
ll dp[N][N], D[N][N];
int n, k;
int main()
{
# ifdef Local
//localInput();
# endif
Read_rap();
cin >> n >> k;
dp[0][0] = dp[1][0] = 1;
for (int i = 2; i <= 2*n; i++) {
for (int j = 0; 2*j <= i; j++)
dp[i][j] = (dp[i - 1][j] + (i >= 2 && j >= 1 ? dp[i - 2][j - 1] : 0)) % Mod;
}
int m = 2*k;
D[0][0] = 1;
for (int i = 1; i <= m; i++) {
int len = (n - (i + 1) / 2) / k + 1;
for (int s = n; s >= 0; s--) {
for (int j = 0; j <= s; j++) {
D[i][s] = (D[i - 1][s - j] * dp[len][j] + D[i][s]) % Mod;
}
}
}
vec<int> f (n + 1);
f[0] = 1;
for (int i = 1; i <= n; i++)
f[i] = (f[i - 1] * 1ll * i) % Mod;
int ans = 0;
for (int cnt = 0; cnt <= n; cnt++) {
int val = ((cnt & 1) ? -1 : +1) * D[m][cnt] * f[n - cnt] % Mod;
ans += val;
if (ans < 0)
ans += Mod;
if (ans >= Mod)
ans -= Mod;
}
cout << ans;
return 0;
}
// Coded by Z..
Submission Info
Submission Time |
|
Task |
D - ~K Perm Counting |
User |
Zhanbolat |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2301 Byte |
Status |
WA |
Exec Time |
2104 ms |
Memory |
134656 KB |
Compile Error
./Main.cpp: In function ‘void files(std::string)’:
./Main.cpp:37:50: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen ((problem + ".in").c_str(),"r",stdin);
^
./Main.cpp:38:52: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen ((problem + ".out").c_str(),"w",stdout);
^
./Main.cpp: In function ‘void localInput(const char*)’:
./Main.cpp:43:29: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen (in, "r", stdin);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2, example3, example4 |
All |
example0, example1, example2, example3, example4, handmade0, handmade1, handmade2, handmade3, handmade4, handmade5, handmade6, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, rand0, rand1, rand2, rand3, rand4, small0, small1, small2, supersmall0, supersmall1, supersmall2 |
Case Name |
Status |
Exec Time |
Memory |
example0 |
AC |
2 ms |
2304 KB |
example1 |
AC |
2 ms |
2304 KB |
example2 |
AC |
2 ms |
2304 KB |
example3 |
AC |
2 ms |
2304 KB |
example4 |
WA |
42 ms |
31488 KB |
handmade0 |
AC |
2 ms |
2304 KB |
handmade1 |
WA |
49 ms |
125440 KB |
handmade2 |
TLE |
2104 ms |
132736 KB |
handmade3 |
WA |
45 ms |
119040 KB |
handmade4 |
TLE |
2104 ms |
124288 KB |
handmade5 |
WA |
846 ms |
128640 KB |
handmade6 |
WA |
831 ms |
128640 KB |
maxrand0 |
TLE |
2104 ms |
130560 KB |
maxrand1 |
TLE |
2104 ms |
130560 KB |
maxrand2 |
TLE |
2104 ms |
134656 KB |
maxrand3 |
WA |
349 ms |
121984 KB |
maxrand4 |
TLE |
2104 ms |
130432 KB |
rand0 |
TLE |
2104 ms |
134656 KB |
rand1 |
WA |
544 ms |
60160 KB |
rand2 |
WA |
1289 ms |
86912 KB |
rand3 |
WA |
5 ms |
8704 KB |
rand4 |
TLE |
2104 ms |
124288 KB |
small0 |
WA |
40 ms |
25216 KB |
small1 |
WA |
12 ms |
17024 KB |
small2 |
WA |
65 ms |
29312 KB |
supersmall0 |
AC |
2 ms |
2304 KB |
supersmall1 |
AC |
2 ms |
2304 KB |
supersmall2 |
AC |
2 ms |
2304 KB |