Submission #1224699
Source Code Expand
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))
#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif
typedef long long ll;
typedef long double ld;
const int inf = (int) 1.01e9;
const ld eps = 1e-11;
const ld pi = acos(-1.0L);
mt19937 mrand(random_device{} ());
int rnd(int x) {
return mrand() % x;
}
const int mod = (int) 1e9 + 7;
void add(int & x, int y) {
if ((x += y) >= mod) {
x -= mod;
}
}
int sum(int x, int y) {
add(x, y);
return x;
}
int mult(int x, int y) {
return (ll) x * y % mod;
}
int power(int x, ll p) {
int res = 1;
while (p) {
if (p & 1) {
res = mult(res, x);
}
x = mult(x, x);
p >>= 1;
}
return res;
}
int inv(int x) {
return power(x, mod - 2);
}
void precalc() {
}
int n, m;
bool read() {
if (scanf("%d%d", &n, &m) < 2) {
return false;
}
return true;
}
void solve() {
int res = 0;
vector<int> c(2 * m + 1);
c[0] = 1;
for (int i = 1; i <= 2 * m; i++) {
c[i] = mult(c[i - 1], 2 * m - i + 1);
c[i] = mult(c[i], inv(i));
}
for (int diff = n - 1; diff <= n; diff++) {
int cur = 0;
int step = 2 * (diff + 1);
vector<int> v(step);
for (int i = 0; i <= 2 * m; i++) {
add(v[i % step], c[i]);
}
int val = 0;
for (int i = m; i <= m + diff; i++) {
add(val, v[i % step]);
}
for (int i = m + step / 2; i <= m + step / 2 + diff; i++) {
add(val, mod - v[i % step]);
}
for (int it = 0; it <= diff; it++) {
add(cur, val);
add(val, v[((m - it - 1) % step + step) % step]);
add(val, mod - v[(m + diff - it) % step]);
add(val, mod - v[((m - it - 1 + step / 2) % step + step) % step]);
add(val, v[(m + diff - it + step / 2) % step]);
}
if ((diff - n) & 1) {
add(res, mod - cur);
} else {
add(res, cur);
}
}
printf("%d\n", res);
}
int main() {
precalc();
#ifdef DEBUG
assert(freopen("text.in", "r", stdin));
assert(freopen("text.out", "w", stdout));
#endif
while (read()) {
solve();
#ifdef DEBUG
eprintf("Time: %.3f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Piling Up |
User |
StanislavErshov |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
2424 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
900 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
2 ms |
256 KB |
subtask_1_01.txt |
AC |
2 ms |
256 KB |
subtask_1_02.txt |
AC |
2 ms |
256 KB |
subtask_1_03.txt |
AC |
2 ms |
256 KB |
subtask_1_04.txt |
AC |
2 ms |
256 KB |
subtask_1_05.txt |
AC |
2 ms |
256 KB |
subtask_1_06.txt |
AC |
2 ms |
256 KB |
subtask_1_07.txt |
AC |
2 ms |
256 KB |
subtask_1_08.txt |
AC |
2 ms |
256 KB |
subtask_1_09.txt |
AC |
2 ms |
256 KB |
subtask_1_10.txt |
AC |
2 ms |
256 KB |
subtask_1_11.txt |
AC |
2 ms |
256 KB |
subtask_1_12.txt |
AC |
2 ms |
256 KB |
subtask_1_13.txt |
AC |
2 ms |
256 KB |
subtask_1_14.txt |
AC |
2 ms |
256 KB |
subtask_1_15.txt |
AC |
2 ms |
256 KB |
subtask_1_16.txt |
AC |
2 ms |
256 KB |
subtask_1_17.txt |
AC |
2 ms |
256 KB |
subtask_1_18.txt |
AC |
2 ms |
256 KB |
subtask_1_19.txt |
AC |
2 ms |
256 KB |
subtask_1_20.txt |
AC |
2 ms |
256 KB |
subtask_1_21.txt |
AC |
2 ms |
256 KB |
subtask_1_22.txt |
AC |
2 ms |
256 KB |
subtask_1_23.txt |
AC |
2 ms |
256 KB |
subtask_1_24.txt |
AC |
2 ms |
256 KB |
subtask_1_25.txt |
AC |
1 ms |
256 KB |
subtask_1_26.txt |
AC |
2 ms |
256 KB |
subtask_1_27.txt |
AC |
1 ms |
256 KB |