题解 | #数字序列第n位的值#

动态规划

• 确定状态，记所有盘子移动从$AA$移动到$BB$状态为0，从$AA$移动到$CC$状态为1;

• 第$nn$步的状态为$dp[n][0]dp[n][0]$、$dp[n][1]dp[n][1]$，$dp[n][0]dp[n][0]$ 表示为所有盘子移动到$BB$所需要的次数，$dp[n][1]dp[n][1]$ 表示为所有盘子移动到$CC$所需要的次数。

• 第$nn$个盘子可以移动到$BB$时只需要移动1次，前$n-1n-1$个盘子一定全部都在$CC$上, 并且接下来要将$CC$上的所有盘子移动到$BB$上，此时所需要移动次数等同于将前$n-1n-1$个盘子从$AA$移动到$CC$上，因此此时的状态转移为:
  $dp[n][0]=1+dp[n-1][1]\ast 2dp[n][0]\; =\; 1\; +\; dp[n-1][1]\; *\; 2$

• 由此类推，所有盘子移动到$CC$时，一定是第$nn$个盘子先移动到$BB$之后，再移动到$CC$,即需要$22$步,而第$nn$个盘子移动到$BB$时，前$n-1n-1$个盘子一定全部都在$CC$上,移动次数为$dp[n-1][1]dp[n-1][1]$,且第$nn$个盘子要移动到$CC$时，前$n-1n-1$个盘子一定要移动到$AA$上，此时移动步数等价于将$n-1n-1$个盘子从$AA$移动到$BB$的步数，即$dp[n-1][0]dp[n-1][0]$,当第$nn$个盘子移动到$CC$之后，又要将前$n-1n-1$个盘子从$AA$移动到$CC$上。 因此此时的状态转移为：
  $dp[n][1]=1+dp[n-1][1]+1+dp[n-1][0]+dp[n-1][1]dp[n][1]\; =\; 1\; +\; dp[n-1][1]\; +\; 1\; +\; dp[n-1][0]\; +\; dp[n-1][1]$
  即:
  $dp[n][0]=1+dp[n-1][1]\ast 2dp[n][0]\; =\; 1\; +\; dp[n-1][1]\; *\; 2$
  $dp[n][1]=2+dp[n-1][1]\ast 2+dp[n-1][0]dp[n][1]\; =\; 2\; +\; dp[n-1][1]\; *\; 2\; +\; dp[n-1][0]$

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9+7;

ll dp[10000005][2];
int n;
int main(){
    cin>>n;
    
    dp[1][0] = 1;dp[2][0] = 5;
    dp[1][1] = 2;dp[2][1] = 7;
    
    for(int i = 3; i <= n; ++i){
        dp[i][0] = (1 + dp[i-1][1] * 2) % mod;
        dp[i][1] = (2 + dp[i-1][1] * 2 + dp[i-1][0]) % mod;
    }
    cout<<dp[n][0]<<' '<<dp[n][1]<<endl;
    return 0;
    
}