#include<stdio.h>
int K,w,h;
int c[300]={0},cnt=0;
int block[300][300]={0},bcnt[300]={0};
int block2[300][300]={0},bcnt2[300]={0};
long long D[300][300]={0},d[300]={0};
long long D2[301][302]={0},sum[301][302]={0};
long long d2[301][302]={0},sum2[301][302]={0};
bool fil[301]={0};
int main()
{
int i,j,k,t;
scanf("%d%d%d",&K,&w,&h);
for(i=0;i<K;i++){ // block 입력
scanf("%d",&t);
for(j=0;j<cnt;j++){
if(c[j]==t){
block[j][bcnt[j]++]=i+1;
break;
}
}
if(j==cnt){
c[cnt]=t;
block[cnt][0]=i+1,bcnt[cnt]=1;
cnt++;
}
}
for(i=0;i<cnt;i++){ // 같은 색깔 블럭으로 만들어 질 수 있는 길이
fil[0]=true;
for(j=1;j<=w;j++) fil[j]=false;
for(j=1;j<=w;j++)
{
for(k=0;k<bcnt[i];k++){
if(j<block[i][k]) break;
if(fil[j-block[i][k]]){
fil[j]=true;
block2[i][bcnt2[i]++]=j;
break;
}
}
}
}
for(i=1;i<=w;i++){ // D[i][j] - i길이에서 j색으로 끝나는 가지수 , d[i] - i길이의 가지수
for(j=0;j<cnt;j++){
for(k=0;k<bcnt2[j];k++){
if(i<block2[j][k]) break;
else if(i==block2[j][k]){
D[i-1][j]++;
D[i-1][j]%=1000000007;
}
else{
D[i-1][j]+=d[i-block2[j][k]-1]-D[i-block2[j][k]-1][j];
if(D[i-1][j]<0) D[i-1][j]+=1000000007;
D[i-1][j]%=1000000007;
}
}
d[i-1]+=D[i-1][j];
d[i-1]%=1000000007;
}
}
for(i=1;i<=w;i++){
D2[i][0]=1,d2[i][0]=0,sum[i][0]=0;
D2[i][1]=sum[i][1]=d[i-1];
d2[i][1]=sum2[i][1]=1;
for(j=2;j<=h+1;j++){
if(i==1)
D2[i][j]=d2[i][j-1];
else{
D2[i][j]=d2[i-1][j];
for(k=1;k<=i-2;k++){
D2[i][j] += (sum[k][j-1]*sum2[w-k-1][j]%1000000007);
D2[i][j] %= 1000000007;
D2[i][j] -= (sum[k][j-2]*sum2[w-k-1][j-1]%1000000007);
if(D2[i][j]<0) D2[i][j]+=1000000007;
D2[i][j] %= 1000000007;
}
D2[i][j]+=D2[i-1][j-1];
D2[i][j]%=1000000007;
D2[i][j]+=D2[i][j-1];
D2[i][j]%=1000000007;
}
d2[i][j]=D2[i][j];
D2[i][j]=(D2[i][j] * d[i-1] % 1000000007);
sum[i][j]=sum[i][j-1]+D2[i][j];
sum[i][j]%=1000000007;
sum2[i][j]=sum2[i][j-1]+d2[i][j];
sum2[i][j]%=1000000007;
}
}
printf("%lld",sum2[w][h+1]);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
5340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
