P2974 組合數學

2022-09-22 22:36:55 字數 544 閱讀 7670

有 n 個木塊排成一行,從左到右依次編號為 1 至 n。

你有 k種顏色的油漆,第 i 種顏色的油漆足夠塗 \(c_i\)個木塊。

所有油漆剛好足夠塗滿所有木塊,即\(\sum_^kc_i\)

由於相鄰兩個木塊塗相同色顯得很難看,所以你希望統計任意兩個相鄰木塊顏色不同的著色方案。

由於答案可能很大,請輸出對 1e9+7 取模的結果。

資料範圍:對於100% 的資料,\(1<=k<=15,1<=c_i<=5\)

本題資料範圍較小,所以可以構造多維的陣列,進行記憶化搜尋,\(dp[a][b][c][d][e][k]\)表示能塗1-5塊木板的數目為a-e,同時上一個木板所塗的顏色為k

#includeusing namespace std;

namespace zzc

void work()

long long ans=dfs(c[1],c[2],c[3],c[4],c[5],0);

cout<}int main()