hackerrank【Lego Blocks】:计数类dp

题目大意：

修一个层数为n，长度为m的墙，每一层可以由长度为1、2、3、4的砖块构成。

每一层都在同一个长度处出现缝隙是方案非法的，问合法的方案数有多少种

思路：

先求出总方案，再减去所有非法的方案数

总方案数容易求得，略

非法方案数就不太好求了，由于需要判重，我们可以按照 " 最左边的缝隙 " 所在的位置给非法方案数分类

这样就不会有重复了！

具体见代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define mod 1000000007
long long n,m;
long long dp[1010],a[1010],sum[1010];
long long pow(long long a,long long b)
{
    long long res=1;
    while(b)
    {
        if(b&1)
        {
            res*=a;
            res%=mod;
        }
        a*=a;
        a%=mod;
        b>>=1;
    }
    return res;
}
void solve(long long n,long long m)
{
    a[1]=1;
    a[2]=2;
    a[3]=4;
    a[4]=8;
    for(int i=5;i<=n;i++)
    {
        a[i]=(a[i-1]+a[i-2]+a[i-3]+a[i-4])%mod;
    }
    for(int i=1;i<=n;i++)
    {
        sum[i]=pow(a[i],m);
    }
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=sum[i];
        for(int j=1;j<i;j++)
        {
            dp[i]-=dp[j]*sum[i-j];
            dp[i]=(dp[i]%mod+mod)%mod;
        }
    }
    cout<<dp[n]<<endl;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cin>>n>>m;
        solve(m,n);
    }
    return 0;
}