题目大意
由两个长度为 n 的 1~n 的排列，定义一个排列的加法：c(i)=(a(i)+b(i)-2)%n+1，如果 c 也是一个 1~n 的排列话，这就是一个可行的加法
现在给你一个长度 n(1≤n≤16)，让你共有多少种可行的排列对，使得他们的加法也是一个排列
做法分析
首先肯定有这样的思路：固定一个排列，比如令 a 为 1，2，...，n
那么，我们找出所有 b 的情况数量 cnt，最终的答案就应该是 cnt*n!
看到 n 的数量级，就想去暴力试试，但是算了下 16 的阶乘，蛮大的，不管了，先写一个暴力，加点小剪枝，十多分钟后，表打出来了：
然后贴着表过了，好没节操
参考代码
1、打表的代码
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 5 using namespace std; 6 7 const int N=26; 8 9 int n, A[N], B[N], ans; 10 bool use[N], vs[N]; 11 12 void DFS(int pos) 13 { 14 if(pos==n) 15 { 16 ans++; 17 return; 18 } 19 for(int i=1; i<=n; i++) 20 { 21 if(use[i]) continue; 22 int cur=(A[pos]+i-2)%n+1; 23 if(vs[cur]) continue; 24 vs[cur]=1, use[i]=1; 25 DFS(pos+1); 26 vs[cur]=0, use[i]=0; 27 } 28 } 29 30 int main() 31 { 32 freopen("out.txt", "w", stdout); 33 for(n=1; n<=16; n+=2) 34 { 35 for(int i=0; i<n; i++) A[i]=i+1; 36 memset(use, 0, sizeof use); 37 memset(vs, 0, sizeof vs); 38 ans=0; 39 DFS(0); 40 printf("n=%d ans=%d\n", n, ans); 41 } 42 return 0; 43 }
2、AC的代码
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 5 using namespace std; 6 7 typedef long long LL; 8 const int MOD=1000000007; 9 10 LL ans[20], fac[20]; 11 12 int main() 13 { 14 memset(ans, 0, sizeof ans); 15 ans[1]=1; 16 ans[3]=3; 17 ans[5]=15; 18 ans[7]=133; 19 ans[9]=2025; 20 ans[11]=37851; 21 ans[13]=1030367; 22 ans[15]=36362925; 23 fac[0]=1LL; 24 for(int i=1; i<=16; i++) fac[i]=(fac[i-1]*i)%MOD; 25 int n; 26 scanf("%d", &n); 27 printf("%I64d\n", ans[n]*fac[n]%MOD); 28 return 0; 29 }