题目

源地址:

http://codeforces.com/contest/15/problem/E

理解

数学渣,这道题无从下手= =。为了方便能自己看出一些东西来,我打了前两项的表去CF提交,幸运地得到了n=6的解,结果是1354。这个结果印证了昨晚比赛时候我的一些想法,因为10=(2^2+1)*274=(6^2+1)*21354=(26^2+1)*2。也就是说,最后的结果一定是某一个数的平方加上一再乘二的结果。这样,这个问题就转化成了,如何找到那个数。我们可以看到,这个数组成的数列是2 6 26。考虑到最后的取模,这个数一定是指数级别的,要不然增长速度太慢了,作为一个未来的码农,想到的第一个数列就是2 4 8。乍一看感觉跟2 6 26扯不上关系,不过再观察一下,2 6 26向前递减之后可以得到另外一个衍生数列,也就是2 4 20。第一个反应就是20=4*5,但是对不上啊,4怎么处理?小脑一动,对啊,4=4*1。1和5跟原数列有什么关系呢?可以看到,1=4-35=8-3。 写到这里,脑子里面已经是一团浆糊了,我来列成表格梳理一下。

a  c  b
2  4  2
4  4  6
8  20 26

这样可以看出,a=pow(2,i),c就等于c*(a-3),明显,b=b+c。于是我就得到了最后的公式。 以上,是通过偷鸡往后再推了一项得到的题解,在实际的比赛中,一方面题目不会再给你下一项(CF倒是可以用这种方法骗答案),另一方面,真的比赛中思路也不会这么清晰。所以还是要学习正规的组合数学+DP的做法,在我学会之前,还是先挖一个坑吧= =。

新技能get

代码


#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#define debug "output for debug\n"
#define pi (acos(-1.0))
#define eps (1e-8)
#define inf 0x3f3f3f3f
#define ll long long int
#define mod 1000000009
using namespace std;

ll a=2,b=2,c=4,n;


int main(int argc, char const *argv[])
{
    scanf("%I64d",&n);
    a=2,b=2,c=4;
    while(n-=2)
    {
        a=a*2%mod,c=c*(a-3)%mod,b=(b+c)%mod;
    }
    printf("%I64d\n",(b*b+1)*2%mod);
    return 0;
}

更新日志

  • 2014年11月23日 已AC。