一个包含四个点的完全图,可以在任意节点出发,可以在任意节点结束,给出每个点被经过的次数,求有多少种合法的遍历序列。如果两个序列至少有一位是不同的,则认为它们不相同。

Input

2 3 3 3

Sample Output

12336

题意:给a个A,b个B,c个C,d个D,求有少种排列,使得相邻的两个不同。

思路:用容斥来做,ans=所有排列-至少一个相邻+至少两个相邻-...+...。

假设有i堆a,则方案数位C(a-1,i-1),则a中至少a-i个相邻;同理; 则i堆a,j堆b,k堆c,l堆d,至少有N-i-j-k-l个相邻,其对应的排列数为 N!/(i!*j!*k!*l!);

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
#define MOD Mod
#define ll long long
const int G=;
const int Mod=;
const int maxn=;
int qpow(int v,int p)
{
int ans=;
for(;p;p>>=,v=1ll*v*v%Mod)
if(p&)ans=1ll*ans*v%Mod;
return ans;
}
void rader(int y[], int len) {
for(int i=,j=len/;i<len-;i++) {
if(i<j) swap(y[i],y[j]);
int k=len/;
while(j>=k) j-=k,k/=;
if(j<k) j+=k;
}
}
void NTT(int y[],int len,int opt) {
rader(y,len);
for(int h=;h<=len;h<<=) {
int wn=qpow(G,(MOD-)/h);
if(opt==-) wn=qpow(wn,Mod-);
for(int j=;j<len;j+=h) {
int w=;
for(int k=j;k<j+h/;k++) {
int u=y[k];
int t=(ll)w*y[k+h/]%MOD;
y[k]=(u+t)%MOD;
y[k+h/]=(u-t+MOD)%MOD;
w=(ll)w*wn%MOD;
}
}
}
if(opt==-) {
int t=qpow(len,MOD-);
for(int i=;i<len;i++) y[i]=(ll)y[i]*t%MOD;
}
}
int A[maxn],B[maxn],C[maxn],D[maxn],f[maxn],rev[maxn],a,b,c,d;
int main()
{
int N,K;
f[]=rev[]=;
rep(i,,) f[i]=(ll)f[i-]*i%Mod;
rev[]=qpow(f[],Mod-);
for(int i=;i>=;i--) rev[i]=(ll)rev[i+]*(i+)%Mod;
while(~scanf("%d%d%d%d",&a,&b,&c,&d)){
N=a+b+c+d;
memset(A,,sizeof(A));
memset(B,,sizeof(B));
memset(C,,sizeof(C));
memset(D,,sizeof(D));
rep(i,,a) A[i]=(ll)f[a-]*rev[i-]%Mod*rev[a-i]%Mod*rev[i]%Mod;
rep(i,,b) B[i]=(ll)f[b-]*rev[i-]%Mod*rev[b-i]%Mod*rev[i]%Mod;
rep(i,,c) C[i]=(ll)f[c-]*rev[i-]%Mod*rev[c-i]%Mod*rev[i]%Mod;
rep(i,,d) D[i]=(ll)f[d-]*rev[i-]%Mod*rev[d-i]%Mod*rev[i]%Mod;
int len=; while(len<=N) len<<=;
NTT(A,len,); NTT(B,len,);
rep(i,,len-) A[i]=(ll)A[i]*B[i]%Mod; NTT(C,len,);
rep(i,,len-) A[i]=(ll)A[i]*C[i]%Mod; NTT(D,len,);
rep(i,,len-) A[i]=(ll)A[i]*D[i]%Mod;
NTT(A,len,-); int opt,ans=;
if(N&) opt=; else opt=-;
rep(i,,N) (((ans+=(ll)opt*f[i]*A[i]%Mod)%=Mod)+=Mod)%=Mod,opt=-opt;
printf("%d\n",ans);
}
return ;
}

最新文章

  1. MySQL 游标
  2. angular初步认识一
  3. Popupwindow 的简单实用,(显示在控件下方)
  4. 匿名内部类--毕向东java基础教程学习笔记
  5. .Net 三款工作流引擎比较:WWF、netBPM 和 ccflow
  6. opencv通过dll调用matlab函数,图片作为参数
  7. Session 与cookies 的区别
  8. 【POJ】【3680】Intervals
  9. windows最基本命令行
  10. 算法Sedgewick第四版-第1章基础-001递归
  11. Qt 5中信号和槽的新语法
  12. 博客系统typecho的安装与使用
  13. 7 Best Free RAR Password Unlocker Software For Windows
  14. JavaWeb工程中web.xml基本配置(转载学习)
  15. EF 事务(转载)
  16. JAVA锁机制-可重入锁,可中断锁,公平锁,读写锁,自旋锁,
  17. phpize是什么
  18. Tomcat 服务器安装 SSL证书,实现 HTTP 自动跳转 HTTPS
  19. 前端安全之XSS
  20. flask 自定义验证器(行内验证器、全局验证器)

热门文章

  1. DNS域名解析的配置
  2. Nginx 自定义404、500错误页面跳转
  3. Refseq,accssion #,gi ,Ensembl的关系
  4. 当root用户无密码,非超级权限用户时提示mysqladmin: Can&#39;t turn off logging; error: &#39;Access denied; you need the SUPER privilege for this op解决方案
  5. Aware接口
  6. BI项目中的ETL设计详解(数据抽取、清洗与转换 )(转载)
  7. POJ - 2785 - 4 Values whose Sum is 0 - 二分折半查找
  8. Android -- 创建XML文件对象及其序列化, pull解析XML文件
  9. MySQL 入门篇
  10. python学习笔记(接口自动化框架 V1.0)