CF285D. Permutation Sum
题目
大意
寻找a，b两个排列从0到n-1，有c[i]=(a[i]+b[i])%n+1，使得c[i]也为全排列的排列方式
思路
a中元素和b中元素的对应方式不同，c数组也不同，且a和b此时全排列方式各有n!种。
可以先固定a中的数，从0到n-1，再dfs搜索b与之相应匹配的值，当然时间消耗会很大（求解n=15大概在五分钟左右）
再看题目条件，n最大到16，所以可以考虑打表方法，获取全部的值。
求解出来的答案再考虑a数组本身的全排列，且b随之对应排列，故需乘上n!
代码
首先打表：
#include<iostream>
#include<cstring>
using namespace std;
int a[20],b[20];
int sign[20];
int count;
void dfs(int now, int num) {
if(now == num) {
count++;
return;
}
for(int i=0;i<num;i++) {
if(b[i]) { // b[i]已经使用过，忽略
continue;
}
int c = (a[now]+i)%num+1;
if(sign[c]) { // c不构成全排列，忽略
continue;
}
sign[c]=1;
b[i]=1;
dfs(now+1, num);
sign[c]=0;
b[i]=0;
}
}
int main() {
for(int i=0;i<16;i++) {
a[i] = i;
}
// a固定下来，b逐个dfs过去
for(int i=0;i<16;i++) {
count = 0;
memset(sign, 0, sizeof(sign));
memset(b, 0, sizeof(b));
dfs(0, i+1);
cout << "num=" << i+1 << ' ' << "count=" << count << endl;
}
}
于是获取到：
num=1 count=1
num=2 count=0
num=3 count=3
num=4 count=0
num=5 count=15
num=6 count=0
num=7 count=133
num=8 count=0
num=9 count=2025
num=10 count=0
num=11 count=37851
num=12 count=0
num=13 count=1030367
num=14 count=0
num=15 count=36362925
所以可以提交代码了：
#include<iostream>
using namespace std;
long long int a[17],b[17];
int mod = int(1e9)+7;
int main() {
a[1]=1;
a[3]=3;
a[5]=15;
a[7]=133;
a[9]=2025;
a[11]=37851;
a[13]=1030367;
a[15]=36362925;
b[1]=1;
for(int i=2;i<=16;i++) {
b[i] = (b[i-1] * i) % mod;
}
long long int n;
cin >> n;
cout << a[n]*b[n]%mod;
}