Codeforces403D

Codeforces403D

D. Beautiful Pairs of Numbers

分类： combinatorics dp

Description

定义这一类数对 (a1,b1),(a2,b2),⋯,(ak,bk) ( a 1 , b 1 ) , ( a 2 , b 2 ) , ⋯ , ( a k , b k ) $(a_1,b_1),(a_2,b_2),\cdots,(a_k,b_k)$ 是美丽的，当它满足：

• 1≤a1≤b1<a2≤b2<⋯<ak≤bk≤n 1 ≤ a 1 ≤ b 1 < a 2 ≤ b 2 < ⋯ < a k ≤ b k ≤ n $1\leq a_1\leq b_1 &#xff0c;其中 、n、k (1≤n,k≤1000) 、 n 、 k ( 1 ≤ n , k ≤ 1000 ) <script type="math/tex" id="MathJax-Element-5">、n、k\ (1\leq n,k\leq 1000)$ 是给定的整数。
• 所有的 b1−a1,b2−a2,⋯,bk−ak b 1 − a 1 , b 2 − a 2 , ⋯ , b k − a k $b_1-a_1,b_2-a_2,\cdots,b_k-a_k$ 都各不相同。

询问方案数，答案取模 109+7 10 9 + 7 $10^9+7$ 。

Solution

首先这个序列的长度不会大于50，因为 ∑i=050i>1000 ∑ i = 0 50 i > 1000 $\sum\limits_{i=0}^{50}i>1000$ ，假设 ci=bi−ai+1 c i = b i − a i + 1 $c_i=b_i-a_i+1$ ，其中 ci c i $c_i$ 表示第 i i $i$ 段的长度，变无序为有序（这样有利于设计动态规划子结构）使得 c1&lt;c2&lt;&#x22EF;&lt;ci,ci&#x2265;1" role="presentation" style="position: relative;">c1<c2<⋯<ci,ci≥1c1<c2<⋯<ci,ci≥1$c_1<c_2&lt;\cdots<c_i,c_i\ge 1$ ，而且有 ∑i=1kci≤n ∑ i = 1 k c i ≤ n $\sum\limits_{i=1}^k c_i\le n$ ，考虑动态规划统计 C C $C$ 的方案数，假设 f(i,j)" role="presentation" style="position: relative;">f(i,j)f(i,j)$f(i,j)$ 表示 C C $C$ 长度为 i" role="presentation" style="position: relative;">ii$i$ 段，且 ∑k=1ick=j ∑ k = 1 i c k = j $\sum\limits_{k=1}^i c_k = j$ 的方案数，那么它可以转移到 f(i,j+i) f ( i , j + i ) $f(i,j+i)$ 和 f(i+1,j+i+1) f ( i + 1 , j + i + 1 ) $f(i+1,j+i+1)$ ，也就是要么把这一整个 C C $C$ 的每个元素 +1" role="presentation" style="position: relative;">+1+1$+1$ （这样才能保证有序性成立），或者在它完成这个操作以后在前头补一个 c0=1 c 0 = 1 $c_0=1$ 变成 i+1 i + 1 $i+1$ 段的方案数。当然这样算的是已知 ∑C=len ∑ C = l e n $\sum C=len$ 的排列数，那么原区间长度是 n n $n$ 因此还有 n&#x2212;len" role="presentation" style="position: relative;">n−lenn−len$n-len$ 个空缺位置，我们要把他插入到 C C $C$ 中，这样的方案数是 (n&#x2212;len+kk)" role="presentation" style="position: relative;">(n−len+kk)(n−len+kk)$\binom{n-len+k}{k}$ ，可以枚举这个 len l e n $len$ 算出最后 C C $C$ 的答案。注意我们一开始是考虑 C" role="presentation" style="position: relative;">CC$C$ 有序得到的，因此最后答案还要乘上 k! k ! $k!$ 表示 C C <script type="math/tex" id="MathJax-Element-34">C</script> 的排列方案数。

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
typedef long long ll;
const int maxm = 1e3 + 5;
const int mod = 1e9 + 7;
/* head */
ll C[maxm][maxm], fac[maxm], f[maxm][maxm];
inline void init() {
    fac[0] = 1;
    rep(i, 1, maxm - 4) fac[i] = fac[i - 1] * i % mod;
    C[0][0] = 1;
    rep(i, 1, maxm - 4) {
        C[i][0] = C[i][i] = 1;
        rep(j, 1, i) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }
    f[0][0] = 1; // length = i, group = j
    rep(i, 1, maxm - 4) {
        rep(j, 1, i + 1) f[i][j] = (f[i - j][j] + f[i - j][j - 1]) % mod;
    }
}
inline void solve() {
    int n, k;
    scanf("%d%d", &n, &k);
    ll ans = 0;
    rep(len, k * (k + 1) / 2, n + 1) ans = (ans + f[len][k] * C[n - len + k][k]) % mod;
    printf("%lld\n", ans * fac[k] % mod);
}
int main() {
    init();
    int t;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}