首页 > 其他分享 >#dp,二项式反演,容斥#CF285E Positions in Permutations

#dp,二项式反演,容斥#CF285E Positions in Permutations

时间:2023-10-27 16:45:50浏览次数:41  
标签:int Positions inv Permutations 容斥 反演 fac dp mod

题目

问有多少个长度为 \(n\) 的排列 \(P\) 满足 \(|P_i-i|=1\) 的 \(i\) 的个数恰好为 \(k\) 个


分析

设 \(dp_{i,j,k}\) 表示前 \(i\) 个数钦定 \(j\) 个数满足上述条件且现在 \(i\) 和 \(i+1\) 因此被占用的方案数。

那么第 \(i\) 个满足上述条件无非就是放入 \(i-1\) 或者 \(i+1\),转移一下即可

然后至少有 \(i\) 个的方案数就是 \((dp_{n,i,0}+dp_{n,i,2})*(n-i)!\) 根据二项式反演容斥一下即可


代码

#include <iostream>
using namespace std;
const int N=1011,mod=1000000007;
int n,k,dp[N][N][4],fac[N],inv[N],f[N];
void Mo(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
long long C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k,fac[0]=fac[1]=inv[0]=inv[1]=1,
	dp[1][0][0]=dp[1][1][1]=1;
	for (int i=2;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
	for (int i=2;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for (int i=2;i<=n;++i) inv[i]=1ll*inv[i-1]*inv[i]%mod;
	for (int i=2;i<=n;++i)
	for (int j=0;j<i;++j)
	for (int k=0;k<4;++k)
	if (dp[i-1][j][k]){
    	Mo(dp[i][j][(k&1)<<1],dp[i-1][j][k]);
		Mo(dp[i][j+1][(k&1)<<1|1],dp[i-1][j][k]);
		if (k<2) Mo(dp[i][j+1][(k&1)<<1],dp[i-1][j][k]);
	}
	for (int i=0;i<=n;++i) f[i]=1ll*(dp[n][i][0]+dp[n][i][2])*fac[n-i]%mod;
	for (int i=0;i<=n;++i){
		for (int j=i+1;j<=n;++j)
		if ((j-i)&1) Mo(f[i],mod-f[j]*C(j,i)%mod);
		    else Mo(f[i],f[j]*C(j,i)%mod);
	}
	return !printf("%d",f[k]);
}

标签:int,Positions,inv,Permutations,容斥,反演,fac,dp,mod
From: https://www.cnblogs.com/Spare-No-Effort/p/17792678.html

相关文章

  • Codeforces Round 884 (Div. 1 + Div. 2) B. Permutations & Primes
    给一个正整数\(n\),你需要构造一个\(n\)的排列\(p_1,p_2,\cdots,p_n\)。对于排列\(p\)的每个子段\([l,r]\),\(mex_{i=l}^{r}a_i\)的结果为质数的次数尽可能多。此处的\(mex\)最小排除值最低为\(1\)而非\(0\)。不难想到,小质数\(2,3\)容易构造。于是有......
  • CF882E1+CF1882E2 Two Permutations 题解-构造题
    CF882E1+CF1882E2TwoPermutations题解-构造题哇,人类智慧,太智慧了。。。此题作为20231010联考的T3。感觉赛时根本没有去往这方面想。CF1882E1CF1882E2E1是简单版,就是没有要求操作数最小化。E1-EasyVersion方法1首先考虑没有次数限制的,对于单独的每一个串的情况。......
  • CodeForces 1882E2 Two Permutations (Hard Version)
    洛谷传送门CF传送门如何评价,模拟赛搬了一道,前一天晚上代码写了一半的题。考虑如何让操作次数最小。发现直接做太困难了。根本原因是,一次操作对序列的影响太大了。考虑做一些转化,减少一次操作对序列的影响。仍然先考虑一个排列怎么做。不知道为什么可以想到在排列前面添加特......
  • Min-Max 容斥学习笔记
    前言某次考试不会这个被打爆了,现在觉得可能有学习的必要。Min-Max容斥我们现在有一个全集\(U\),设\(\min(S)\)为集合\(S\)中的最小值,\(\max(S)\)为最大值。\[\max(S)=\sum_{T\subseteqS}(-1)^{|T|+1}\min(T)\\\min(S)=\sum_{T\subseteqS}(-1)^{|T|+1}\max(T)\\\]然......
  • 反射容斥
    故事的起因是模拟赛遇到了一道题:\(N,M\le1e7\)赛时想到了其实可以去枚举原地不动的步数,然后catalan去计算方案数,但是有一个问题,就是这个限制:这个过程不能走出格子这就相当于说我有一个栈,大小为m,要放入i个数,2*i次操作每次选择放入和拿出的方案数,但是栈不能取空,同时也不能爆栈......
  • 容斥定理
    01容斥定理容斥定理(简单情况)对任意两个有限集合 A 和 B ,有=+-其中,分别表示 A ,B 的元素个数.推广结论:对于任意三个有限集合 A , B , C ,有= ++---+有限集合的计数方法1:利用容斥定理的上述两个公式计算有限集合的元素个数.有限集合的计数方法2:文氏图法,即首先根......
  • 容斥原理应用Acwing890借鉴题解
    参考文献简单的容斥原理介绍请看下图:C++代码简单的容斥原理介绍请看下图:本题思路:将题目所给出的m个数可以看成是m位的二进制数,例如当p[N]={2,3}时,此时会有01,10,11三种情况而二进制的第零位表示的是p[0]上面的数字2,第1位表示p[1]上面的数字3所以当i=1时表示只选择2的......
  • CF1677D Tokitsukaze and Permutations
    好玩题。对于一个排列\(p\),进行\(k\)轮冒泡,记\(v_i=\sum_{j<i}[p_j<p_i]\),给定\(v_i\),部分值不确定,求合法的\(p\)的个数。\(p\)由\(v\)唯一确定。考虑一个个加数字进去,每次可以判断加入数字与前面数字的相对大小,于是可以确定原排列。只用研究\(v\),不用......
  • 容斥原理再再探
    前传,一年之期已到!来看一看gf去凑容斥系数!经典例题:20210620省队互测-qwaszxT2,jiangly的排列数数题,P7275计树一个组合对象由若干元素组成,但是元素直接可能可以合并,不能任意拼接。先假设可以任意拼接,然后对系数分配适当的容斥系数(此时一个方案的贡献要乘上所有元素的容斥系数......
  • 集合不相等容斥 笔记
    学习自zhouyuhang老师的ABC236Ex题解。其实就是完善了一下zhouyuhang老师没写的一些简单部分。我们先从一个经典的容斥理解:正难则反,我们钦定\(S\)内部全部相等,那么容斥系数是\((-1)^{|S|}\),于是答案就是\(\sum\limits_{S}(-1)^{|S|}f(S)\)。注意到这个集合不相等容斥......