纪中23日c组T3 2161. 【2017.7.11普及】围攻斐波那契数列

2161. 围攻

(File IO): input:siege.in output:siege.out

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述

经过刘邦的严密缉查，项羽的位置也就水落石出了。刘邦便趁机集合军队，进行对项羽的围攻。为了增加胜率，张良研究出一种全新的战法，目的就是一举打败难缠的项羽。
这种军队共有N个单位，一个接着一个排成一排，每个单位可以是士兵，或者是战车，这样的组合可以爆发出意想不到的强大战斗力；但有一点，两辆战车不能相邻，否则会发生剐蹭等不好的事故。刘邦希望知道这N个单位的军队都多少种不同的排列方法，以便在战场中随机应变。两种军队的排列方法是不同的，当且仅当某一个单位对应不同，如：第i位这种是士兵，那种是战车……

输入

输入仅一行，一个整数N。

输出

输出仅一行，一个整数，表示排列的方案数。
答案对 10^8+7 取模

样例输入

样例输出

数据范围限制

对于30%的数据：N≤15；
对于70%的数据：N≤10^6；
对于100%的数据：N≤10^18。

提示

样例解释

以0表示士兵，1表示战车，则全部方案如下：000，100，010，001，101。

Solution

这道题是什么题？组合？数列？暴力枚举？搜索剪枝？

先打个表压压惊……

Algorithm1

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#define IL inline
#define re register
using namespace std;

long long n,ans;
IL void dfs(int depth,bool last)
{
    if(depth>=n) {
        ans++;
        return;
    }
    if(!last) dfs(depth+1,1);
    dfs(depth+1,0);
}
int main()
{
//    freopen("siege.in","r",stdin);
//    freopen("siege_table.out","w",stdout);
    for(n=1;n<=50;n++)
    {
        cout<<"n="<<n<<endl;
        ans=0;
        dfs(0,0);
        cout<<ans<<endl;
    }
    return 0;
}

table

打表找规律，暴力出奇迹

n=1
2
n=2
3
n=3
5
n=4
8
n=5
13
n=6
21
n=7
34
n=8
55
n=9
89
n=10
144
n=11
233
n=12
377
n=13
610
n=14
987
n=15
1597
n=16
2584
n=17
4181
n=18
6765
n=19
10946
n=20
17711
n=21
28657
n=22
46368
n=23
75025
n=24
121393
n=25
196418
n=26
317811
n=27
514229
n=28
832040
n=29
1346269
n=30
2178309
n=31
3524578
n=32
5702887
n=33
9227465
n=34
14930352
n=35
24157817
n=36
39088169
n=37
63245986
n=38
102334155
n=39
165580141
//速度太慢了，后略……

好了，规律已找到，就是从2:1开始的斐波那契数列嘛

（然而我并没有看到取模，于是在打完表后我就去写高精度了）

证明呢？

别问我……下午听完讲后再证明吧……

Algorithm2

当然是：

暴力递推，边算边取模！

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<set>
 8 #include<queue>
 9 #include<vector>
10 #define IL inline
11 #define re register
12 using namespace std;
13 
14 
15 int main()
16 {
17 //    freopen("siege.in","r",stdin);
18 //    freopen("siege.out","w",stdout);
19     re unsigned int n,x=2,y=1,t,mo=1e8+7;
20     cin>>n;
21     while(--n)
22     {
23         t=x;
24         x=x+y;
25         y=t;
26         while(x>=mo) 
27             x-=mo;
28     }
29     printf("%d",x);
30     return 0;
31 }

经过我多次实验，

while+减法比%要快一倍

每次只需要让x取模

y和t也会变小

以及

这还是拿不到100分！

Algorithm3

好吧……我之前在洛谷上做过这道题的算法版（只是没有这些背景）

然而，我忘记了……

洛谷P1962 斐波那契数列

对于100%的数据，n<=10^18，一些公式可以利用

公式一

f(2n)=f(n)^2-f(n-1)^2=(2f(n-1)+f(n))*f(n)

公式二

f(2n+1)=f(n+1)^2+f(n)^2

证明

下午再说……

这样的话，只要对n进行二进制运算就可以了O（log（n））

顺便加一个数组存已经计算好的斐波那契数，方便以后调用

（不过10^18貌似存不下，考虑使用map）

Code3

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<set>
 8 #include<queue>
 9 #include<vector>
10 #define IL inline
11 #define re register
12 using namespace std;
13 map<int,int>fbnq;
14 long long mo=1e8+7;
15 IL long long f(long long num)
16 {
17     if(num==1) return 1;
18     if(num==2) return 1;
19     if(num==3) return 2;
20     if(fbnq.find(num)!=fbnq.end()) return fbnq[num];
21     long long ans=0,n=num>>1;
22     if(num&1)
23     {
24         ans=f(n+1)*f(n+1)%mo;
25         ans+=f(n)*f(n)%mo;
26     }
27     else
28     {
29         ans=2*(f(n-1))%mo+f(n);
30         ans%=mo;
31         ans*=f(n);
32         
33     }
34     ans%=mo;
35     fbnq[num]=ans;
36     return ans;
37 }
38 int main()
39 {
40 //    freopen("siege.in","r",stdin);
41 //    freopen("siege.out","w",stdout);
42     long long n;
43     cin>>n;
44     printf("%lld",f(n+2));
45     return 0;
46 }

Attention

最好都开long long以防还没取模就溢出了！

还有许多细节可以优化

但是我饿了

纪中2019-08-23 12:32:06

哎……

纪中23日c组T3 2161. 【2017.7.11普及】围攻 斐波那契数列