首页 > 代码库 > UVALive 5971

UVALive 5971

2024-07-13 12:08:14   225人阅读

Problem J Permutation Counting
Dexter considers a permutation of first N natural numbers good if it doesn‘t have x and x+1 appearing consecutively, where (1 ≤ x < N)  For example, for N=3 , all goodpermutations are:
1. {1, 3, 2}
2.{2, 1, 3}
3.{3, 2, 1}
Input
Input starts with an integer T (≤ 10000 , denoting the number of test cases.Each
case starts with a line containing an integer N (1 ≤ N ≤ 106)
.
Output
For each case, print the case number and the number ofgoodpermutations
modulo1000 000 007
.
Sample Input
Output for Sample Input
3
2
3
5
Case 1: 1
Case 2: 3
Case 3: 53
 1 #include <map> 2 #include <set> 3 #include <list> 4 #include <cmath> 5 #include<cctype> 6 #include <ctime> 7 #include <deque> 8 #include <stack> 9 #include <queue>10 #include <cstdio>11 #include <string>12 #include <vector>13 #include<climits>14 #include <cstdlib>15 #include <cstring>16 #include <iostream>17 #include <algorithm>18 #define LL long long19 #define PI 3.141592653589793262620 using namespace std;21 int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}22 #define MAXN 100000523 #define MOD 100000000724 LL ans[MAXN],tmp[MAXN];25 void init()26 {27     ans[1]=1;ans[2]=1;28     for (int i=3;i<MAXN;i++)29        {30            ans[i]=((i-1)*ans[i-1])+(i-2)*ans[i-2];31            ans[i]%=MOD;32        }33 }34 int main()35 {36     init();37     int T;int kase=1;38     scanf("%d",&T);39     while (T--)40     {41         int N;42         scanf("%d",&N);43         printf("Case %d: %lld\n",kase++,ans[N]);44     }45     return 0;46 }
View Code

 

 


联系
我们