SPOJ - PERMJUMP Permutation Jumping

Discription

John likes playing the game Permutation Jumping. First he writes down a permutation A of the first n numbers. Then, he chooses any cell to start on. If he is currently at cell x and hasnt visited the cell A[x], he jumps to cell A[x]. He keeps doing this till he cannot move to the cell A[x], because he has already visited it. In the end, he counts all the cells that he visited during the game, including the cell on which he started.

He does not want the game to go on for too long, and thus he wishes that irrespective of the choice of his starting cell, he does not ever have to visit more than K cells. On the other hand, he does not want the game to be too short either. Thus, irrespective of the choice of his starting cell, he should be able to visit atleast two cells.

Now he wonders how many permutations could he have chosen in the first place which would allow him to have the game duration as above. i.e. He should visit atleast 2 cells and atmost K cells, no matter which cell he started on.

Input

The first line contains the number of test cases T (T <= 1000). The next T lines contain 2 space seperated integers N and K. (2 <= K <= N <= 100)

Output

Output T lines, one corresponding to each test case. For each test case output a single integer which is the answer for the corresponding test case. Since the answer can be very large, output the answer modulo 1000000007.

Example

Sample Input :
2
4 2
6 4

Sample Output :
3
145

Note :
For the first case, the valid permutations are {2 1 4 3}, {3 4 1 2} and {4 3 2 1}.

设f[i]为i的排列中满足条件的个数，转移的时候直接枚举1所在的循环的大小，再乘上其他数位置的排列数即可。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=205;

const int ha=1000000007;

inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}

inline int ksm(int x,int y){ int an=1; for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha; return an;}

int jc[maxn],ni[maxn],T,n,k,f[maxn];

inline int P(int x,int y){ return x<y?0:jc[x]*(ll)ni[x-y]%ha;}

inline void init(){

	jc[0]=1;

	for(int i=1;i<=200;i++) jc[i]=jc[i-1]*(ll)i%ha;

	ni[200]=ksm(jc[200],ha-2);

	for(int i=200;i;i--) ni[i-1]=ni[i]*(ll)i%ha;

}

inline void solve(){

	f[0]=1;

	for(int i=1;i<=n;i++)

	    for(int j=min(k,i);j>1;j--) f[i]=add(f[i],f[i-j]*(ll)P(i-1,j-1)%ha);

	printf("%d\n",f[n]);

}

int main(){

	init();

	scanf("%d",&T);

	while(T--) memset(f,0,sizeof(f)),scanf("%d%d",&n,&k),solve();

	return 0;

}

巴特西

SPOJ - PERMJUMP Permutation Jumping

最新文章

热门文章