翻译已交，直接上正解。
Solution
显然，直接 dfs 生成排列-测试会超时。
想到可以在 dfs 过程中进行测试（判断下一个放置的数字是否满足反斐波那契序列的条件）。
于是代码就长这样：
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
| #include<bits/stdc++.h>
using namespace std;
int n;
bool flag[10001];
int ans[10001];
int tot;
void dfs(int now)
{
if(now==n+1)
{
tot++;
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
puts("");
}
for(int i=1;i<=n;i++)
if(!flag[i]&&(now==1||now==2||ans[now-2]+ans[now-1]!=i))
{
flag[i]=true;
ans[now]=i;
dfs(now+1);
if(tot==n) return;
flag[i]=false;
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
tot=0;
memset(flag,0,sizeof(flag));
cin>>n;
dfs(1);
}
}
|
46ms，AC。
But，你认为这就结束了吗？
Solution++
以上方法时间复杂度玄学（不想算，反正有 ，系数还蛮大），但通过数学分析可以降至裸 。并且代码量少很多
将排列降序。任意选择第 位数，那么这个数就是 。向前数两个数，分别是 和 。显然，。
将前两个数字相加，关于 的方程 的解为 。
若不是反斐波那契数列，就应该满足 。与 相矛盾。说明逆序排列是反斐波那契数列。
那么，如果我们调换一下前后相邻的两个数的顺序？
那么，序列就会变成：
$$
(n-i+4),(n-i+3),(n-i+1),(n-i+2),(n-i+0),(n-i-1)
$$
事实上，可能没有 ，但没有可以不用管这个数字了，所以不会有问题。
如果有的话，调换顺序会波及到这些数字。
一一列出方程，解就完事了！
，不成立。
，不成立。
，不成立。
（想必你能猜到是这个吧），不成立。
都不成立，说明在倒序的基础上对调数字，都满足反斐波那契数列。
所以，总共可以调转 次，加上原来的逆序 次，就有 次了。
满足了题目条件。
这也就为什么题目上会有 的原因吧。
附：中间为什么会有一个 的解呢？
理性的认识，中间的两个数对调，移项了，所以有两点贡献，相比逆序的解应该少 。
这下，其他的解为 应该也不难理解了吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int j=n;j>=1;j--) printf("%d ",j);puts("");
for(int i=n;i>=2;i--)
{
for(int j=n;j>=1;j--)
{
if(j==i) printf("%d %d ",j-1,j),j--;
else printf("%d ",j);
}
puts("");
}
}
return 0;
}
|
Solution+
事实上，这道题有许多方法，最终原理就是 逆序排列永远满足反斐波那契数列。
方法1
逆序后，将任意一个数提前，也是 种。
方法2
逆序后，调换间隔一个数的两个数。（猜测）
附上 Translate。
Translate
反斐波那契数列（anti-Fibonacci）定义为 的排列中不满足 的排列。
输入 数据，每组数据给定序列长度 。
对于每组数据，只需任意输出 个长度为 的反斐波那契数列。每行一个序列，用空格分隔。（不允许输出多个相同的序列。易证长度为 的反斐波那契数列数量必定大于等于 。）
其中 。