舔狗舔到最后一无所有

NC20875. 舔狗舔到最后一无所有

描述

作为队伍的核心，forever97很受另外两个队友的尊敬。
Trote_w每天都要请forever97吃外卖，但很不幸的是宇宙中心forever97所在的学校周围只有3家forever97爱吃的外卖。
如果Trote_w给forever97买了别家的外卖，forever97就会大喊“我不吃我不吃”。
但是forever97又不喜欢连续三天吃一种外卖。
如果Trote_w哪天忘了这件事并且三天给他买了同一家外卖，那么forever97就会把Trote_w的头摁进手机屏幕里。
作为Trote_w的好朋友，你能告诉他连续请forever97吃n天饭，有多少不同的购买方法吗？

输入描述

多组样例
第一行一个整数T(1<=T<=20)代表测试样例数
接下来t行每行一个整数n，代表Trote_w要请forever97吃n天饭(1<=n<=100000)

输出描述

输出T个整数代表方案数，由于答案太大，你只需要输出mod 1e9+7 后的答案即可。

示例1

输入:

2
3
500

输出:

24
544984352

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3 解法, 执行用时: 104ms, 内存消耗: 80544K, 提交时间: 2022-07-26 14:30:31

N = 100010
M = int(1e9 + 7)
dp = [0] * (N)
dp[1],dp[2] = 3,9
for i in range(3,N):
    dp[i] = (dp[i - 1] + dp[i - 2])%M * 2 % M
for i in range(int(input())):
    n = int(input())
    print(dp[n])

Python3 解法, 执行用时: 67ms, 内存消耗: 10444K, 提交时间: 2021-11-28 15:40:05

ds=[3,9]
for i in range(2,100000+1):
    ds.append((ds[-1]*2+ds[-2]*2)%1000000007)
t=int(input())
for i in range(t):
    n=int(input())
    print(ds[n-1])

上一题

下一题

详情