B. Jzzhu and Sequences(思维)Codeforces Round #257 (Div. 2)
程序员文章站
2022-06-04 19:37:55
...
原题链接: https://codeforces.com/problemset/problem/450/B
测试样例
Input
2 3
3
Output
1
Input
0 -1
2
Output
1000000006
Note
In the first sample, f2 = f1 + f3, 3 = 2 + f3, f3 = 1.
In the second sample, f2 = - 1; - 1 modulo ( 1 0 9 + 7 ) (10^9 + 7) (109 + 7) equals ( 1 0 9 + 6 ) (10^9 + 6) (109 + 6).
题意: 给出一个序列如下:
需要你求出 f n f_n fn mod 1 0 9 + 7 10^9+7 109+7的值。
解题思路: 这道题我们肯定不是无脑递归推下去的,这肯定不现实,那么我们该如何做呢?根据给定信息入手,既然 f i = f i − 1 + f i + 1 f_i=f_{i-1}+f_{i+1} fi=fi−1+fi+1。那么 f i = f i − 1 − f i − 2 f_i=f_{i-1}-f_{i-2} fi=fi−1−fi−2.又因为 f i − 1 = f i − 2 − f i − 3 f_{i-1}=f_{i-2}-f_{i-3} fi−1=fi−2−fi−3.这两个式子相加我们自然可以得到 f i = − f i − 3 f_i=-f_{i-3} fi=−fi−3。 故我们可以得到这个序列周期为6,则我们把前六个数求出来即可。注意,我们负数取模的规则为先加模再取模。
AC代码
/*
*邮箱:aaa@qq.com
*blog:https://me.csdn.net/hzf0701
*注:文章若有任何问题请私信我或评论区留言,谢谢支持。
*
*/
#include<bits/stdc++.h>//POJ不支持
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=a;i>=n;i--)
using namespace std;
const int inf=0x3f3f3f3f;//无穷大。
const int maxn=1e5;//限定值。
typedef long long ll;
const ll mod=1000000007;
ll a[6];
int n;
int main(){
while(cin>>a[0]>>a[1]){
cin>>n;
rep(i,2,5){
a[i]=(a[i-1]-a[i-2])%mod;
}
cout<<(a[(n-1)%6]+mod)%mod<<endl;
}
return 0;
}
推荐阅读
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #659 (Div. 2) A. Common Prefixes(字符串,思维)
-
Educational Codeforces Round 60 (Rated for Div. 2) ----A - Best Subsegment(思维题)
-
Codeforces Round #461 (Div. 2) B. Magic Forest(异或的性质)
-
构造思维+树形结构 Codeforces Round #612 (Div. 2) D题 Numbers on Tree
-
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)
-
Codeforces Round #583 (Div. 1 + Div. 2,) D. Treasure Island(dfs+思维)
-
Codeforces Round #659 (Div. 2) C、String Transformation 1(思维+set)
-
Codeforces Round #663 (Div. 2) B. Fix You
-
Codeforces Round #658 (Div. 2) B. Sequential Nim