SRM416: CustomDice

ほとんど毎日考えてたけど結局わからなかったのでeditorial見た

(問題概要)
目の平均値がM以下になるようなサイコロの作り方は何通りあるか。
ただし全ての目は異なる。

(解法)
差分形式に式変形していくとDPに落とせるようだ。
これは難しいけど、汎用的に使えそうなテクニックなのでしっかりと理解したい。

#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class CustomDice {
public:
  int countDice(int M);
};

int CustomDice::countDice(int M){
  const int m = 6 * M - 21;
  const int mod = 1000000007;

  if(m < 0) return 0;

  vector<int> dp(m + 1, 1);

  for(int i = 1; i <= 6; i++){
    vector<int> next(m + 1);
    REP(j,m + 1){
      next[j] = dp[j];
      if(j >= i)
	next[j] += next[j - i];
      next[j] %= mod;
    }
    dp.swap(next);
  }

  return (30ll * dp[m]) % mod;
}