「fjWC2015」圣诞树
「题目描述」
用m种颜色的彩球装点n层的圣诞树。圣诞树的第i层恰由l[i]个彩球串成一行，且同一层内的相邻彩球颜色不同，同时相邻两层所使用彩球的颜色集合不同。求有多少种装点方案，答案对p取模。
只要任一位置上的彩球颜色不同，就算作不同的方案。
「输入格式」
第一行三个整数n,m,p，表示圣诞树的层数、彩球的颜色数和取模的数。
接下来一行包含n个整数，表示l[i]。
「输出格式」
一个整数表示答案。
「样例输入」
3 2 1000
3 1 2
「样例输出」
8
「数据范围」
对于30%的数据，m <= 2, Σl[i] <= 10
对于60%的数据，n <= 20, l[i] <= 100
对于100%的数据，1 <= n,m <= 10^6, 2 <= p <= 10^9, 1 <= l[i] <= 5000, Σl[i] <= 10^7
题解
30%直接2^∑l[i]爆搜判断即可
100%
搬运coolinging神犇学长的题解
题目来源：CodeForces 140 E
考察要点：动态规划、组合数学
先考虑小问题：恰用j种颜色布置一行i个球的方案数dp[i][j]。
用类似于最小表示法的思想，我们要求x号颜色的首次出现位置必须比x+1号颜色的早，这样一来将所求得的方案数乘以颜色的全排列数j!就是原来的方案数。
若前i-1个球使用了j-1种颜色，则第i个球必然使用了第j种颜色；若前i-1个球已使用了j种颜色，则第i个球使用的颜色必须与第i-1个球不同，所以有(j-1)种方案。故可由简单的dp递推而得：
F[i][j] = F[i-1][j-1] + F[i-1][j] * (j-1)
现在考虑相邻两层之间的限制，用d[i][j]表示前i层中第i层恰用了j种颜色的方案数。因为使用的颜色数不可能多于球数，又总球数不超过10^7,故d[i][j]的状态总数也不超过10^7。
若不考虑两层之间的颜色集合需不同这一条件，则转移方程为
d[i][j] = (m!/(m-j)!) * F[l[i]][j] * Σd[i-1][k]
再减去不符合这一条件的部分即可：
d[i][j] = (m!/(m-j)!) * F[l[i]][j] * Σd[i-1][k] – d[i-1][j] * F[l[i]][j] * j!
其中(m!/(m-j)!)与j!都可以预处理得到
时间复杂度：O(Σl[i] + l[i]^2)
30分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<set> #include<map> #include<cstdio> #include<ctime> #include<cmath> #include<queue> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define rad 100000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,p,ans; int l[100005]; ll f[5005][5005]; int s[105],c[105]; int sum; bool jud() { int now=0; memset(s,0,sizeof(s)); for(int i=1;i<=n;i++) { for(int j=now+1;j<=now+l[i];j++) { if(j!=now+1&&c[j]==c[j-1])return 0; s[i]|=1<<(c[j]-1); } now+=l[i]; } for(int i=2;i<=n;i++)if(s[i]==s[i-1])return 0; return 1; } void solve(int k) { if(k==sum+1) { ans+=jud();ans%=p; return; } for(int i=1;i<=m;i++) { c[k]=i;solve(k+1); } } int main() { //freopen("christmas.in","r",stdin); //freopen("christmas.out","w",stdout); n=read();m=read();p=read(); for(int i=1;i<=n;i++)l[i]=read(),sum+=l[i]; solve(1); printf("%d\n",ans); return 0; } |
100分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,p; ll C[1000005],l[1000005],g[5005],fac[5005],pr[5005]; int f[5005][5005]; void pre() { C[0]=1; for(int i=1;i<=m;i++) C[i]=C[i-1]*(m-i+1)%p; f[0][0]=1; for(int i=1;i<=5000;i++) for(int j=1;j<=min(i,m);j++) { f[i][j]=(ll)f[i-1][j]*(j-1)%p+f[i-1][j-1]; f[i][j]%=p; } fac[1]=1; for(int i=2;i<=5000;i++)fac[i]=fac[i-1]*i%p; } void dp() { ll sum=1,tmp; for(int i=1;i<=n;i++) { tmp=0; for(int j=1;j<=l[i];j++) g[j]=(sum*C[j]%p*f[l[i]][j]%p-f[l[i]][j]*pr[j]%p*fac[j]%p+p)%p; for(int j=1;j<=l[i];j++) tmp=(tmp+g[j])%p; sum=tmp; for(int j=1;j<=l[i-1];j++)pr[j]=0; for(int j=1;j<=l[i];j++)pr[j]=g[j]; } printf("%I64d",sum); } int main() { //freopen("christmas.in","r",stdin); //freopen("christmas.out","w",stdout); n=read();m=read();p=read(); pre(); for(int i=1;i<=n;i++)l[i]=read(); dp(); return 0; } |
OI 课件=>
