最开始 题解
KesdiaelKen
2018-11-06 19:17:42
# T0最开始 题解
$40\%$（常数小则$60\%$）数据：
我们要求$a^n+\frac{1}{a^n}$，可以找出它与$a^{n-1}+\frac{1}{a^{n-1}}$的关系：$(a^{n-1}+\frac{1}{a^{n-1}})(a+\frac{1}{a})=(a^n+\frac{1}{a^n})+(a^{n-2}+\frac{1}{a^{n-2}})$，发现可以递推。
$100\%$数据：
以上为$O(m)$做法，显然不符合要求。超时原因是我们知道了太多$a^s+\frac{1}{a^s}$的值。我们考虑$O(\log m)$。有$(a^n+\frac{1}{a^n})^2=a^{2n}+\frac{1}{a^{2n}}+2$，$(a^n+\frac{1}{a^n})(a^{n+1}+\frac{1}{a^{n+1}})=a^{2n+1}+\frac{1}{a^{2n+1}}+(a+\frac{1}{a})$，所以就可以愉快的记忆化搜索啦！
标程：
```
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
using namespace std;
long long mod=1000000007;
map<long long,long long>dy;
void dfs(long long shu)
{
if(dy.count(shu))return;
dfs(shu/2);dfs(shu-shu/2);dfs(shu&1);
dy[shu]=dy[shu/2]*dy[shu-shu/2]-dy[shu&1];
dy[shu]%=mod;
}
int main()
{
long long n,m;scanf("%lld%lld",&n,&m);
dy[0]=2;dy[1]=n;
dfs(m);
printf("%lld\n",dy[m]);
return 0;
}
```