首页 > 其他分享 >牛客小白月赛61-E-排队

牛客小白月赛61-E-排队

时间:2024-03-14 22:30:05浏览次数:27  
标签:return 61 int exgcd 牛客 逆元 小白月赛 rec mod

很好的一道题啊,学到了不少东西!!!!

首先是一个结论

逆序对总数 =    n! / 2  * 不相等的数字对数

(1) 不相等的数字对数怎么求

        结论        不相等的数字对数 = C(n,2) - ∑C(2,cnt(i))(i数字的出现次数)

(2) n! / 2 怎么处理,有取模的除运算怎么处理???

这块一直不会,今天一学才发现,就是之前学过的乘法逆元,学过就忘,不愧是我(doge

这里只说怎么处理,证明之类的不写了

a / b % mod 的情况,可以求b的乘法逆元

下面是两种求法

(1) p为质数

        b的乘法逆元  x = qpow(b,mod - 2,mod),费马小定理,注意是mod - 2

(2)p不是质数

        那么就得用扩展欧几里得算法了

        实现代码

        

void Exgcd(int a, int b, int& x, int& y) {
		if (!b) x = 1, y = 0;
		else Exgcd(b, a % b, y, x), y -= a / b * x;
}

       对于求 a / b % mod的问题 用扩展欧几里得算法

      各参数含义:

        a: 这里的a其实是a / b里的b

        b:这里的b其实是p

        x:要求的逆元

        y:不知道

        注意,扩展欧几里得是可以有返回值的,这个返回值的意义就是a,b的gcd

   其实是exgcd(b,p,逆元x,路人y) return = b,p的gcd,不过这里用不到

求出逆元以后,就可以用 n! * 逆元 * 求出的不相等的数字数 % mod了

// Problem: 排队
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/46597/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Date: 2024-03-14 21:21:51
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define endl '\n'
#define int int64_t
using namespace std;
int a[100005],rec[100005];
const int mod = 1e9 + 7;
int fac(int x) {
	if (rec[x]) return rec[x];
	if (x == 0)
		return rec[0] = 1;
	return 
		rec[x] = (fac(x - 1) * x) % mod;
}
int qpow(int a,int b) {
	int res = 1;
	while (b) {
		if (b & 1)res = res * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return res;
}
int C2(int x) {
	return x * (x - 1) / 2;
}
void exgcd(int a,int b,int&x ,int& y) {
	if (!b) x = 1, y = 0;
	else exgcd(b, a % b, y, x), y -= a / b * x;
}
void solve() {
	int n; cin >> n;
	fac(n);
	unordered_map<int, int>p;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[a[i]]++;
	}
	//逆序对总数 = n! / 2 * 不相等的数字对数
	int x, y;
	exgcd(2,mod, x, y);
	x = (x % mod + mod) % mod;
	int l = (rec[n] * x) % mod;
	/*cout << "x = " << x << endl;
	cout << "rec[n] = " << rec[n] << endl;*/
	int r = C2(n);
	for (auto k : p) {
		r -= C2(k.second);
	}
	/*cout << "l = " << l << endl;
	cout << "r = " << r << endl;*/
	cout << l * r % mod << endl;
}
signed main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

标签:return,61,int,exgcd,牛客,逆元,小白月赛,rec,mod
From: https://blog.csdn.net/aiwangyi6/article/details/136723399

相关文章

  • 洛谷 P3261 [JLOI2015] 城池攻占 题解
    题目分析其他人要么倍增,要么左偏树,那我就来讲讲朴实无华的dfs序加上线段树的做法。首先发现题目中明确指出了作乘法的时候一定是乘上一个大于零的数,这是为什么呢?首先把可以占领当前城池的战斗力的不等式列出来:\[h_j\le\left\{\begin{array}{c}s_i\timesv_j&&{a_j=......
  • [牛客]小红的数组分配
    题目思路去考虑sort排序为相同数字为偶数个,输出格式错误的去思考了数组为pair代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e6+10;inti,j,k,n,m,t,res,a[N]={0};strings;voidslove(){ cin>>n; for(i=0;i<n*2;i++)ci......
  • [牛客]小红的正整数
    题目思路我的思路:排好序后找到几个0,在将最后一个0的右边一位输出,再根据0的个数输出0,再输出其余数字别人思路:排好序后将0右边一个和第一个0交换后,直接输出代码#include<bits/stdc++.h>usingnamespacestd;intmain(){chara[6]={};cin>>a;......
  • 617. 合并二叉树c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*mergeTrees(structTreeNode*root1,structTreeNode*root2){if(!root1&&!roo......
  • 《牛客》-D小红数组操作 (链表)
    思路:采用链表进行动态维护即可我们采用map集合来模拟链表结构(用结构体也是可以的)就是输出需要一点点思考.ACcode:#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongmap<int,int>l,r;intq,x,y,op,k;voidsolve(){ cin>>q; while(q--){ cin>>o......
  • leetcode: 2861. 最大二进制奇数
    给你一个 二进制 字符串 s ,其中至少包含一个 '1' 。你必须按某种方式 重新排列 字符串中的位,使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。以字符串形式,表示并返回可以由给定组合生成的最大二进制奇数。注意 返回的结果字符串 可以 含前导零。示例......
  • 开题顺序(暴搜&dfs)---牛客小白月赛69-C
    #include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'#defineinf0x3f3f3f3fconstintN=2e5+5;intn,t,p;inta[N],b[N],c[N],x[N],y[N];intres,vis[N];voiddfs(ints,intm){ res=max(res,s); for(inti=1;i......
  • 旅游(最小生成树&二分)---牛客小白月赛69-D
    #include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'#defineinf0x3f3f3f3fconstintN=4e4+5;intn,m,c;intp[N];structnode{ intx,y,w; booloperator<(constnode&t)const{ returnw<t.w; ......
  • LeetCode[题解] 1261. 在受污染的二叉树中查找元素
    首先我们看原题给出一个满足下述规则的二叉树:root.val==0如果 treeNode.val==x 且 treeNode.left!=null,那么 treeNode.left.val==2*x+1如果 treeNode.val==x 且 treeNode.right!=null,那么 treeNode.right.val==2*x+2现在这个二叉树受到「污......
  • 【牛客】-E 小红勇闯地下城
    一语点醒雾中人:看出最短路问题(dijkstra)ACocde:#include<bits/stdc++.h>usingnamespacestd;constintN=1000;#defineintlonglongintdx[5]={0,-1,0,1,0};intdy[5]={0,0,1,0,-1};structE{ intw; intx,y; booloperator<(constE&u)c......