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; }