Submission #856760

#	Time	Username	Problem	Language	Result	Execution time	Memory
856760		raresmihai	NoM (RMI21_nom)	C++17	100 / 100	130 ms	756 KiB

Main

#include <iostream>

#define MOD 1000000007
#define MAXN 10000
using namespace std;

long long dp[MAXN + 1][2];
int val[MAXN];
long long fact[MAXN + 1];
long long invFact[MAXN + 1];
int m, n;

long long makeInv(long long x) {
  int pow;
  long long ans;

  ans = 1;
  pow = MOD - 2;
  while ( pow ) {
    if ( pow % 2 ) {
      ans = (ans * x) % MOD;
    }

    pow /= 2;
    x = (x * x) % MOD;
  }

  return ans;
}

void makeFact() {
  long long ans;
  int i;

  ans = 1;
  fact[0] = invFact[0] = 1;
  for ( i = 1; i <= MAXN; i++ ) {
    ans = (ans * i) % MOD;
    fact[i] = ans;
    invFact[i] = makeInv(ans);
  }
}

long long makeCombi(int n, int choose) {
  if ( n >= choose && choose >= 0 ) {
    return (((fact[n] * invFact[choose]) % MOD) * invFact[n - choose]) % MOD;
  }
  return 0;
}

long long makeChoose(int n, int choose) {
  if ( n >= choose && choose >= 0 ) {
    return (fact[n] * invFact[n - choose]) % MOD;
  }
  return 0;
}

long long calcAns(int a, int b, int x) { ///from a to b(x from b have pair); we choose from a increasing, other does not matter
  if ( a >= x && x >= 0 && b >= x ) {
    return (makeCombi(a, x) * makeChoose(b, x)) % MOD;
  }
  return 0;
}

void smh() {
  int currNr, i, pos, i2, i3;

  //makeFact();

  //scanf("%d%d", &n, &m);

  n *= 2;
  for ( i = 0; i < n; i++ ) {
    val[i % m]++;
  }

  pos = 0;
  dp[0][0] = 1;
  currNr = 0;
  for ( i = 0; i < m; i++ ) {
    pos ^= 1;

    for ( i2 = 0; i2 <= MAXN; i2++ ) {
      dp[i2][pos] = 0;
    }

    for ( i2 = 0; i2 <= val[i]; i2++ ) { //how many we pair
      for ( i3 = 0; i3 <= currNr; i3++ ) { //how many are used
        dp[i3 + 2 * i2][pos] = (dp[i3 + 2 * i2][pos] + (dp[i3][pos ^ 1] * calcAns(currNr - i3, val[i], i2)) % MOD) % MOD;
      }
    }

    currNr += val[i];
  }

  long long pow;

  pow = 1;
  for ( i = 1; i <= n / 2; i++ ) {
    pow = ((long long) pow * 2) % MOD;
  }

  printf("%lld\n", (((dp[n][pos] * fact[n / 2]) % MOD) * pow) % MOD);
}

int main() {
  makeFact();

  scanf("%d%d", &n, &m);

  smh();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~

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