Submission #2382284
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;
int 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);
dp[i][j] %= Mod;
}
}
int m = min (n, 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] * 1ll * dp[len][j]) % Mod + 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 |
2362 Byte |
Status |
WA |
Exec Time |
2104 ms |
Memory |
67456 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 |
1 ms |
2304 KB |
example2 |
AC |
2 ms |
2304 KB |
example3 |
AC |
2 ms |
2304 KB |
example4 |
WA |
43 ms |
17152 KB |
handmade0 |
AC |
2 ms |
2304 KB |
handmade1 |
WA |
39 ms |
63872 KB |
handmade2 |
TLE |
2104 ms |
67456 KB |
handmade3 |
WA |
35 ms |
61696 KB |
handmade4 |
TLE |
2104 ms |
65152 KB |
handmade5 |
WA |
915 ms |
65024 KB |
handmade6 |
WA |
897 ms |
65024 KB |
maxrand0 |
TLE |
2104 ms |
67328 KB |
maxrand1 |
TLE |
2104 ms |
65280 KB |
maxrand2 |
TLE |
2104 ms |
67328 KB |
maxrand3 |
WA |
369 ms |
62208 KB |
maxrand4 |
TLE |
2104 ms |
67328 KB |
rand0 |
TLE |
2104 ms |
67328 KB |
rand1 |
WA |
518 ms |
29824 KB |
rand2 |
WA |
752 ms |
35968 KB |
rand3 |
WA |
4 ms |
4736 KB |
rand4 |
TLE |
2104 ms |
63104 KB |
small0 |
WA |
43 ms |
15232 KB |
small1 |
WA |
12 ms |
11136 KB |
small2 |
WA |
43 ms |
13184 KB |
supersmall0 |
AC |
2 ms |
2304 KB |
supersmall1 |
AC |
1 ms |
2304 KB |
supersmall2 |
AC |
1 ms |
2304 KB |