HDU4565 So Easy! —— 共轭构造、二阶递推数列、矩阵快速幂
题目链接:https://vjudge.net/problem/HDU-4565
So Easy!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5525 Accepted Submission(s): 1841
Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn.
You, a top coder, say: So easy!
2 3 2 2013
2 2 1 2013
14
4
题解:
1.因为:0< a,(a-1)2< b < a2,。当a>=1时, a-1<根号b<a,那么 0<(a-根号b)<1;当0<a<1时, 1-a<根号b<a,那么 那么 0<(a-根号b)<2*a-1<1。综上:0<(a-根号b)<1。所以0<(a-根号b)^n<1
2.这里假设b = 根号b,以方便描述。根据上述结论,那么可得:[(a+b)^n] = [(a+b)^n + (a-b)^n] = (a+b)^n + (a-b)^n 。
解释:
2.1 因为a-1<b<1,所以b必定是浮点数,那么(a+b)^n 也必定是浮点数,此时,再加上个大于0小于1的浮点数(a-b)^n,那么 [(a+b)^n + (a-b)^n] 有可能等于[(a+b)^n] ,也有可能等于[(a+b)^n] +1,这就要取决(a+b)^n的小数部分与(a-b)^n的小数部分之和是否大于1。
2.2 此时,就要将(a+b)^n+(a-b)^n展开进行分析。展开后可知,当b的指数为奇数时,正负抵消;当b的指数为偶数时,b^2k 为一个整数。综上:(a+b)^n+(a-b)^n为一个整数,即表明(a+b)^n的小数部分与(a-b)^n的小数部分之和刚好等于1,所以[(a+b)^n] = [(a+b)^n + (a-b)^n] = (a+b)^n + (a-b)^n 。
3.根据上述分析,问题转化为求:S[n] = (a+b)^n + (a-b)^n 。而这个式子可以看成是二阶齐次递推式的通项公式,可以根据通项公式反推回递推式,然后构造矩阵进行求解。具体如下:
以上来自:http://blog.csdn.net/ljd4305/article/details/8987823
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
//const int MOD = 1e9+7;
const int MAXN = 1e6+; int MOD;
const int Size = ;
struct MA
{
LL mat[Size][Size];
void init()
{
for(int i = ; i<Size; i++)
for(int j = ; j<Size; j++)
mat[i][j] = (i==j);
}
}; MA mul(MA x, MA y)
{
MA ret;
memset(ret.mat, , sizeof(ret.mat));
for(int i = ; i<Size; i++)
for(int j = ; j<Size; j++)
for(int k = ; k<Size; k++)
ret.mat[i][j] += 1LL*x.mat[i][k]*y.mat[k][j]%MOD, ret.mat[i][j] = (ret.mat[i][j]%MOD+MOD)%MOD;
return ret;
} MA qpow(MA x, LL y)
{
MA s;
s.init();
while(y)
{
if(y&) s = mul(s, x);
x = mul(x, x);
y >>= ;
}
return s;
} int main()
{
LL a, b, n, m, f[];
while(scanf("%lld%lld%lld%lld", &a,&b,&n,&m)!=EOF)
{
MOD = (int)m;
f[] = ; f[] = *a;
if(n<=)
{
printf("%lld\n", f[n]%MOD);
continue;
} MA s;
memset(s.mat, , sizeof(s.mat));
s.mat[][] = *a; s.mat[][] = b-a*a;
s.mat[][] = ; s.mat[][] = ; s = qpow(s, n-);
LL ans = (1LL*s.mat[][]*f[]%MOD+1LL*s.mat[][]*f[]%MOD+*MOD)%MOD;
printf("%lld\n", ans);
}
}
最新文章
- CentOS7 Jenkins安装
- linux发行版基础目录
- c#winform程序,修改MessageBox提示框中按钮的文本
- 必须知道的八大种排序算法【java实现】(三) 归并排序算法、堆排序算法详解
- strerror
- Java编程思想学习笔记_1(Java内存和垃圾回收)
- 如果在安装32位oracle 客户端组件时的情况下以64位模式运行,将出现问题
- BOOL、sizeof
- 《JS权威指南学习总结--3.1数字》
- 设置ubuntu 默认不启动图形界面
- ViewSwitcher的功能与用法
- jQuery对象长度size
- python全栈开发day51-jquery插件、@media媒体查询、移动端单位、Bootstrap框架
- POJ 3579 Median 【二分答案】
- mysql关联表修改语句
- Mac下压力测试工具siege
- win7笔记本VirtualBox安装黑苹果MacOS 10.13
- 【转】METADATATYPE的使用,MVC的MODEL层数据验证
- 【MarkdownPad】不能输入表格Table
- Apache Shiro在web开发安全框架中的应用