[洛谷P5367]【模板】康托展开

分手后的思念是犯贱 2021-12-09 21:11 297阅读 0赞

**题目大意：**给定一个$n$的排列，求它在$n$的全排列中的名次

**题解：**康托展开，对于一个全排列，第$i$为有$n+1-i$种选择，用变进制数表示，这一位就是$n+1-i$进制。记排列中第$\[1,i)$中比第$i$位小的数个数位$a$，变进制数中第$i$位的数为$i-a-1$。可以用树状数组维护

**卡点：**无

**C++ Code：**

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #define maxn 1000010
    #define mul(a, b) (static_cast<long long> (a) * (b) % mod)
    const int mod = 998244353;
    
    inline void reduce(int &x) { x += x >> 31 & mod; }
    int fac[maxn], ans = 1, n;
    
    namespace BIT {
    	int V[maxn], res;
    	inline void add(int p) { for (; p <= n; p += p & -p) ++V[p]; }
    	inline int query(int p) { for (res = 0; p; p &= p - 1) res += V[p]; return res; }
    }
    
    int main() {
    	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    	std::cin >> n;
    	fac[0] = 1;
    	for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
    	for (int i = 1, x; i <= n; ++i) {
    		std::cin >> x;
    		reduce(ans += mul(x - BIT::query(x) - 1, fac[n - i]) - mod);
    		BIT::add(x);
    	}
    	std::cout << ans << '\n';
    	return 0;
    }

转载于:https://www.cnblogs.com/Memory-of-winter/p/11161585.html

发表评论取消回复

表情：

评论列表（有 0 条评论，297人围观）

还没有评论，来说两句吧...

相关阅读

相关 ACM模板——康托展开

1 include<iostream> 2 include<cstdio> 3 include<cstring> 4 define _fo

红太狼/ 2023年06月01日 08:49/ 0 赞/ 15 阅读

相关康托展开与逆康托展开

康托展开 int cantor(int a,int n) { int ans=0; for(int i=0;i<n;i+

桃扇骨/ 2023年03月04日 08:16/ 0 赞/ 35 阅读

相关洛谷P1379 八数码难题（提高+/省选-）广度优先BFS+康托展开；我做出了一道蓝题！使用广度优先BFS+康托展开

P1379 八数码难题题目描述在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要

ゝ一世哀愁。/ 2022年11月09日 11:21/ 0 赞/ 133 阅读

相关排列序列（康托展开）

X星系的某次考古活动发现了史前智能痕迹。这是一些用来计数的符号，经过分析它的计数规律如下：（为了表示方便，我们把这些奇怪的符号用a~q代替） abcdefgh

﹏ヽ暗。殇╰゛Y/ 2022年06月18日 07:06/ 0 赞/ 178 阅读

相关康托展开和逆展开

解析http://www.2cto.com/kf/201311/260148.html //展开，给你一个排列，让你求这是第几个排列 //逆展开，给你一个数n

骑猪看日落/ 2022年06月18日 06:07/ 0 赞/ 194 阅读

相关详解--康托展开

康托展开： X=an\(n-1)!+an-1\(n-2)!+…+ai\(i-1)!+…+a2\1!+a1\0! ai为整数，并且0<=ai<i(1<=i<=n) 应

àì夳堔傛蜴生んèń/ 2022年06月10日 12:27/ 0 赞/ 205 阅读

相关康托展开

康托展开是一个全排列到一个[自然数][Link 1]的[双射][Link 2]，常用于构建[哈希表][Link 3]时的空间压缩。康托展开的实质是计算当前排列在所

古城微笑少年丶/ 2022年05月17日 22:49/ 0 赞/ 229 阅读

相关【算法】康托展开和逆康托展开

文章目录康拓展开逆康拓展开康拓展开 > 康托展开是一个全排列到一个自然数的双射，常用于构建hash表时

你的名字/ 2022年04月01日 06:20/ 0 赞/ 227 阅读

相关 [洛谷P5367]【模板】康托展开

题目大意：给定一个$n$的排列，求它在$n$的全排列中的名次题解：康托展开，对于一个全排列，第$i$为有$n+1-i$种选择，用变进制数表示，这一位就是$n+1-i$进制。

分手后的思念是犯贱/ 2021年12月09日 21:11/ 0 赞/ 298 阅读

相关洛谷 P1098 字符串的展开

洛谷 P1098 字符串的展开传送门 [I'm here!][I_m here] -------------------- 思路大暴力字符串题这

亦凉/ 2021年11月16日 11:32/ 0 赞/ 358 阅读