题目大意:给出n,m和k,表示有一个序列,由1~n组成,有序,现在将这个序列重排,问有多少种重排序列满足:前m个中恰好有k个的位置不变(即i=pos[i])。
解题思路:首先c=C(km)为前m个数选中k个位置保持不变,然后枚举后n-m个中有多少个数的位置是不变的,C(in−m),这样就有n−k−i个数为乱序排列。解法和uva10497一样。
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 1005;
const ll MOD = 1000000007;
int n, m, k;
ll dp[N], c[N][N];
void init () {
memset(c, 0, sizeof(c));
for (int i = 0; i < N; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
}
dp[0] = 1;
dp[1] = 0;
for (ll i = 2; i < N; i++)
dp[i] = ((dp[i-1] + dp[i-2]) % MOD * (i-1)) % MOD;
}
ll solve () {
ll ans = 0;
int t = n - m;
for (int i = 0; i <= t; i++)
ans = (ans + c[t][i] * dp[n-k-i]) % MOD;
return (ans * c[m][k]) % MOD;
}
int main () {
init();
int cas;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
scanf("%d%d%d", &n, &m, &k);
printf("Case %d: %lld\n", i, solve());
}
return 0;
}
分享到:
相关推荐
Arrange the output lines by telephone number in ascending lexicographical order. If there are no duplicates in the input print the line: No duplicates. Sample Input 12 4873279 ITS-EASY 888-4567 ...
public class Arrange{ private int[] index;//用于存储需要全排列的数组的下标的成员变量。 private int n;//表示待排数组的元素个数。 private long numLeft;//用于存储剩余排列序列个数的成员变量。 private...
很好用的jQuery拖拽排序插件,兼容IE浏览器
jQuery ui drag插件实现浮动div拖动排列布局代码,jQuery实现拖动布局并将排序结果保存到数据库
components-arrange, 用于排列/对齐水平单元格的组件 CSS,有点像 flexbox 适合CSS组件排列 适用于水平和垂直排列单行单元格的CSS组件。 包含用于相等宽度单元格和分离单元格的修改器类。 使用 CSS table 布局。注意...
sudo npm install -g mp3-arrange 用法 Usage: mp3-arrange [options] Options: -s DIR, --source DIR Source directory -d DIR, --destination DIR Destination directory -l FILE, --logfile FILE Log file ...
比较实用的js拖拽插件。
css-arrange css的知识点整理
中高考排考系统npm installnpm run serve
排课系统--回溯装载问题
js安排 js知识的整理总结
Kicad插件排列示意图 复制到.kicad_plugins 。 按照原理图中显示的顺序排列组件,以帮助进行初始布局。
一个关于 拖拽(Drag) 的例子
An android layout to re-arrange child views via dragging Screencast Demo Layout Usage All the child views are draggable once the layout is added to an activity (activity_main.xml) <!-- add ...
课程安排 ...(3)如果构造的AOV网无环,则将课程信息及其先行关系信息、合理的课程安排保存到course-arrange.txt文件中;否则将课程信息及其先行关系信息、提示信息保存到course- arrange.txt文件中。
排列文本大小 用于排列元素文本大小的 Angular 指令 入门 (即将推出) 文档 (即将推出) 例子 (即将推出) 贡献 代替正式的风格指南,注意维护现有的编码风格。 为任何新的或更改的功能添加单元测试。...
-Arrange captured data to user preferences such as the byte width per line -View low level protocol including SCSI sense data and USB setup packets -View microsecond resolution timing of each phase...
2DDL is totally dynamic, this mean that you can re-arrange lights and obstacles, and the final result is affected in real-time; or you can choose a Pre-Baked Light and thus avoid the calculation in ...
基于jQuery的拖拽排序插件dragarrange