牛牛在農(nóng)場飼養(yǎng)了n只奶牛,依次編號為0到n-1, 牛牛的好朋友羊羊幫牛牛照看著農(nóng)場.有一天羊羊看到農(nóng)場中逃走了k只奶牛,但是他只會告訴牛牛逃走的k只奶牛的編號之和能被n整除茫蛹。你現(xiàn)在需要幫牛牛計算有多少種不同的逃走的奶牛群。因為結(jié)果可能很大,輸出結(jié)果對1,000,000,007取模奈偏。
例如n = 7 k = 4:
7只奶牛依次編號為0到6, 逃走了4只
編號和為7的有:{0, 1, 2, 4}
編號和為14的有:{0, 3, 5, 6}, {1, 2, 5, 6}, {1, 3, 4, 6},{2, 3, 4, 5}
4只牛的編號和不會大于18,所以輸出5.輸入描述:
輸入包括一行,兩個整數(shù)n和k(1 ≤ n ≤ 1000),(1 ≤ k ≤ 50),以空格分割鲫售。輸出描述:
輸出一個整數(shù)表示題設(shè)所求的種數(shù)宦芦。輸入例子:
7 4輸出例子:
5
看了下網(wǎng)的一些解法，基本的dp狀態(tài)方程都是可以寫對的萍虽。問題再于實現(xiàn)時候的上來就使用狀態(tài)壓縮了，而且也沒解釋明白形真，看得一頭霧水杉编。這里寫一下過程
首先定義
使用dp[i][j][t]表示前i+1頭奶牛中選取j頭的和除以n余為t的方案數(shù)超全。
- 這里是i+1頭，所以i的取值范圍是0~n-1的邓馒。
- j的取值是可以取0的嘶朱，也就是一頭都沒逃走，j在循環(huán)里面的最大值是i和k的最小者光酣。
好了疏遏，接下來是狀態(tài)方程
則方案分為兩種：選取了第i頭奶牛和沒有選取第i頭奶牛兩個子問題
沒有選擇第i頭奶牛的方案數(shù)： dp[i?1][j][t]
選擇第i頭奶牛的方案數(shù)：dp[i?1][j?1][((t+n)?i)%n]
解釋一下這個((t+n)?i)%n，第一救军，因為選了第i頭牛财异，所以剩下的余數(shù)應該是用t-i，但是因為可能會出現(xiàn)負數(shù)唱遭，所以再加個n戳寸。然后再用n取余，就可以得到減去i之后拷泽，余數(shù)應該是多大疫鹊。
下面先不用狀態(tài)壓縮來實現(xiàn)算法：
int func(int n, int k) {
vector<vector<vector<int>>> dp;
vector<int> vec1;
vector<vector<int>> vec2;
vec1.resize(n); //因為只能取0~n-1共n個數(shù)
vec2.resize(k + 1, vec1); //可以取0~k共k+1個數(shù)
dp.resize(n, vec2); //因為只能取0~n-1共n個數(shù)
for (int m=0; m<n; m++) {//先初始化全部元素都為0
for (int i = 0; i<k+1; i++) {
for (int j=0; j<n; j++) {
dp[m][i][j] = 0;
}
}
}
//初始賦值 ,i = 0時， 存在1頭牛司致，選出0個拆吆，余n為0，這是一種唯一方案脂矫； 選出1個锈拨，余n為0，也是一種唯一方案
dp[0][1][0] = dp[0][0][0] = 1;
for (auto i = 1; i < n; i++) {//前i+1頭奶牛
{
for (auto j = 0; j <= MIN(k, i+1); j++)//選擇j頭奶牛羹唠。因為i對應有i+1頭牛
{
for (auto t = 0; t < n; ++t)//余t
{
if (j > 0) { //因為這里會涉及到 j-1奕枢，需要確保它打于0
dp[i][j][t] = (dp[i-1][j][t] + dp[i-1][j - 1][((t + n) - i) % n]);
} else {
if (t == 0) { //當j==0的時候，也就是一頭牛都沒逃走佩微，那么這個時候余數(shù)必須是0才有值缝彬，取其他余數(shù)都是0
dp[i][j][t] = 1;
}
}
}
}
}
return dp[n-1][k][0];
}
這個算法沒啥好說的，就是按照狀態(tài)方程實現(xiàn)哺眯。然后留意一下初始化條件和j-1的狀態(tài)就行谷浅。
然后來看看狀態(tài)壓縮的。留意到狀態(tài)轉(zhuǎn)移方程奶卓，其實每次計算新的i的時候一疯，它只會用到i-1的二維數(shù)組的值。所以可以只使用一個二維數(shù)組去保存狀態(tài)值就行了夺姑。所以狀態(tài)方程可以寫成
dp[j][t] = (dp[j][t] + dp[j - 1][((t + n) - i) % n]);
因為賦值的時候是先取等號右邊的值去計算的墩邀，所以賦值語句是正確的。就像a=a+1盏浙，這個計算的a結(jié)果為原始的a+1一樣眉睹。
這里有一個問題就是dp[j - 1][((t + n) - i) % n]這一項荔茬，里面依賴了j-1這項，所以我們必須先計算j竹海，然后在計算j-1.否則的話慕蔚，如果先計算了j-1，那么這個j-1的所有項對應的i都會加1斋配，和j對應的i就對不上了孔飒。
int func2(int n, int k) {
vector<vector<int>> dp;
vector<int> vec;
vec.resize(n + 1);
dp.resize(k + 1, vec);
for (int i = 0; i<k+1; i++) {
for (int j=0; j<n; j++) {
dp[i][j] = 0;
}
}
dp[1][0] = dp[0][0] = 1; //網(wǎng)上有些寫法，只寫了dp[0][0] = 1其實是不對的
for (auto i = 1; i < n; i++)//前i+1頭奶牛
{
for (auto j = MIN(k, i+1); j > 0; --j)//選擇j頭奶牛艰争。
// 需要留意的就是這個十偶，這里必須用遞減來做，因為狀態(tài)方程依賴于j-1园细，
//如果我們使用遞增惦积，就會先計算了j-1，然后再計算j猛频，這樣狮崩，j-1就會變成了下一個循環(huán)的i。
//比如現(xiàn)在正在計算i=2鹿寻，計算完了j-1之后睦柴，j-1所對應的元素的值都會增加到對應i=3，
//然后你再計算j的時候毡熏，就會用到i=3的j-1的項坦敌。那樣就不對了。
{
for (auto t = 0; t < n; ++t)//余t
{
dp[j][t] = (dp[j][t] + dp[j - 1][((t + n) - i) % n]) ;
}
}
}
return dp[k][0];
}
