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[],a[],sum[];
long long pow(long long a,long long b)
{
long long res=;
while(b)
{
if(b&)
{
res*=a;
res%=mod;
}
a*=a;
a%=mod;
b>>=;
}
return res;
}
void solve(long long n,long long m)
{
a[]=;
a[]=;
a[]=;
a[]=;
for(int i=;i<=n;i++)
{
a[i]=(a[i-]+a[i-]+a[i-]+a[i-])%mod;
}
for(int i=;i<=n;i++)
{
sum[i]=pow(a[i],m);
}
dp[]=;
for(int i=;i<=n;i++)
{
dp[i]=sum[i];
for(int j=;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 ;
}
上一篇:lldpcli 常用命令


下一篇:kafka学习(一)-背景及架构设计