关键词：
You are given a tetrahedron. Let‘s mark its vertices with letters A, B, C and D correspondingly.
An ant is standing in the vertex D of the tetrahedron. The ant is quite active and he wouldn‘t stay idle. At each moment of time he makes a step from one vertex to another one along some edge of the tetrahedron. The ant just can‘t stand on one place.
You do not have to do much to solve the problem: your task is to count the number of ways in which the ant can go from the initial vertex Dto itself in exactly n steps. In other words, you are asked to find out the number of different cyclic paths with the length of n from vertex D to itself. As the number can be quite large, you should print it modulo 1000000007 (109?+?7).
The first line contains the only integer n (1?≤?n?≤?107) — the required length of the cyclic path.
Print the only integer — the required number of ways modulo 1000000007 (109?+?7).
2
3
4
21
思路：
递推ans[n]=ans[n-1]*2+ans[n-2]*3，但是ans会很大，需要取模
取模后的ans可能已经不是ans了
(ans[n-1]%mod*2+ans[n-2]*3)%mod==(ans[n-1]*2+ans[n-2]*3)%mod 是否成立？
经过查阅
1.(a*b) mod M=(a mod M)*(b mod M) mod M
2.(a+b) mod M=(a mod M+b mod M) mod M;
#include<bits/stdc++.h> using namespace std; int main() long long n,ans,a=0,b=3,c=6; cin>>n; if(n<4) if(n==1)ans=a; else if(n==2)ans=b; else if(n==3)ans=c; for(int i=4;i<=n;i++) ans=(b*3+c*2)%1000000007; a=b; b=c; c=ans; cout<<ans<<endl; return 0;
codeforces631d.dreamoonlikessequences位运算^组合数递推(代码片段)
https://codeforces.com/contest/1330/problem/D给出d,m,找到一个a数组，满足以下要求：a数组的长度为n,n≥1;1≤a1<a2<?<an≤d；定义一个数组b：b1=a1, ∀i>1,bi=bi−1⊕ai ，并且b1<b2<?<bn−1<bn；求满足条件的a... 查看详情
在android中的地图上的两个名称之间寻找路线？
】在android中的地图上的两个名称之间寻找路线？【英文标题】：routefindingbetweentwodesignationonmapsinandroid?【发布时间】：2011-02-0307:26:56【问题描述】：我只想找到地图上位置之间的最短路径。我们必须通过该位置的地理点，然后单... 查看详情
happynecklace(矩阵快速幂+递推+取模)
题目链接ProblemDescriptionLittleQwantstobuyanecklaceforhisgirlfriend.Necklacesaresinglestringscomposedofmultipleredandbluebeads.LittleQdesperatelywantstoimpresshisgirlfriend,heknowsthatshewillliketheneckl 查看详情
hdu1207汉诺塔ii（递推）(代码片段)
汉诺塔IIProblemDescription经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞... 查看详情
cf935dfafaandancientalphabet概率dp(递推)(代码片段)
D.FafaandAncientAlphabet(简洁题意请往下翻)timelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputAncientEgyptiansareknowntohaveusedalargesetofsymbols towriteont 查看详情
cf697e&&cf696cplease
...简，然后对1e9+7取模。题解：首先我们可以轻易得到一个递推式：$d[i]=frac{{1-d[i-1]}}{2}$但递推式是不行的，我们要得到一个封闭形式。运用数列技巧，我们可以进行如下变换：$d[i]-frac{1}{ 查看详情
cf1105cayoubandlostarray——动态规划(代码片段)
...0]+dp[i-1][1]*num[2]+dp[i-1][2]*num[1]dp[i][1]和dp[i][2]的情况同理，递推到n，dp[n][0]就是我们要的答案。为什么是添加到尾部？不能插入到某个数字前吗？这样做会不会漏情况？实际上，插入到某个数字之前会带来重复（会有另一个数被顶... 查看详情
cf438dthechildandsequence(代码片段)
外国人的数据结构题真耿直唯一有难度的操作就是区间取模，然而这个东西可以暴力弄一下，因为一个数$x$被取模不会超过$logn$次。证明如下（假设$xMod y$）：如果$yleqfracx2$那么$x$取模之后会小于$fracx2$，而如果$y>fracx2... 查看详情
cf981cusefuldecomposition树/思维(代码片段)
...输出No。【分析】：因为是一棵树,所以如果要求任意两条路线至少有一个公共点,到最后,所有的路线都会有唯一的公共点.如果有两个公共点的话,就至少有两条路线只包含其中的一条路线,否则就会有环,有了环就不是树了.也就是... 查看详情
cf1140epalindrome-lessarrays(巧妙的递推)(代码片段)
LINK题意一个数组有些位置是???,你可以使用[1,k][1,k][1,k]填充满足最后对于i∈[1,n−2]i\\in[1,n-2]i∈[1,n−2]有ai!=ai+2a_i!=a_i+2ai!=ai+2,求方案数我们分成奇数索引构成的数组和偶数索引构成的数组分别考虑现在设奇... 查看详情
cf1140epalindrome-lessarrays(巧妙的递推)(代码片段)
LINK题意一个数组有些位置是???,你可以使用[1,k][1,k][1,k]填充满足最后对于i∈[1,n−2]i\\in[1,n-2]i∈[1,n−2]有ai!=ai+2a_i!=a_i+2ai!=ai+2,求方案数我们分成奇数索引构成的数组和偶数索引构成的数组分别考虑现在设奇... 查看详情
hdu1207汉诺塔ii（递推）
经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝... 查看详情
cf429bdp递推
DescriptionSummeriscoming!It‘stimeforIahubandIahubinatoworkout,astheybothwanttolookhotatthebeach.Thegymwheretheygoisamatrix a with n linesand m columns.Letnumber a[i 查看详情
cf438dthechildandsequence(代码片段)
CF438DTheChildandSequence 给定数列，区间查询和，区间取模，单点修改。n,m小于10^5 难点在于区间取模，类似于区间开方，如果这个区间的最大值$<=$$mod$，不对其进行操作，反之对区间里每个数进行操作（由于操作数很少）&... 查看详情
[递推]aw1208.翻硬币(递推+蓝桥杯第四届省赛cb)(代码片段)
...目来源链接：1208.翻硬币相同题，不同场景：[递推]aw3777.砖块(思维+递推+CF1271B)2.题目解析经典递推题目，思路和[递推]aw3777.砖块(思维+递推+CF1271B)一样，数据保证一定有解，无解情况需要判断操... 查看详情
cf492evanyaandfield(代码片段)
题目大意：一天，Vanya来到了一片滑稽树林中，准备采摘滑稽果。滑稽树林可看作一个 n×n 的正方形，其中 m 个点上有滑稽果，某些点没有。（注意一个点上可能有多个滑稽果）Vanya会沿向量 (dx,dy)(dx,dy) 方... 查看详情
数学意义上的四维正五面体在三维上展开有几种立体形状？
如同三维的正四面体在二维展开，他有三种形状，如图（自己画的，不太好看）问题任然有效你说是在三维展开吗，那个好说，就是5个正四面体，其中任何一个正四面体都和其他的4个正四面体共面。并且这个共同的面就是正四... 查看详情
技术路线的选择重要但不具有决定性[转]
...人也收到一封来信，写信人大意是说自己大学时选择.NET路线，一路 查看详情