Submission #520381

#	Time	Username	Problem	Language	Result	Execution time	Memory
520381		Alex_tz307	NoM (RMI21_nom)	C++17	100 / 100	49 ms	364 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int kN = 2e3;
int f[1 + 2 * kN], invf[1 + 2 * kN], cnt[1 + kN], dp[2][1 + kN];

void multSelf(int &x, int y) {
  x = (int64_t)x * y % mod;
}

int mult(int x, int y) {
  multSelf(x, y);
  return x;
}

void addSelf(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

int invers(int x) {
  int ans = 1, n = mod - 2;
  while (n) {
    if (n % 2) {
      multSelf(ans, x);
    }
    multSelf(x, x);
    n /= 2;
  }
  return ans;
}

void computeFactorials(int n) {
  f[0] = 1;
  for (int i = 1; i <= 2 * n; ++i) {
    f[i] = mult(f[i - 1], i);
  }
  invf[2 * n] = invers(f[2 * n]);
  for (int i = 2 * n - 1; i >= 0; --i) {
    invf[i] = mult(invf[i + 1], i + 1);
  }
}

int arr(int n, int k) {
  return mult(f[n], invf[n - k]);
}

int nck(int n, int k) {
  return mult(f[n], mult(invf[k], invf[n - k]));
}

void testCase() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= 2 * n; ++i) {
    ++cnt[1 + i % m];
  }
  computeFactorials(n);
  int sum = 0;
  dp[0][0] = dp[1][0] = 1;
  for (int i = 1, t = 1; i <= m; ++i, t ^= 1) {
    sum += cnt[i];
    for (int j = 1; j * 2 <= sum; ++j) {
      dp[t][j] = 0;
      for (int k = 0; k <= j && 2 * k <= cnt[i]; ++k) {
        addSelf(dp[t][j], mult(dp[t ^ 1][j - k], mult(arr(cnt[i], 2 * k), nck(j, k))));
      }
    }
  }
  int ans = f[2 * n];
  for (int i = 1; i <= n; ++i) {
    int contribution = mult(nck(n, i), mult(f[2 * n - 2 * i], dp[m % 2][i]));
    if (i % 2) {
      contribution = mod - contribution;
    }
    addSelf(ans, contribution);
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48