[模拟赛] StopAllSounds

Description

小松鼠开心地在树之间跳跃着，突然她停了下来。因为眼前出现了一个拿着专克超萌小松鼠的法宝————超萌游戏机的游客！　超萌游戏机之所以拥有这个名字，是因为它的屏幕是一个n × 2的矩形。小松鼠接过游戏机，开始了她的第一个游戏：俄罗斯方块。　考虑到小松鼠的智商，游戏机里的方块只有下面四种，方块按顺序下落，

可以在任意时刻（甚至是下落前）对其进行不限次数的旋转操作。

由于四种方块最小宽度都为2，因此下落的时候在水平方向上是不能够移动的。我们称当前方块下落的过程完成了，当且仅当其再往下移动一个单位就会与之前覆盖的方块有部分相重叠。小松鼠想要知道，在这个n×2的游戏界面中，一共会出现多少种游戏状态。游戏状态指单次方块下落的过程完成后，不要求游戏结束（即不要求第1行非空），且界面中出现的必须是完整的方块。

两种游戏状态被认为是相同的，当且仅当游戏界面中的每一个格子两种状态下被覆盖的方块类型都相同（或都不被覆盖）。

如下图是两种不同的游戏状态
　　
再次考虑到小松鼠的智商，答案模109 + 7 输出。

Input

一行一个数n，表示游戏界面的长度。

Output

一个数，表示游戏界面的状态数在模109 + 7意义下的值。

Constraints

对于前10%，(n <= 10。)
对于前30%，(n <= 1000。)
对于前60%，(n <= 100000。)
对于100%， (n <= 1000000。)

Soluiton

大模拟递推

定义数组dp[N][6]
题目只有两列,所以所有的方块只有6种情况

dp[i][0~6]分别表示在第i种情况的方块落下后,第i行的方案数

结合代码理解一下很简单的

Code

#include<bits/stdc++.h>
#define il inline
#define rg register
#define lol long long
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)

using namespace std;

const int N=1e6+10;
const int inf=2e9;

lol ans;
int n;
lol dp[N][6];//0.左中 1.右中 2.上下 3.块 4.反L 5.倒L
const int mod=1e9+7;

void in(int &ans)
{
    ans=0; int f=1; char i=getchar();
    while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
    while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0', i=getchar();
    ans*=f;
}

int main()
{
    freopen("StopAllSounds.in","r",stdin);
    freopen("StopAllSounds.out","w",stdout);
    in(n);
    if(n==1) {
        cout<<1<<endl;
        return 0;
    }
    if(n==2) {
        cout<<2<<endl;
        return 0;
    }
    for(int i=0;i<=5;i++) dp[3][i]=1;
    dp[3][3]=0; dp[2][3]=1;
    for(int i=4;i<=n;i++) {
        dp[i][0]=(dp[i-3][0]+dp[i-2][1]+dp[i-2][2]+dp[i-3][3]+dp[i-2][4]+dp[i-3][5])%mod;
        dp[i][1]=(dp[i-2][0]+dp[i-3][1]+dp[i-3][2]+dp[i-3][3]+dp[i-3][4]+dp[i-3][5])%mod;
        dp[i][2]=(dp[i-3][0]+dp[i-2][1]+dp[i-2][2]+dp[i-3][3]+dp[i-2][4]+dp[i-3][5])%mod;
        dp[i][3]=(dp[i-2][0]+dp[i-2][1]+dp[i-2][2]+dp[i-2][3]+dp[i-2][4]+dp[i-2][5])%mod;
        dp[i][4]=(dp[i-3][0]+dp[i-3][1]+dp[i-3][2]+dp[i-3][3]+dp[i-3][4]+dp[i-3][5])%mod;
        dp[i][5]=(dp[i-3][0]+dp[i-2][1]+dp[i-2][2]+dp[i-3][3]+dp[i-1][4]+dp[i-3][5])%mod;
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=5;j++)
            (ans+=dp[i][j])%=mod;
    cout<<ans+1<<endl;
    return 0;
}