当前位置：首页 > news >正文

打卡信奥刷题（2606）用C++实现信奥题 P2476 [SCOI2008] 着色方案

news 2026/3/26 22:31:30

P2476 [SCOI2008] 着色方案

题目描述

有nnn个木块排成一行，从左到右依次编号为111至nnn。

你有kkk种颜色的油漆，第iii种颜色的油漆足够涂cic_ici个木块。

所有油漆刚好足够涂满所有木块，即∑i=1kci=n\sum_{i=1}^kc_i=n∑i=1kci=n。

由于相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。

由于答案可能很大，请输出对109+710^9+7109+7取模的结果。

输入格式

第一行，一个整数kkk，表示颜色数量。

第二行kkk个整数c1,c2,…,ckc_1,c_2,\dots,c_kc1,c2,…,ck，表示每种颜色能够涂木块的个数。

输出格式

一行一个整数，表示答案对109+710^9+7109+7取模的结果。

输入输出样例 #1

输入 #1

3 1 2 3

输出 #1

输入输出样例 #2

输入 #2

5 2 2 2 2 2

输出 #2

输入输出样例 #3

输入 #3

10 1 1 2 2 3 3 4 4 5 5

输出 #3

85937576

说明/提示

对于50%50\%50%的数据，1≤k≤51 \leq k \leq 51≤k≤5，1≤ci≤31 \leq c_i \leq 31≤ci≤3；
对于100%100\%100%的数据，1≤k≤151 \leq k \leq 151≤k≤15，1≤ci≤51 \leq c_i \leq 51≤ci≤5。

C++实现

#include<bits/stdc++.h>#defineRGregister#defineILinline#defineFill(a,b)memset(a,b,sizeof(a))usingnamespacestd;typedeflonglongll;constintZsy(1e9+7);IL llInput(){RG ll x=0,z=1;RGcharc=getchar();for(;c<'0'||c>'9';c=getchar())z=c=='-'?-1:1;for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);returnx*z;}intk,c[16],C[80][80],f[20][80],sum[16];ILvoidPrepare(){C[0][0]=1;for(RGinti=1;i<=75;++i){C[i][0]=1;for(RGintj=1;j<=75;++j)C[i][j]=(C[i-1][j]+C[i-1][j-1])%Zsy;}}intmain(RGintargc,RGchar*argv[]){Prepare();k=Input();for(RGinti=1;i<=k;++i)c[i]=Input(),sum[i]=sum[i-1]+c[i];f[1][c[1]-1]=1;for(RGinti=1;i<k;++i)for(RGintj=0;j<sum[i];++j){if(!f[i][j])continue;for(RGinta=1;a<=c[i+1];++a)for(RGintb=0;b<=a&&b<=j;++b){RGintret=1LL*f[i][j]*C[c[i+1]-1][a-1]%Zsy*C[j][b]%Zsy;ret=1LL*ret*C[sum[i]+1-j][a-b]%Zsy;(f[i+1][j+c[i+1]-a-b]+=ret)%=Zsy;}}printf("%d\n",f[k][0]);return0;}