一道规律题，比较简单。
题目大意：给出一个公式 f [ n ]=f [ n-1 ] - f [ n-2 ]，然后给出 f [ 1 ]和f [ 2 ]的值，以及n，求f [ n ]。附链接：http://codeforces.com/problemset/problem/450/B。
大体思路：因为所给的n很大，所以直接循环n次肯定超时。第一种方法，可以找一下规律，一般公式题都有规律可循，第二种，用矩阵快速幂暴力破解。第一种，通过对样例 1给出的两个数求 f [ n ]，可以发现循环节是6，然后此时由公式 f [ 3 ] = f [ 2 ] - f [ 1 ] 再来推，可以发现第6次的时候得到的 f [ 6 ] = f [ 2 ] - f [ 1 ]。
1. 找规律：
#include
using namespace std;
int main(){
int x,y;
while(cin>>x>>y){
int n;
cin>>n;
int f1=x;
int f2=y;
int f3;
if(n==1){
if(x<0)
cout<<(1000000007+x)< 2. 矩阵快速幂，这个方法有固定的步骤，把矩阵构造出来就好了。代码如下：
#include
#include
using namespace std;
const int maxn=2;
const long long mod=1000000007;
struct Matrix{
long long mat[maxn][maxn];
};
Matrix unit;
Matrix mul(Matrix a,Matrix b){
Matrix c;
for(int i=0;
i>x>>y>>n;
if(n==1){
if(x<0)
cout< 【ACM|Jzzhu and Sequences(CF #257 Div. 2)】
推荐阅读
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- 解题报告|51nod 1667 概率好题
- ACM|HDU 5322 Hope (CDQ分治+NTT)