題意：定義函數\(f(A,B) = \sum_{i=1}^n \max(A_i,B_i)\)，其中\(A\)和\(B\)都是長度為\(n\)的排列。給出\(n\)和\(k\)，問有多少對\((A,B)\)滿足\(f(A,B)\geq k\)。對\(10^9 + 7\)取模。
\(n \leq 50\)
首先，可以直接欽定\(A\)為\(1,2...n\)的一個排列，即對于所有\(i\)滿足\(A_i = i\)，最后答案再乘以\(n!\)。
然后就變成了對\(B\)這一個排列的計數問題。考慮函數\(f\)中有貢獻的只有較大值，我們不必計較其中的較小值具體是什么。這啟發我們在dp時把較小的數分配到較大的位置，并記錄其數量。
因此，我們令狀態\(dp_{i,j,k}\)表示當前從\(1\)開始放置了\(i\)個數，其中有\(j\)個數被分配到后面的位置，并且當前得到的函數值為\(k\)。當然，這里的函數值只包括\(\max(A_s,B_s) \leq i\)的值，這樣便于轉移。同樣地，當我們把一個數分配到后面的位置上時，我們不能輕易乘上一個系數（可分配的位置個數），因為分配不同的位置對答案的貢獻不同。
那么，對于第\(i+1\)個數以及位置，就有下面這些情況：
- \(i+1\)放在第\(i+1\)個位置。那么，j不變，k+=i，且只有一種方案。
- \(i+1\)放在前\(i\)個位置，第\(i+1\)個位置放了小于\(i+1\)的數。那么，j-=1，k+=2*i，且第\(i+1\)個數有\(j\)個位置可放，第\(i+1\)個位置也有\(j\)個數來放。因此有\(j^2\)種方案。
- \(i+1\)放在前\(i\)個位置，第\(i+1\)個位置放了大于\(i+1\)的數。那么，j不變，k+=i，且第\(i+1\)個數有\(j\)個位置可放，放在第\(i+1\)個位置的數未確定。因此有\(j\)種方案。
- \(i+1\)放在后面的位置，第\(i+1\)個位置放了小于\(i+1\)的數。那么，j不變，k+=i，且\(i+1\)未確定放在哪個位置，第\(i+1\)個位置有\(j\)個數來放。因此有\(j\)種方案。
- \(i+1\)放在后面的位置，第\(i+1\)個位置放了大于\(i+1\)的數。那么，j+=1，k不變，且\(i+1\)放在哪里，第\(i+1\)個位置放什么都是為確定的。因此只有一種方案。
時間復雜度\(O(n^4)\)。
#include <bits/stdc++.h>
using namespace std;const int MAXN = 55, MOD = (int)(1e9 + 7);
int dp[2][MAXN][MAXN * MAXN];
class LittleElephantAndPermutationDiv1 {
public:int getNumber( int N, int K );
};
int LittleElephantAndPermutationDiv1::getNumber(int N, int K) {int p = 1;memset(dp,0,sizeof dp);dp[0][0][0] = 1;for (int i = 1 ; i <= N ; ++ i, p ^= 1) {memset(dp[p],0,sizeof dp[p]);for (int j = 0 ; j < i ; ++ j) {for (int k = 0 ; k <= 2500 ; ++ k) {if (!dp[p^1][j][k]) continue;(dp[p][j][k+i] += dp[p^1][j][k]) %= MOD;if (j > 0) (dp[p][j-1][k+i+i] += 1ll * j * j * dp[p^1][j][k] % MOD) %= MOD;if (i < N) (dp[p][j][k+i] += 1ll * j * dp[p^1][j][k] % MOD) %= MOD;if (i < N) (dp[p][j][k+i] += 1ll * j * dp[p^1][j][k] % MOD) %= MOD;if (i < N) (dp[p][j+1][k] += dp[p^1][j][k]) %= MOD;}}}p ^= 1;int ret = 0;for (int i = K ; i <= 2500 ; ++ i)(ret += dp[p][0][i]) %= MOD;for (int i = 1 ; i <= N ; ++ i)ret = 1ll * ret * i % MOD;return ret;
}小結：這個dp的特色在于確定一個排列，從而同時對位置和值的分配dp，這樣可以解決一些較復雜的問題。
