当前位置:网站首页>Lick the dog until the last one has nothing (simple DP)
Lick the dog until the last one has nothing (simple DP)
2022-07-06 19:24:00 【surowvv】
Title Description
As the core of the team ,forever97 He is respected by the other two teammates .
Trote_w Please... Every day forever97 Take out , But unfortunately, the center of the universe forever97 There are only 3 home forever97 Favorite takeout .
If Trote_w to forever97 Bought takeout from another family ,forever97 Will shout “ I don't eat I don't eat ”.
however forever97 I don't like to eat a takeout for three days in a row .
If Trote_w One day I forgot about it and bought him the same takeout for three days , that forever97 It will Trote_w Press your head into the screen of your mobile phone .
As Trote_w Good friends , You can tell him to keep asking forever97 eat n Tianfan , How many different ways to buy ?
Input description :
Multiple sets of samples The first line is an integer T(1<=T<=20) Represents the number of test samples Next t Each row is an integer n, representative Trote_w Please forever97 eat n Tianfan (1<=n<=100000)
Output description :
Output T An integer represents the number of schemes , Because the answer is too big , You just need to output mod 1e9+7 The answer after .
Example 1
Input
2
3
500
Output
24
544984352
analysis :
about a,b,c Three takeaways , Hypothesis number 1 i God eat a, Then the number of schemes is i-1 God eat a+ The first i-1 God eat b+ The first i-1 God eat c;
Among them the first i-1 God eat a when , The first i-2 It's impossible to eat a, Can only eat b or c.
So the first i God eat a Number of schemes Actually, it is No i-2 God eat b+ The first i-2 God eat c+ The first i-1 God eat b+ The first i-1 God eat c;
The same goes for the other two takeout .
The first i God eat b Number of schemes Actually, it is No i-2 God eat a+ The first i-2 God eat c+ The first i-1 God eat a+ The first i-1 God eat c;
The first i God eat c Number of schemes Actually, it is No i-2 God eat a+ The first i-2 God eat b+ The first i-1 God eat a+ The first i-1 God eat b;
All in all , The first i Number of prescriptions = The first i-2 Number of prescriptions *2+ The first i-1 Number of prescriptions *2;
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int f[100010];
int main()
{
int T;
cin >> T;
f[1] = 3, f[2] = 9;
while (T--) {
int x;
cin >> x;
for (int i = 3; i <= x; i++) f[i] = (f[i - 1] + f[i - 2]) % mod * 2 % mod;
cout << f[x] << endl;
}
return 0;
}
边栏推荐
- [translation] a GPU approach to particle physics
- JDBC details
- 史上超级详细,想找工作的你还不看这份资料就晚了
- 中缀表达式转后缀表达式详细思路及代码实现
- Solution of intelligent management platform for suppliers in hardware and electromechanical industry: optimize supply chain management and drive enterprise performance growth
- Computer network: sorting out common network interview questions (I)
- Pytorch common loss function
- Interface test tool - postman
- C # use Marshall to manually create unmanaged memory in the heap and use
- 三面蚂蚁金服成功拿到offer,Android开发社招面试经验
猜你喜欢
Fast power template for inverse element, the role of inverse element and example [the 20th summer competition of Shanghai University Programming League] permutation counting
ACTF 2022圆满落幕,0ops战队二连冠!!
MRO工业品企业采购系统:如何精细化采购协同管理?想要升级的工业品企业必看!
It's super detailed in history. It's too late for you to read this information if you want to find a job
全套教学资料,阿里快手拼多多等7家大厂Android面试真题
Benefit a lot, Android interview questions
CPU负载很低,loadavg很高处理方法
Help improve the professional quality of safety talents | the first stage of personal ability certification and assessment has been successfully completed!
零基础入门PolarDB-X:搭建高可用系统并联动数据大屏
Pytorch common loss function
随机推荐
助力安全人才专业素养提升 | 个人能力认证考核第一阶段圆满结束!
Qlabel marquee text display
Based on butterfly species recognition
Dark horse -- redis
Tensorflow and torch code verify whether CUDA is successfully installed
English topic assignment (25)
spark基础-scala
The list of people who passed the fifth phase of personal ability certification assessment was published
A popular explanation will help you get started
Excel 中VBA脚本的简单应用
Meilu biological IPO was terminated: the annual revenue was 385million, and Chen Lin was the actual controller
Zero foundation entry polardb-x: build a highly available system and link the big data screen
In 50W, what have I done right?
MRO industrial products enterprise procurement system: how to refine procurement collaborative management? Industrial products enterprises that want to upgrade must see!
Sanmian ant financial successfully got the offer, and has experience in Android development agency recruitment and interview
谷粒商城--分布式高级篇P129~P339(完结)
Mysql Information Schema 学习(一)--通用表
Use of deg2rad and rad2deg functions in MATLAB
今日直播 | “人玑协同 未来已来”2022弘玑生态伙伴大会蓄势待发
swagger2报错Illegal DefaultValue null for parameter type integer