「fjWC2014」排列方案
时限：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分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<iostream> #include<cstdio> #define mod 10007 using namespace std; bool used[1000001]; int T,n,k,ans; bool pd(int a,int b) { if(a-b>k||b-a>k)return 0; return 1; } void search(int s) { if(s==n+1){ans++;ans%=mod;} for(int i=1;i<=n;i++) { if(pd(s,i)&&!used[i]) { used[i]=1; search(s+1); used[i]=0; } } } int main() { scanf("%d",&T); for(int i=1;i<=T;i++) { ans=0; printf("Case %d: ",i); scanf("%d%d",&n,&k); if(k) { search(1); printf("%d\n",ans); } else printf("1\n"); } return 0; } |
Subscribe
计数器 9854669
OI 课件=>
OI 课件=>