//1,2,3,…の順で挿入して順列を作る。このときの樹形図を書いて、反転数の増加量を枝に記入してみる。 //すると、合計がK以下になるように「{0},{0,1},{0,1,2},…,{0,1,…,N-1}の中からそれぞれ1要素ずつ選ぶ」方法の数、が答えになると分かる。 //選んでいく過程で使用する情報は、「今いくつめの{}から選んでいるか?, 今までの和」の2つなので、この2つをキーにして漸化式が立ちそうだと分かる。 //dp[i][j] = {0},{0,1},…,{0,1,…,i}の中からそれぞれ1要素ずつ選んで、選んだ要素の合計をjにする方法の数 //とおくと、dp[0][0] = 1として、以下の漸化式を(i, j)昇順に回せばよいことが分かる。(個人的には、DAGの経路数をイメージすると分かりやすいです。) //dp[i + 1][j + [0,1,…,i+1]] += dp[i][j] //適宜余りを取りつつ更新すると、O(N^4)またはO(N^3K)で間に合わない。ここで、更新が「区間加算」になっていることに注目して、各iについてimos法で更新すると //O(N^3)またはO(N^2 K)で間に合う。 #include using namespace std; int mod = 1000000007; int n, K; int dp[300][50000]; int main() { int i, j; cin >> n >> K; dp[0][0] = 1; for (i = 0; i < n - 1; i++) { for (j = 0; j <= i * (i + 1) / 2; j++) { dp[i + 1][j] += dp[i][j]; if (dp[i + 1][j] >= mod) dp[i + 1][j] -= mod; dp[i + 1][j + i + 2] += mod - dp[i][j]; if (dp[i + 1][j] >= mod) dp[i + 1][j] -= mod; } for (j = 1; j <= (i + 1) * (i + 2) / 2; j++) { dp[i + 1][j] += dp[i + 1][j - 1]; if (dp[i + 1][j] >= mod) dp[i + 1][j] -= mod; } } int ans = 0; for (j = 0; j <= K; j++) { ans += dp[n - 1][j]; if (ans >= mod) ans -= mod; } cout << ans << endl; return 0; }