想了很久觉得自己做法肯定T啊，就算是CF机子的3s时限，但我毕竟是 O ( C(15,7)*7!*log ) ....
果然在n=15的点T了...贱兮兮地特判了15过掉了，结果发现题解说就是打表...
(卒，享年16岁)
总之啊总之，要灵活啊
回归机房以后发现Div2的D都要想一个世纪了......不过感觉这题真的挺好的？
命不久矣，所以想最后写写题解吧。
题目大意：求满足 a+b=c（ a,b,c均为长度为n的排列）的有序对{a,b}的对数
(说明：a,b,c均为0~(n-1)的排列 +运算为题中定义的+的等价修改 即ci=(ai+bi)mod n )
∆初步分析，有 2*n*(n-1)/2 = n*k + n*(n-1)/2 (k为整数) 则有 k=(n-1)/2 则n必须为奇数 否则答案为0
∆显然，{a,c}和{a,b}是一一对应的，所以我们不妨求{a,c}的有序对数（实际上这个转换并没有什么用处，只是我感觉爽....）
∆进一步化简，不妨将a固定为{0,1,2...n-1}，则最终所求方案数* n! 即为答案。
∆考虑c需要满足的条件：
(1)i-ci=j-cj(mod n) 对于任意 i!=j 均不成立
(2)ci为0~n-1 且互不相同
(2)较容易解决，记录出现的数字即可。考虑如何满足(1)。想象你是在玩一个类似数独的游戏，在一个一个填数字，那么你只要保证:1.已经填上的数字彼此之间满足(1).(2) 2.新填入的第i+1个数字和前i个数字不重复、不冲突。
由此，我们可以像填数独一样，列出下一个格子不能取的值。那么我们就有一个大致思路，即状压，记录两维状态v1,v2（即由条件(1)、(2)，下一位不能取的数字有哪些）。转移只需枚举下一位的可行数字x，在v1并入x，在v2并入x并循环右移1位（ ci !=( val=cj-j+i ) ci+1 != (val+1=cj-j+i+1) ） 。
∆然鹅，这样复杂度很高（上界可达 O(n*22n) ？总之打表估计都GG），因此我们考虑进一步优化。
优化的本质就是探寻性质。我们发现，对于f[v1][v2]>0，v1和v2中的1个数一定相同，即在v2中并入数字时一定不会并入一个已经存在的位。可以用反证法证明，若并入ci对ci+1的影响时，该位已有cj对ci+1的影响，那么i、j两位就一定不符合(2)。
也就是说，v1,v2是可以「拆分」的。
∆「拆分」具体是什么意思呢？我们来模拟一下。
假设n=7,当前已经放了4个数：
v1=1100110
v2=1001011
现在我们挨个放入剩下的数字。例如：
v1=1120110
v2=0210111
v1=1123110
v2=2131110
v1=1123114
v2=1311142
将末状态和初状态做差，得到：
v1=0023004
v2=0300042
即
v1=0011001
v2=0100011
我们发现 对于初状态的{v1,v2} 差状态即为{1111111^v1, turn(1111111^v1,3) }
(turn(j,ct)表示将j循环右移ct位)
∆于是 我们就可以开心地折半搜索了！复杂度见第一行
（以下是打表代码，如果直接复制会在n=15的点TLE）
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define rep(i,l,r) for(int i=l;i<=r;++i) 5 #define per(i,r,l) for(int i=r;i>=l;--i) 6 #define mp make_pair 7 #define fir first 8 #define sec second 9 10 typedef long long ll; 11 typedef pair<int,int> pii; 12 13 const int p=1000000007,V=1e6+3; 14 15 int n,full,semi,turn[V]; 16 map<pii,int>f[2]; 17 map<pii,int>::iterator it; 18 19 int rev(int j){//j循环右移1位 20 int ans=0; 21 if(j>=semi){ 22 ans=1; 23 j-=semi; 24 } 25 26 return ans|(j<<1); 27 } 28 29 int main(){ 30 scanf("%d",&n); 31 32 if(n==1){ 33 printf("1"); 34 return 0; 35 } 36 37 if(n%2==0){ 38 printf("0"); 39 return 0; 40 } 41 42 full=(1<<n)-1; 43 semi=(1<<(n-1)); 44 45 46 int u=(n>>1); 47 48 f[0][mp(0,0)]=1; 49 50 //多出的一维[0/1]是在愚蠢地省空间... 51 bool oi=0; 52 rep(o,0,u){ 53 f[!oi].clear(); 54 55 for(it=f[oi].begin();it!=f[oi].end();++it){ 56 pii P=it->fir;int val=it->sec; 57 int L=P.fir,R=P.sec; 58 59 int j=(L|R); 60 if(j==full) continue; 61 62 rep(i,0,n-1) if( ( (1<<i)&L ) ==0 && ( (1<<i)&R ) ==0 ) 63 (f[!oi][mp( ( L|(1<<i) ) , rev( R|(1<<i) ) )]+=val)%=p; 64 65 } 66 67 oi=!oi; 68 } 69 70 int pre=(1<<(u+1))-1,suf=full^pre; 71 rep(i,1,full) turn[i]=((i&pre)<<u)|((i&suf)>>(u+1)); 72 //turn[i]即i循环右移(n/2)位 73 74 ll ans=0; 75 for(it=f[oi].begin();it!=f[oi].end();++it){ 76 pii P=it->fir;ll val=it->sec; 77 int L=P.fir,R=P.sec; 78 79 (ans+=val*f[!oi][mp(full^L,turn[full^R])]%p)%=p; 80 } 81 82 rep(i,1,n) (ans*=i)%=p; 83 84 printf("%lld",ans); 85 86 return 0; 87 }