TopCoder SRM 572 Div2 Hard: DistinctRemainders

解法

dp[sum][m] := m個の相異なる非負整数からなる合計がsumとなる増加数列の個数。
この並び方は m! 通りある。
さらにこの数列の上に blocks 個の M の倍数を積んでいく時、重複組合せより通りある。

逆元から組み合わせを求めるテクを使うと大きい数字にも対応できる。

コード

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

int MOD = 1e9 + 7;

class InverseCombination {
  vector<int64_t> rev, revt;
  const int C = 200;

 public:
  InverseCombination() {
    rev.assign(C + 1, 0), revt.assign(C + 1, 0);
    rev[1] = 1;
    for (int i = 2; i <= C; i++) rev[i] = rev[MOD % i] * (MOD - MOD / i) % MOD;

    revt[0] = 1;
    for (int i = 1; i <= C; i++) revt[i] = revt[i - 1] * rev[i] % MOD;
  }

  // Get nCm
  int64_t get(int64_t n, int64_t m) {
    assert(m < revt.size());
    int64_t ret = revt[m];
    for (int i = 0; i < m; ++i) ret = (ret * ((n - i) % MOD)) % MOD;
    return ret;
  }
};

class DistinctRemainders {
 public:
  int howMany(long long N, int M) {
    vector<vector<int64_t>> dp(M * M, vector<int64_t>(M + 1, 0));
    dp[0][0] = 1;

    for (int m = 0; m < M; ++m)
      for (int x = m * (m + 1) / 2; x >= 0; --x)
        for (int y = m; y >= 0; --y) {
          dp[x + m][y + 1] += dp[x][y];
          dp[x + m][y + 1] %= MOD;
        }

    vector<int64_t> fact(M + 1, 0);
    fact[0] = 1;
    for (int i = 0; i < M; ++i) fact[i + 1] = (fact[i] * (i + 1)) % MOD;

    InverseCombination combination;

    int64_t ans = 0;
    for (int sum = 0; sum <= M * (M - 1) / 2; ++sum) {
      if (sum > N) continue;
      if ((N - sum) % M) continue;
      int64_t blocks = (N - sum) / M;
      for (int m = 1; m <= M; ++m) {
        int64_t addition = dp[sum][m];
        addition = (addition * fact[m]) % MOD;
        addition = (addition * combination.get(blocks + m - 1, m - 1)) % MOD;
        ans = (ans + addition) % MOD;
      }
    }

    return ans;
  }
};