消息传播

消息传播"/>

消息传播

Description

　　众所周知，HYF有很多小姊妹。
　　HYF每天放学之后都要跟（不同的）MM约会。HYF这天约会的时候不巧被jzt撞上了……虽然换一个新的MM约会这种事情对于HYF来说如同家常便饭，所谓“好事不出门，坏事传千里”，jzt迅速将这个消息传播开来。
　　每个听到这个消息的人首先会震惊一段时间（他怎么又换MM了- -~！），但是这样的震惊只会持续2个时刻（因为这对于HYF来说太正常了= =~！）。如果他在第i个时刻听到这个消息，就会从第（i+2）个时刻开始传播这个消息，每个时刻把这个消息告诉两个人，当然他只会告诉不知道这个消息的人。但是当他连续告诉了10个人之后，他就会口干舌燥，停止传播。
　　jzt在第0时刻撞到HYF（当然jzt也有震惊时间），请问第N时刻共有多少人知道了这个消息？
Input
　　一行一个整数N，表示第N时刻。
Output
　　一行一个整数，表示N分钟后知道这个消息的总人数。
Sample Input
【输入样例1】
4
【输出样例1】
11
【样例解释】
时刻0：一开始只有jzt知道
时刻2：jzt开始传播，时刻2传播给A和B，时刻3传播给C和D，时刻4传播给E和F；
时刻4：A和B在4开始传播，时刻4传播给2×2=4个人，传播给H、I、J、K；
最后知道消息的共有：jzt,A,B,C,D,E,F,H,I,J,K，共11个人。
【输入样例2】
1
【输出样例2】
1
【输入样例3】
10
【输出样例3】
651
Sample Output

The solution

这道题告诉我们，如果一开始没有思路的话，就先暴力找到递推公式。
我们可以发现，这道题的递推公式很显然，以下：

由于答案很大，所以要用高精度。

主要靠我们的递推能力，与高精度递推。

PS.插广告：这时我做的模板库就有用了。嘿嘿嘿

在比赛时，第一次用c++打了一种奇怪的方法。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define N 10005
#define M 1005
#define ya 1000000
#define fo(i,a,b) for (int i=a;i<=b;i++)
#define fd(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
int n,f[N][M],g[M],h[M];
void jia(int a[],int b[],int c[])
{fill(c,c+M,0);int k=max(a[0],b[0]);fo(i,1,k){c[i]+=a[i]+b[i];c[i+1]+=c[i]/ya;c[i]%=ya;}if (c[k+1]>0) c[0]=k+1;else c[0]=k;}void jian(int a[],int b[],int c[])
{int d[M],k=a[0];fill(c,c+M,0),fill(d,d+M,0);memcpy(d,a,sizeof(d));fo(i,1,k){if (d[i]<b[i]){d[i+1]--;d[i]+=ya;}c[i]=d[i]-b[i];}while (!c[k]) k--;c[0]=k;
}int main() 
{scanf("%d",&n);fo(i,0,6) f[i][0]=1;f[0][1]=f[1][1]=1;f[2][1]=3;f[3][1]=5;f[4][1]=11;f[5][1]=21;f[6][1]=43;fo(i,7,n){jian(f[i-2],f[i-7],g);jia(g,g,h);jia(f[i-1],h,f[i]);}printf("%d",f[n][f[n][0]]);fd(i,f[n][0]-1,1) printf("%06d",f[n][i]);return 0;
}