題目描述：
調戲完了狗，ZCC開始玩起了積木。ZCC的面前有一塊 $ n \times n $ 的棋盤，他要用這些 $ 1 \times 1 $ 的積木在棋盤上搭出一個宏偉的建築。積木有三種顏色，ZCC認為一個建築要被稱為宏偉的應該滿足能從正面看到的每一個積木都是同一種顏色。現在，ZCC想要知道他能用他擁有的積木搭出多少種宏偉的建築。當然，為了讓建築足夠大，ZCC需要用完他所有的積木。兩個建築被稱為不同的當且僅當兩個建築形狀不同或者存在一塊相同位置不同顏色的積木。
算法標籤：DP
思路：
首先枚舉在視野可見的那一種顏色是什麼，那麼剩下兩種顏色實際上沒有差別，所以可以看作只有兩種顏色。
考慮DP
首先我們先單獨考慮一列的情況：
$g[i][j][k]$ 表示前 $i$ 行，已經用了 $j$ 個方塊，目前最高的色塊高度為 $k$ 的方案數。
$$
g[i][j][max(k,z)]+=g[i-1][j-z][k]
$$
(則有 $j$ 個方塊必須固定為某一種顏色，其他顏色可以隨機放)
$f[i][j][k]$ 表示前 $i$ 列，已經用了 $j$ 個方塊，有 $k$ 各方塊被強制為某一種顏色的方案數。
$$
f[i][j+x][k+y]+=f[i-1][j][k]*g[n][x][y]
$$
最後枚舉哪一種顏色有多少露在表面，乘上相應的組合數。
$$
\sum_{i=0}^{r}ans+=f[n][r+g+b][i]\times C_{r+g+b-i}^{r-i}\times C_{g+b}^{g}
$$
以下代碼：
#include<bits/stdc++.h>
#define il inline
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=100,p=1e9+7;
int r,G,b,n,c[N][N],g[N][N][N],f[N][N][N];
il int read(){
int x,f=1;char ch;
_(!)ch=='-'?f=-1:f;x=ch^48;
_()x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
il int mu(int x,int y){
if(x+y>=p)return x+y-p;
return x+y;
}
int main()
{
n=read();r=read();G=read();b=read();
int m=r+G+b,mx=max(max(r,G),b);
for(int i=0;i<=m;i++){
c[i][0]=1;
for(int j=1;j<=i;j++)c[i][j]=mu(c[i-1][j-1],c[i-1][j]);
}
g[0][0][0]=f[0][0][0]=1;
for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)
for(int k=0;k<=mx&&k<=j;k++)
for(int z=0;z<=mx&&z<=j;z++){
int kk=max(k,z);
g[i][j][kk]=mu(g[i][j][kk],g[i-1][j-z][k]);
}
for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)
for(int k=0;k<=mx&&k<=j;k++){
if(!f[i-1][j][k])continue;
for(int x=0;x+j<=m;x++)
for(int y=0;y+k<=mx&&y<=x;y++)
f[i][j+x][k+y]=mu(f[i][j+x][k+y],1ll*f[i-1][j][k]*g[n][x][y]%p);
}
int ans=0;
for(int i=0;i<=r;i++)ans=mu(ans,1ll*f[n][m][i]*c[m-i][r-i]%p*c[m-r][G]%p);
for(int i=0;i<=G;i++)ans=mu(ans,1ll*f[n][m][i]*c[m-i][G-i]%p*c[m-G][r]%p);
for(int i=0;i<=b;i++)ans=mu(ans,1ll*f[n][m][i]*c[m-i][b-i]%p*c[m-b][r]%p);
printf("%d\n",ans);
return 0;
}View Code
