欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【组合计数】[JZOJ4391] 装饰

程序员文章站 2022-06-28 12:45:57
...

Description

【组合计数】[JZOJ4391] 装饰
【组合计数】[JZOJ4391] 装饰

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

剩下的颜色必然是成对成对放了,两种颜色数目相同
,用可以空的隔板法可知,这样的方案数是(Ytc1+t+k1t+k1)
k段奇数段有c1段是Y颜色多的,那么是(kc1)
t+k段,有t段为偶数,是(t+kt)
t段偶数段,每段都有两种放法,那么是2t
全部乘起来就是了。

注意最后答案还要乘以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);
}
相关标签: 排列组合 计数