Description

紅藍球各無限多個.
初始時隨意地從中選擇 n 個, 扔入箱子
初始有一個空的序列
接下來依次做 m 組操作, 每組操作為依次執行下述三個步驟

(1) 從箱子中取出一個求插入序列尾

(2) 往箱子里補充 一紅一藍

(3) 從箱子中取出一個求插入序列尾
求 mm 次操作后, 有多少種不同的顏色序列, 答案對 109+7 取模

Input

第一行兩個數 n,mn,m .

Output

一個數 ans 表示答案對 10^9+7 取模的值.

Sample Input

# 樣例輸入12 3# 樣例輸入21000 10# 樣例輸入31000 3000

Sample Output

# 樣例輸出156# 樣例輸出21048576# 樣例輸出3693347555

HINT

樣例解釋1
一共有 6 個球會被從盒子中取出.
一個方案是不合法的當且僅當第 2,3,4,5 個球的顏色完全相同.

所以答案為 2^6?2^3=56

數據范圍

n,m≤3000

Sol

定義\(f[i][j]\)為進行i輪，紅球j個的方案數，然后跑普及組dp，但是這樣會重復，原因：一個最終序列可能是由多個初始集合生成的。但是我們發現，如果開始有i個紅球能夠生成一個序列，i+j個也可以，那么我們找到這個最小的i，可以發現一定會用完，所以再加一維\([0/1]\)表示有沒有用完過紅球，然后就不會有重復了。

Code

#include <cstdio> int n,m,f[3005][3005][2],ans;const int P=1e9+7; int main() {scanf("%d%d",&n,&m);f[0][0][1]=1;for(int i=1;i<=n;i++) f[0][i][0]=1;for(int i=0;i<m;i++) for(int j=0;j<=n;j++) for(int k=0;k<=1;k++){if(j) f[i+1][j-1][k|!(j-1)]=(f[i+1][j-1][k|(j==1)]+f[i][j][k])%P;if(n-j) f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%P;if(j) f[i+1][j][k|(j==1)]=(f[i+1][j][k|(j==1)]+f[i][j][k])%P;if(n-j) f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%P;}for(int i=0;i<=n;i++) ans=(ans+f[m][i][1])%P;printf("%d\n",ans); }

轉載于:https://www.cnblogs.com/CK6100LGEV2/p/9469383.html

總結

以上是生活随笔為你收集整理的【AGC013D】Pilling Up dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。