upc 训练赛 第九场 问题 G: 似魔鬼的步伐（思维题）

步伐（思维题）"/>

upc 训练赛 第九场 问题 G: 似魔鬼的步伐（思维题）

[提交] [状态] [命题人:admin]
题目描述
一步两步一步两步，一步一步似爪牙。似魔鬼的步伐。摩擦摩擦，在这光滑的地上摩擦摩擦，似魔鬼的步伐。似魔鬼的步伐。庞麦郎喜欢在光滑的地板上摩擦。假设他拥有N格体力。初始摩擦值为0，每次可以选择可以摩擦或者行走。摩擦消耗两格体力，第n次的摩擦值=第n-1次的摩擦值2+2。行走消耗一格体力，第n次的摩擦值=第n-1次的摩擦值1+1。求最大的摩擦值为多少？

输入
第一行有一个正整数K。
接下来有K行，每行有一个数N。
数据保证1≤K≤100 ,0≤N≤1 000 0。摩擦值对1 000 000 007取模。

输出
输出k行，第i行代表第i个数据的的结果

样例输入

2
1
5

样例输出

1
10

#include<cstdio>
#include<iostream>
#include<algorithm>
typedef long long ll;
const int mod = 1e9+7;
ll fiction;
using namespace std;void get(int n)
{while(n>0){if(n%2!=0){n--;;fiction=fiction*1+1;fiction%=mod;}else{n-=2;fiction=fiction*2+2;fiction%=mod;}}cout<<fiction<<"\n";
}int main()
{int k,n,cnt=0;cin>>k;while(cnt<k){fiction=0;cin>>n;get(n);cnt++;}return 0;
}

思路：首先，因为摩擦对摩擦力的影响是走路对摩擦力的影响的两倍，所以首先考虑摩擦这种方式。但是呢，有可能体力是奇数，这样就会有多的一点体力。所以，当体力值为奇数时，应该先用一次行走，当体力值为偶数时，都用摩擦。