301594: CF301E. Yaroslav and Arrangements

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Yaroslav and Arrangements

题意翻译

【问题描述】 如果一个数列相邻两项之差的绝对值均为 1(我们认为首项和末项也相 邻),并且首项是数列中最小的元素之一,那么我们称之为良好数列。 如果一个数列单调不降且长度在 1 到 n 之间,数列中每个数的值在 1 到 m 之间,且重排后能得到至少 1 个至多 k 个良好数列,那么我们称之为优秀数列。 给出 n、m、k,求优秀数列的个数。 答案对 1000000007 取模 【输入格式】 单独一行三个整数 n,m,k 【输出格式】 单独一行输出答案 Translated by @Kirito_Rivaille

题目描述

Yaroslav calls an array of $ r $ integers $ a_{1},a_{2},...,a_{r} $ 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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF301E/938f366b586bab0fd2fd57fba81115a5a67045ff.png). An array of integers $ b_{1},b_{2},...,b_{r} $ is called great, if it meets the following conditions: 1. The elements in it do not decrease $ (b_{i}<=b_{i+1}) $ . 2. If the inequalities $ 1<=r<=n $ and $ 1<=b_{i}<=m $ hold. 3. 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 $ 1000000007 $ $ (10^{9}+7) $ . Two arrays are considered distinct if there is a position in which they have distinct numbers.

输入输出格式

输入格式


The single line contains three integers $ n $ , $ m $ , $ k $ $ (1<=n,m,k<=100) $ .

输出格式


In a single line print the remainder after dividing the answer to the problem by number $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

1 1 1

输出样例 #1

0

输入样例 #2

3 3 3

输出样例 #2

2

Input

题意翻译

【问题描述】 如果一个数列相邻两项之差的绝对值均为 1(我们认为首项和末项也相 邻),并且首项是数列中最小的元素之一,那么我们称之为良好数列。 如果一个数列单调不降且长度在 1 到 n 之间,数列中每个数的值在 1 到 m 之间,且重排后能得到至少 1 个至多 k 个良好数列,那么我们称之为优秀数列。 给出 n、m、k,求优秀数列的个数。 答案对 1000000007 取模 【输入格式】 单独一行三个整数 n,m,k 【输出格式】 单独一行输出答案 Translated by @Kirito_Rivaille

加入题单

上一题 下一题 算法标签: