题目描述:
调戏完了狗, ZCC 开始玩起了积木. ZCC 的面前有一块 $ n \times n $ 的棋盘, 他要用这些 $ 1 \times 1 $ 的积木在棋盘上搭出一个宏伟的建筑. 积木有三种颜色, ZCC 认为一个建筑要被称为宏伟的应该满足能从正面看到的每一个积木都是同一种颜色. 现在, ZCC 想要知道他能用他拥有的积木搭出多少种宏伟的建筑. 当然, 为了让建筑足够大, ZCC 需要用完他所有的积木. 两个建筑被称为不同的当且仅当两个建筑形状不同或者存在一块相同位置不同颜色的积木.
- $$
- g[i][j][max(k,z)]+=g[i-1][j-z][k]
- $$
- (则有 $j$ 个方块必须固定为某一种颜色, 其他颜色可以随机放)
- $$
- 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
来源: http://www.bubuko.com/infodetail-2985609.html