Description

字母表的長度為\(m\)，用表中的字母構造長度為\(2n\)的字符串，要求同一種字母能同時出現(xiàn)在前\(n\)個字符中和后\(n\)個字符中。輸出方案數(shù)，結果模\(10^9+7\)。

Input

第一行給出用例組數(shù)\(T\)，每組用例給出兩個整數(shù)\(n\)和\(m\)。\(1 \leqslant n,m \leqslant 2000\)。

Output

對于每組用例，輸出方案數(shù)。

Sample Input

2 3 2 2 3

Sample Output

2 18

Solution

字母表中的每中字符有三種情況，在前\(n\)個字符中出現(xiàn)，在后\(n\)個字符中出現(xiàn)和不出現(xiàn)。設有\(p\)中字符在前\(n\)個字符中出現(xiàn)，\(q\)種字符在后\(n\)個字符中出現(xiàn)，則這種分配方案數(shù)量為
\[\binom{m}{p,q,m-p-q}=\frac{m!}{p! \cdot q! \cdot (m-p-q)!}\]

現(xiàn)在只需要解決，\(n\)個位置，\(m\)種字符，每種字符至少用一次的方案數(shù)。
設\(dp[i][j]\)表示前\(i\)個位置，\(j\)種字符每種至少用一種的方案數(shù)。
考慮前\(i-1\)個位置：

如果只用了\(j-1\)種字符，那么第\(i\)個位置就必須用最后一種字符，但最后一種字符具體是那個是不確定的，因此有\(j\)種情況。

如果j種字符全都出現(xiàn)過，那么第\(i\)個位置放任意一個字符都可以，同樣有\(j\)種情況。
綜上，
\[dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]) \cdot j\]

最終答案為
\[ans = \sum_{p,q \leqslant n,p+q \leqslant m}{\binom{m}{p,q,m-p-q} \cdot dp[n][p] \cdot dp[n][q]}\]
簡單化簡整理得
\[ans = m! \cdot \sum_{p,q \leqslant n,p+q \leqslant m}{dp[n][p] \cdot dp[n][q] \cdot inv(p!) \cdot inv(q!) \cdot inv((m-p-q)!)}\]
其中\(inv(i)\)表示\(i\)的逆元。\(O(n^2)\)的時間得到\(dp\)數(shù)組，\(O(n)\)的時間預處理\(0\)到\(2000\)的階乘，再用\(O(n)\)的時間得到\(0\)到\(2000\)階乘的逆元，枚舉每個\(p\)和\(q\)，累加即為答案。

Code

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const ll mod = 1e9 + 7; const int N = 2e3 + 10;ll power(ll a, ll b, ll mod) {ll ans = 1;while (b){if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans; }ll dp[N][N], fac[N], ifac[N];void init(int n) {fac[0] = 1;for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;ifac[0] = 1;for (int i = 1; i <= n; i++) ifac[i] = power(fac[i], mod - 2, mod);for (int i = 1; i <= n; i++) dp[i][1] = 1, dp[i][i] = fac[i];for (int i = 3; i <= n; i++)for (int j = 2; j < i; j++)dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) * j % mod; }int main() {init(2000);int T;scanf("%d", &T);while (T--){int n, m;scanf("%d%d", &n, &m);ll ans = 0;for (int p = 1; p <= n && p <= m; p++)for (int q = 1; q <= n && p + q <= m; q++){ll s = dp[n][p] % mod * dp[n][q] % mod;s = s * ifac[p] % mod * ifac[q] % mod * ifac[m - p - q] % mod;ans = (ans + s) % mod;}ans = ans * fac[m] % mod;printf("%lld\n", ans);}return 0; }

Link

http://acm.hdu.edu.cn/showproblem.php?pid=6143

轉載于:https://www.cnblogs.com/dadamrx/p/7384560.html

總結

以上是生活随笔為你收集整理的HDU 6143 Killer Names (组合数学+DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。