【fjwc2014】排列方案

2014年2月13日1,2260

 

时限:3s 内存:32M

★问题描述:

给定两个正整数n和k,问编号为1~n的n个数的全排列中,有多少排列满足如下条件:对于1~n中的每个数i,满足,它所在的位置的编号(编号从1~n)和它自身的数字i相差不超过k。

例如,当n=4,k=2时,共有24种不同的排列,其中排列(1,3,4,2),(3,1,2,4),(3,4,1,2)等满足条件,排列(2,3,4,1),(2,3,4,1),(3,2,4,1),(4,1,3,2)等不满足条件(前三个排列中1的位置和编号相差为3,第四个排列中4的位置和编号相差为3,不满足条件)

★数据输入:

首先输入一个整数Q(0 < Q ≤ 10),表示有Q组数据。

每组数据输入两个整数n和k (0 < n ≤ 1000000000, 0 ≤ k ≤ 3),表示排列中数的个数和所需k的大小。

★结果输出:

对于每组数据,首先输出编号,之后输出满足条件的不同排列个数,答案对10007取模,具体格式见输出示例。

 

 

输入示例

输出示例

3

4 2

100 0

10 1

Case 1: 14

Case 2: 1

Case 3: 89

 

蒟蒻啥都不会

暴力20分