【组合计数】[JZOJ4391] 装饰
Description
Solution
考虑将原问题转化
一列2个格子一定不同,那么我们用这一列没有出现的那个颜色代表这一列。
那么我们得到了一个新的长度为M的序列,容易发现一个序列会且仅会对应两个原来的方格图(上下颠倒),第三个条件就告诉我们这个序列相邻两个颜色不能相同,并且序列中红色有M-R个,绿色有M-G个,蓝色有M-B个
问题转化为有三种颜色,每种颜色有一定数量,求构成的序列数,要求相邻不能相同。
考虑先把一种颜色固定下来,再用另外两种颜色往里面放。
枚举序列第一个颜色是什么,那么我们必须要用另两种颜色将第一个颜色位置隔开
设我们枚举的这个颜色有X个,它将这个序列分割成了非空的X段或X-1段,另外两种颜色分别有Y个和Z个
考虑每一段中怎么放,如果这一段长度为偶数,那么用的另外两种颜色数目相同,长度确定时有两种不同的放法(看哪个颜色开头)。
如果这一段长度为奇数,那么一种颜色数目比另一种颜色数目多1,长度确定时只有一种放法。
不妨枚举有多少段长度为偶数,那么奇数的段数可以根据奇偶性直接计算出来
因为每一段必须非空,因此偶数长度段必须两种颜色都至少有一个,设枚举有t段长度为偶数,算出k段为奇数
因为两种颜色数目差已知,奇数段数也已知,可以解二元一次方程解出每种颜色多的段数分别有多少
分别设为c1与c2
则剩余的*颜色数为Y-t-c1,Z-t-c2
剩下的颜色必然是成对成对放了,两种颜色数目相同
,用可以空的隔板法可知,这样的方案数是
k段奇数段有c1段是Y颜色多的,那么是
t+k段,有t段为偶数,是
t段偶数段,每段都有两种放法,那么是
全部乘起来就是了。
注意最后答案还要乘以2
Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 2000005
#define LL long long
#define mo 1000000007
using namespace std;
int n,a[3];
LL js[N],ny[N],cf[N];
LL zh(LL n,LL m)
{
if(n==-1&&m==-1) return 1;
if(n<m) return 0;
return js[n]*ny[m]%mo*ny[n-m]%mo;
}
int main()
{
cin>>n>>a[0]>>a[1]>>a[2];
js[0]=ny[0]=js[1]=ny[1]=1;
cf[0]=1,cf[1]=2;
fo(i,2,2*n)
{
cf[i]=cf[i-1]*(LL)2%mo;
js[i]=js[i-1]*(LL)i%mo;
ny[i]=(-ny[mo%i]*(LL)(mo/i)%mo+mo)%mo;
}
fo(i,2,2*n) ny[i]=ny[i-1]*(LL)ny[i]%mo;
fo(i,0,2) a[i]=n-a[i];
LL s=0;
fo(i,0,2)
{
swap(a[i],a[0]);
LL s1=0;
for(int j=0;j<=a[0];j++)
{
int k=a[0]-j;
if(k%2!=(a[1]+a[2])%2) k--;
if(k<0) break;
int c1=(k+a[1]-a[2])/2,c2=(k+a[2]-a[1])/2;
if(c1<0||c2<0) continue;
s1=(s1+zh(k,c1)*zh(a[1]-j-c1+j+k-1,j+k-1)%mo*zh(j+k,k)%mo*cf[j]%mo)%mo;
}
s=(s+s1)%mo;
}
printf("%lld\n",s*(LL)2%mo);
}
上一篇: Mybatis从认识到了解
下一篇: 驾校老板娘加了我微信
推荐阅读
-
python编程(类的方法、三大特征、装饰器、组合、多态、设计模式)
-
洛谷P2606 [ZJOI2010]排列计数(组合数 dp)
-
BZOJ4517: [Sdoi2016]排列计数(组合数+错位排列)
-
[计数dp][组合数] JZOJ P1975 连边
-
Redux实现组合计数器的示例代码
-
【组合计数】[JZOJ4391] 装饰
-
python编程(类的方法、三大特征、装饰器、组合、多态、设计模式)
-
HDU 6350 2018HDU多校赛 第五场 Always Online(图论 + 并查集 + 组合计数)
-
POJ -- 3046、Ant Counting (多重集组合数,计数类dp)
-
CodeForces - 1260F Colored Tree(树链剖分 + 组合计数 + 树状数组)