首页 > 其他分享 >[ABC134F] Permutation Oddness

[ABC134F] Permutation Oddness

时间:2023-08-15 19:14:55浏览次数:61  
标签:Oddness 盒子 int 转移 2j Permutation 匹配 ABC134F dp

题目大意

定义一个 \(1 \sim n\) 的排列 \(p\) 的「怪异度」为

\[\sum_{i=1}^n|p_i-i| \]

求「怪异度」为 \(m\) 的 \(1 \sim n\) 的排列数,答案对 \(10^9+7\) 取模。

思路

考虑把 \(p_i\) 和 \(i\) 看作小球与盒子,方便题意理解。

考虑球与盒子的匹配。

假设球在左侧,盒子在右侧,他们构成了一个二分图。

从上到下顺着排列每组球与盒子,球与盒子之间有一条横线。

我们发现,假设第 \(i\) 个盒子与 \(j\) 个球相连,他们之间的距离为 \(\left\lvert i - j \right\rvert\),他们产生的贡献相当于从 \(i\) 到 \(j\) 的连线穿过的横线的数量。

那么我们考虑状态如何设计,记 \(dp_{i,j,k}\) 表示已经匹配了前 \(i\) 行,有 \(j\) 组球与盒子未匹配,怪异度为 \(k\) 的方案数。

那么初始值为 \(dp_{0,0,0}=1\),答案为 \(dp_{n,0,m}\) 表示匹配了前 \(i\) 行,没有球与盒子未匹配,怪异度为 \(m\) 的方案数。

考虑转移,对于一行,有一个球和一个盒子,可以匹配 \(0,1,2\) 组三种可能,那么就分这三种情况进行转移。

匹配 \(0\) 组

都不匹配的话,应该是 \(dp_{i-1,j-1,k-2j}\)。

考虑第二维为什么是从 \(j-1\) 个未匹配组转移过来。

先考虑我们匹配 \(1\) 组的情况,我们新加入了 \(1\) 组,即第 \(i\) 行的球与盒子,又匹配了 \(1\) 组,那么新的没有匹配的组数没有发生变化,即第二维从 \(j\) 转移到 \(j\)。

那么匹配 \(2\) 组的情况,相比于匹配 \(1\) 组的情况多匹配了一组,所以要从 \(j + 1\) 转移到 \(j\);同理,匹配 \(0\) 组的情况就要从 \(j-1\) 转移到 \(j\)。

再考虑第三维。原本前面那些没有被匹配的盒子与球是可能被匹配到第 \(i\) 行及以后的,但是现在我们考虑的转移第 \(i\) 行并没有匹配这 \(j\) 组盒子与球。

那么这 \(j\) 组盒子与球只能匹配到第 \(i +1\) 行及以后,那么相等于我们前面的 \(j\) 组球与盒子又需要多穿过一条横线,那么总共 \(2j\) 个物品,就使得怪异值增加了 \(2j\),所以从 \(k-2j\) 转移过来。

匹配 \(1\) 组

将第 \(i\) 个球与前面的 \(i-1\) 行未被匹配的 \(j\) 个盒子进行匹配,有 \(j\) 种选择,每种选择的方案数为 \(j \times dp_{i-1,j,k-2j}\)。

用第 \(i\) 个盒子去匹配球的方案数同理。

第 \(i\) 个球连第 \(i\) 个盒子的方案数单独处理,为 \(dp_{i-1,j,k-2j}\)。

匹配 \(2\) 组

如果要匹配两组,那么第 \(i\) 行的球与盒子之间不能相互选择。

第 \(i\) 行的球与前 \(i-1\) 行的 \(j+1\) 个未匹配的盒子转移过来,盒子同理,根据乘法原理,有 \((j + 1)^2dp_{i-1,j+1,k-2j}\) 种方案。

状态转移方程

\[dp_{i,j,k}=j \times dp_{i-1,j,k-2j}+j \times dp_{i-1,j,k-2j}+dp_{i-1,j,k-2j}+(j+1)^2 \times dp_{i-1,j+1,k-2j}+dp_{i-1,j-1,k-2j} \]

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long MainType;

const int N = 55;
const int Mod = 1e9 + 7;

int n,m;

MainType dp[N][N][N * N];
// dp[i][j][k]
// 对于前 i 组有 j 组没有配对,怪异度为 k 的方案数 

int main() {
#ifdef ONLINE_JUDGE == 1
    freopen("genshin.in","r",stdin);
    freopen("genshin.out","w",stdout);
#endif

    cin >> n >> m;

    dp[0][0][0] = 1;

    for(int i = 1;i <= n; i++) {
        for(int j = 0;j <= i; j++) {
            for(int k = j * 2;k <= m; k++) {
                if(j < 1)
                    dp[i][j][k] = (dp[i - 1][j + 1][k - j * 2] * (j + 1) % Mod * (j + 1) % Mod + dp[i - 1][j][k - j * 2] * (j * 2 + 1) % Mod) % Mod;
                else
                    dp[i][j][k] = (dp[i - 1][j + 1][k - j * 2] * (j + 1) % Mod * (j + 1) % Mod + dp[i - 1][j][k - j * 2] * (j * 2 + 1) % Mod + dp[i - 1][j - 1][k - j * 2] % Mod) % Mod;
            }
        }
    }

    cout << dp[n][0][m] % Mod;

#ifdef ONLINE_JUDGE == 1
    fclose(stdin);
    fclose(stdout);
#endif
    return 0;
}

标签:Oddness,盒子,int,转移,2j,Permutation,匹配,ABC134F,dp
From: https://www.cnblogs.com/baijian0212/p/solution-at-abc134-f.html

相关文章

  • 2023牛客多校第九场 D Non-Puzzle: Error Permutation
    题意给定一个长度为n的序列,计算有多少个子区间满足子区间第K小的数不在子区间第K位。 找出所有不满足条件的区间。枚举所有的ai和左端点al,找出满足ai是区间[l,r]中第r-l+1小的右端点r,则右端点r一定是一段区间。例如   342165         l i ......
  • [ABC309G] - Ban Permutation 题解
    [ABC309G]-BanPermutation题解题目描述求长为\(N(N\leq100)\)且满足以下条件的排列\(P=(P_1,P_2,...,P_N)\)的个数,模\(998244353\):\(\forall1\leqi\leqN\),\(|P_i-i|\geqX(X\leq5)\)。思路首先拆绝对值,得到:\[P_i\geX+i\veeP_i\leX-i\]数数题除了排列......
  • Permutations 题解
    题目传送门一道枚举题。数据范围非常小,考虑暴力枚举全排列。可以dfs两次,第一次求出能使\(f(p)\)取得的最大值。第二次求出第\(m\)个排列。注意一下,第二次dfs的时候需要按字典序枚举。Code#include<bits/stdc++.h>#definelllonglong#defineINF1e9usingname......
  • next_permutation的简单实现
    next_permutation的简单实现​ 首先需要从后往前找到第一对数字满足nums[i]<num[j],i<j.此时记下这个i为l,在从后往前找到第一个大于nums[l]的数字,下标记为r.此时交换nums[l],nums[r].然后对数组内l以后的内容进行反转.如果找不到满足第一个条件的l,则对全部数组进行......
  • CF1844F Min Cost Permutation
    题面传送门先不考虑字典序的问题,只考虑最小值怎么求。先考虑一个特殊情况:\(c=0\),也就是说我想要相邻两项之差的绝对值最小。那么将其从小到大排序以后就满足要求。我们猜想实际上更一般的情况不会和这个差太多。不妨令\(c>0\),实际上最小值就在升序排列的时候取到。假设有四......
  • Atcoder Regular Contest 114 F - Permutation Division
    显然分成\(k\)段以后,最大化形成的排列的字典序的策略是将所有段按第一个元素的大小降序排列。由于最终排列的字典序肯定\(\ge\)原排列的字典序,因此我们考虑最大化最终排列与原排列的LCP,这部分就考虑二分答案,记\(dp_i\)表示以\(p_1\)开始\(p_i\)结尾的LDS的长度,那么......
  • CF1175F The Number of Subpermutations 对自己的警告--zhengjun
    太久没见过启发式合并了,然后没想出做法。首先笛卡尔树建出来。然后直接枚举跨过\(mid\)的长度为\(a_{mid}\)的区间,RMQ\(O(1)\)验证即可。发现这样的区间个数不超过左右区间大小的较小值,时间复杂度:\(O(n\logn)\)。代码#include<bits/stdc++.h>usingnamespacestd;us......
  • AtCoder Beginner Contest 309 G Ban Permutation
    洛谷传送门AtCoder传送门前置知识:[ARC132C]AlmostSorted看\(\geX\)不顺眼,怎么办呢!直接容斥!钦定\(j\)个位置满足\(|P_i-i|<X\),其余任意,就转化成了[ARC132C]AlmostSorted。具体一点就是,你设\(f_{i,j,S}\)表示前\(i\)位有\(j\)个位置满足\(|P_i-i|<......
  • Atcoder ARC159C Permutation Addition
    设\(s=\sum\limits_{i=1}^na_i\),考虑加上排列\(p\),那么\(s\leftarrows+\frac{n\times(n+1)}{2}\)。当有解时,因为\(a_i\)相等,所以有\(s\bmodn=0\)。考虑\(n\bmod2=1\)时,\(\frac{n\times(n+1)}{2}\bmodn=0\),所以\(s\bmodn=0\)时才会有解。......
  • next_permutation 函数
    next_permutation函数next_permutation是全排列函数。一、基本用法inta[];do{}while(next_permutation(a,a+n));二、例题[P1088[NOIP2004普及组]火星人]([P1088NOIP2004普及组]火星人-洛谷|计算机科学教育新生态(luogu.com.cn))#include<bits/stdc++.h......