首页 > 其他分享 >DPT Permutation

DPT Permutation

时间:2023-11-23 09:12:03浏览次数:26  
标签:DPT int ans include Permutation mod getchar

题意

给定 \(S \in ['>', '<']\)。表示排列 \(P\) 两点之间的大小关系。

求排列 \(P\) 的方案数。

Sol

排列方案,考虑 \(f_{i, j}\) 表示第 \(i\) 位的数在排列中排名为 \(j\) 的方案数。

  • 当 \(S_i = '>'\),\(f_{i, j} = \sum_{k = 1} ^ {j - 1} f_{i - 1, k}\)。
  • 当 \(S_i = '<'\),\(f_{i, j} = \sum_{k = j} ^ {i - 1} f_{i - 1, k}\)。

预处理是 \(trivial\) 的。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
string read_() {
	string ans;
	char c = getchar();
	while (c != '<' && c != '>')
		c = getchar();
	while (c == '<' || c == '>') {
		ans += c;
		c = getchar();
	}
	return ans;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 3005, mod = 1e9 + 7;

array <array <int, N>, N> f;
array <int, N> g;

void Mod(int &x) {
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}
int main() {
	int n = read();
	string s = " " + read_();
	f[1][1] = 1;
	for (int i = 1; i <= n; i++) g[i] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if (s[i - 1] == '<') f[i][j] = g[j - 1];
			else f[i][j] = g[i - 1] - g[j - 1];
			Mod(f[i][j]);
		}
		for (int j = 1; j <= i; j++)
			g[j] = g[j - 1] + f[i][j], Mod(g[j]);
	}
	write(g[n]), puts("");
	return 0;
}

标签:DPT,int,ans,include,Permutation,mod,getchar
From: https://www.cnblogs.com/cxqghzj/p/17850799.html

相关文章

  • CF1858C Yet Another Permutation Problem
    CF1858CYetAnotherPermutationProblemYetAnotherPermutationProblem-洛谷这题本来很简单,思路我也想到了,但是代码一直没写对,思路也一直换来换去(悲然而发现最开始的思路是对的题意Alex收到了一个名为"GCD排列"的游戏作为生日礼物。这个游戏的每一轮进行如下操作:......
  • 题解 P7972【[KSN2021] Self Permutation】
    怎么其他两篇题解都是\(O(n\logn)\)的,来发一个\(O(n)\)做法,当考前复习了。对原序列建出小根笛卡尔树,节点编号与原序列中的下标相同。记\(T_u\)表示以\(u\)为根的子树,\(lc(u),rc(u)\)分别表示\(u\)的左儿子和右儿子。设\(f_u\)表示删除若干\(T_u\)中的点(可以不删......
  • CF1542E2 Abnormal Permutation Pairs (hard version) 题解
    怎么会有这么离谱的题目啊。【模板】前缀和优化dp。思路考虑一个基本的东西。由于要求字典序的限制。我们可以枚举最长公共前缀计算。考虑如何求长度为\(i\)的排列有\(j\)个逆序对的数量。设\(dp_{i,j}\)。\[dp_{i,j}=\sum_{k=0}^{i-1}dp_{i-1,j-k}\]就是枚举新的......
  • [题解] CF1156E Special Segments of Permutation
    SpecialSegmentsofPermutation给你一个排列\(p\),求有多少个区间\([l,r]\)满足\(p_l+p_r=\max_{i\in[l,r]}p_i\)。\(n\le2\times10^5\)。按最大值分治,记当前的分治中心为\(mid\),分治区间为\([l,r]\)。然后需要计算跨分治中心的贡献。如果\(mid-l......
  • SP15637 GNYR04H - Mr Youngs Picture Permutations(线性 dp)
    题目求方案数,考虑dp——状态设计和边界——题目告诉了一个很显然的性质:每一排从左至右保证高度单调递减每一列从后往前保证高度单调递减那么可以发现,对于每一行,每一列,一定是按高度顺序插入,并且是连续插入,因为如果不连续,就无法保证单调递减的性质同时,它给出了另一个性......
  • CF213E Two Permutations
    CF213ETwoPermutations题解下文的\(a+x\)表示\(a_1+x,a_2+x,...a_n+x\)这个序列。发现\(n,m\)不大,所以可以枚举\(x\),然后快速判断是否合法。考虑如何快速判断一个\(x\)是否合法。注意到\(a,b\)都是排列。\(a_1+x,a_2+x,...a_n+x\)的数在\([1+x,n+x]\)范围内......
  • 「CF715E」Complete the Permutations
    \(\text{「CF715E」CompletethePermutations}\)\(\text{Link}\)\(\text{Describe}\)给定长为\(n\)的且部分确定的置换\(p,q\)。定义\(p,q\)距离为通过交换\(p\)任意两项变为\(q\)的最小步数,对于\(0\lek\len-1\)求通过补全\(p,q\)使得\(p,q\)距离为\(k\)的......
  • UVA1485 Permutation Counting
    传送门description一个长度为\(n\)的排列\(a\),其权值为满足\(a_i>i\)的位置的数量。求权值恰为\(k\)的长度为\(n\)的排列的方案数。\(n,k\leq1000\)solution设\(f_{i,j}\)表示考虑前\(i\)个数,钦定\(j\)个满足\(a_i>i\),这\(j\)个数排列的方案数。有转移......
  • [ABC299G] Minimum Permutation
    ABC229G洛谷链接atcoder链接容易发现如果最终答案有两个相邻的数\(b_i,b_{i+1}\)满足\(b_i>b_{i+1}\)且\(b_i\)之后出现过,则显然可以找到另一个不劣的答案不满足这个性质先说一个错误的结论:从前往后考虑,用链表维护答案,对于加入的一个数\(a_i\),如果之前在\(a_j\)出现......
  • #dp,二项式反演,容斥#CF285E Positions in Permutations
    题目问有多少个长度为\(n\)的排列\(P\)满足\(|P_i-i|=1\)的\(i\)的个数恰好为\(k\)个分析设\(dp_{i,j,k}\)表示前\(i\)个数钦定\(j\)个数满足上述条件且现在\(i\)和\(i+1\)因此被占用的方案数。那么第\(i\)个满足上述条件无非就是放入\(i-1\)或者\(......