NO IMAGE

題目描述
邁克喜歡在火車旅行的時候用手機聽音樂,他有N首歌在手機裡,在整個火車途中,他可以聽P首歌,所以他想產生一個播放表產生P首歌曲,這個播放表的規則是:
·每首歌都要至少被播放一次
·在兩首一樣的歌中間,至少有M首其他的歌
邁克在想有多少種不同的播放表可以產生,那麼給你N,M,P,你來算一下,輸出結果取1000000007的餘數

輸入
輸入N,M,P
N範圍在1到100
M範圍在0到N
P範圍在N到100

輸出
輸出結果mod 1000000007的餘數
樣例輸入
1 0 3
樣例輸出
1
提示
其他樣例

1 1 3

0

2 0 3

6

50 5 100

222288991

題解
記錄到了第i個位置,已經用了j種顏色的方案數,我們不需要考慮第i個位置要放哪種歌,而是考慮能放幾種不同種類的歌。記憶化搜尋即可。

程式碼

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define mo 1000000007
using namespace std;
ll dp[105][105];
int n,m,p;
ll dfs(int i,int j)
{
if (dp[i][j]!=-1) return dp[i][j];
if (i==p)
{
if (j==n){dp[i][j]=1;return 1;}
else{dp[i][j]=0;return 0;}  
}
dp[i][j]=0;
if (j>m)dp[i][j]=dfs(i 1,j)*(j-m);
if (j<n)dp[i][j] =dfs(i 1,j 1)*(n-j);
if (dp[i][j]>=mo) dp[i][j]%=mo;
return dp[i][j];
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
for (int i=0;i<=p;i  )
for (int j=0;j<=n;j  )
dp[i][j]=-1;
printf("%lld",dfs(0,0));
return 0;
}