题目链接:http://codeforces.com/problemset/problem/285/D
题目大意:
有序列 a,b。其中长度均为N,而a1,a2,a3.....an各不相同,且都属于[1, n]。b也是。
现在有一个操作,ci = ((ai - 1 + bi - 1) mod n) + 1 (1 ≤ i ≤ n).
从而生成一个新的序列C。且使得C也符合上述序列的要求。
问a,b有多少种不同的选择,当a!=b时,(a,b)(b,a)为两种选择。
解题思路:
只能够想到n * n!的方法,而且通过打表可以偶数时为0,但奇数最大为15,15!* 15 太大了。
网上看到一个复杂度 为(2^n) * (2^n) 的搜索。虽然也无法在3s内搜完,但至少能打出表。。= =!
其实只需要找到1,2,3,4,……n有多少种匹配的b序列,之后将答案乘以n!(n的全排列)即可。
对于n,用[0, 1<<n)(即二进制枚举)来表示,然后分为两部分搜索。
前一部分选取n1个数字,然后用(1,2,3,……n1)这些数字作为b序列,后一部分选取n-n1个数,然后用(n2,n3……n)作为b序列(在搜索过程中考虑了排列问题)
两者sum1[j] * sum2[j ^ ((1 << n) - 1]即为该种情况的答案数。
/* ID: wuqi9395@126.com PROG: LANG: C++ */ #include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define For(i, n) for (int i = 0; i < n; i++) const int MOD = 1000000007; typedef long long ll; int n; int n1, n2; int g1[20], g2[20]; int key; int cnt1, cnt2; ll sum1[1 << 17], sum2[1 << 17]; int pan(int i, int k) { int sum = 0; while(i) { sum += i & 1; i = i >> 1; } return sum == k; } void dfs1(int s) { if(s > n1) { sum1[key]++; return ; } for(int i = 0; i < cnt1; i++) { int tmp = g1[i]; if(g1[i] == -1) continue; int tmp1 = (tmp + s - 2) % n + 1; if(key & ( 1 << (tmp1 - 1) ) ) continue; key |= ( 1 << (tmp1 - 1) ); g1[i] = -1; dfs1(s + 1); g1[i] = tmp; key ^= ( 1 << (tmp1 - 1) ); } } void dfs2(int s) { if(s > n) { sum2[key]++; return ; } for(int i = 0; i < cnt2; i++) { int tmp = g2[i]; if(g2[i] == -1) continue; int tmp1 = (tmp + s - 2) % n + 1; if(key & ( 1 << (tmp1 - 1) ) ) continue; key |= ( 1 << (tmp1 - 1) ); g2[i] = -1; dfs2(s + 1); g2[i] = tmp; key ^= ( 1 << (tmp1 - 1) ); } } int main() { for(int i = 1; i <= 16; i++) { n = i; n1 = n / 2; n2 = n - n1; ll ans = 0; for(int i = 0; i <= (1 << n) - 1; i++) { if(pan(i, n1) == 0) continue; cnt1 = 0; cnt2 = 0; for(int j = 0; j < n; j++) { if( (1 << j)&i ) g1[cnt1++] = j + 1; else g2[cnt2++] = j + 1; } memset(sum1, 0, sizeof(sum1)); memset(sum2, 0, sizeof(sum2)); key = 0; // 主要用来记录c的情况... dfs1(1); key = 0; dfs2(n1 + 1); for(int j = 0; j <= (1 << n) - 1; j++) { int tmp = j ^ ((1 << n) - 1); ans = (ans + (sum1[j] * sum2[tmp]) % MOD) % MOD; } } for(int i = 1; i <= n; i++) ans = (ans * i) % MOD; printf("%I64d,", ans); } return 0; }