CodeForces 301 E. Yaroslav and Arrangements

E. Yaroslav and Arrangements Round 182

time limit per test 3 seconds
memory limit per test 256 megabytes

Yaroslav calls an array of r integers a1, a2, …, ar good, if it meets the following conditions: \(|a_1 - a_2| = 1, |a_2 - a_3| = 1, …, |a_{r-1} - a_r| = 1, |a_r - a_1| = 1\), at that \(a_1 = \min _{i=1}^r a_i \).

An array of integers \(b_1, b_2, …, b_r\) is called great, if it meets the following conditions:

The elements in it do not decrease (\(b_i \le b_{i+1}\)).
If the inequalities 1 ≤ r ≤ n and 1 ≤ bi ≤ m hold.
If we can rearrange its elements and get at least one and at most k distinct good arrays.
Yaroslav has three integers n, m, k. He needs to count the number of distinct great arrays. Help Yaroslav!

As the answer may be rather large, print the remainder after dividing it by 1,000,000,007.

Two arrays are considered distinct if there is a position in which they have distinct numbers.

Input

The single line contains three integers n, m, k (1 ≤ n, m, k ≤ 100).

Output

In a single line print the remainder after dividing the answer to the problem by number 1,000,000,007.

Examples

input

3 3 3

output

2

Solution

题目大意:求出有多少个b使得其所有排列中符合a的个数小于等于k。

像这种求方案数小于等于k的方案数的题目,就是DP套DP了。下面给出做法:

波浪形的不好做,我们不妨只提出上升的来,那么这些上升的肯定对应唯一的b。
考虑将数字一个一个插入。通过枚举数字和个数来统计方案数小于等于k的方案数(有点绕。。。)
考虑状态如何设计?

  1. 我们必须清楚当前最大数是多少 这样才知道下一个应该放什么 记为i
  2. 我们必须清楚放了多少个数 这样才知道有多少空位置还可以放 记为j
  3. 我们必须清楚当前最大数出现了多少次k 这样才会不重不漏的统计方案(考虑将来放的和这k个位置的关系即可)
  4. 我们必须清楚当前放入这些之后会形成多少个不同的a数列(题目要求小于等于K) 记为l

~~不~~显然的,我们只需要记录这4个状态就好了。

注意:因为我们只统计上升序列,n要除以2,并且对于情况1 2 3 2,我们统计的上升序列只能为1 2,并不是1 2 3,换个角度讲,如果当前最大值为n(除以二之后的),那么对于答案是没有贡献的(1 2 3要怎样才能对长度为6的有贡献?) 所以代码中 \(f_{i,j,k,l}\)对答案贡献要乘以\(m-i\)

Code

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, K;
int C[105][105];
int f[55][55][55][105], ans;
const int P = 1000000007;
typedef long long LL;
void inc(int &x, int val) {
    x = (x + val) % P;
}
int main() {
    scanf("%d %d %d", &n, &m, &K);
    n >>= 1;

    C[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= n; ++j)
            C[i][j] = min(233, C[i-1][j-1] + C[i-1][j]);
        f[1][i][i][1] = 1;
    }

    int mi = min(n, m);
    for (int i = 1; i <= mi; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= j; ++k)
                for (int l = 1; l <= K; ++l) {
                    inc(ans, LL(f[i][j][k][l]) * LL(m-i) % P);
                    for (int x = 1; x <= n-j; ++x) {
                        int l1 = LL(l) * C[k+x-1][x-1] % P;
                        if (l1 > K) break;
                        inc(f[i+1][j+x][x][l1], f[i][j][k][l]);
                    }
                }
    printf("%d", ans);
}
Show Comments