2011 Michigan Invitational Programming Contest
2024-08-26 17:08:33
Crossings
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/gym/100463
Description
Given a permutation P of {0, 1, ..., n − 1}, we define the crossing number of it as follows. Write the sequence 0, 1, 2, . . . , n − 1 from left to right above the sequence P(0), P(1), . . . , P(n − 1). Draw a straignt line from 0 in the top line to 0 in the bottom line, from 1 to 1, and so on. The crossing number of P is the number of pairs of lines that cross. For example, if n = 5 and P = [1, 3, 0, 2, 4], then the crossing number of P is 3, as shown in the figure below. !""""#""""""""""""&" In this problem a permutation will be specified by a tuple (n, a, b), where n is a prime and a and b are integers (1 ≤ a ≤ n − 1 and 0 ≤ b ≤ n − 1). We call this permutation Perm(n, a, b), and the ith element of it is a ∗ i + b mod n (with i in the range [0, n − 1]). So the example above is specified by Perm(5, 2, 1).
Input
There are several test cases in the input file. Each test case is specified by three space-separated numbers n, a, and b on a line. The prime n will be at most 1,000,000. The input is terminated with a line containing three zeros.
Output
For each case in the input print out the case number followed by the crossing number of the permutation. Follow the format in the example output.
Sample Input
5 2 1
19 12 7
0 0 0
Sample Output
Case 1: 3
Case 2: 77
给你三个数n,a,b
满足第i个数等于(a*i+b)%n,然后问你逆序数是多少
这个n有1e6呢,所以树状数组和归并都能解决这个题吧
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+;
int d[N];
ll n,a,b;
void update(int x,int y) {
while(x<=n) {
d[x]+=y;
x+=x&-x;
}
}
int sum(int x) {
int s=;
while(x>) {
s+=d[x];
x-=x&-x;
}
return s;
}
int main() {
int k=;
while(~scanf("%lld%lld%lld",&n,&a,&b)) {
if(!n&&!a&&!b)
break;
memset(d,,sizeof(d));
ll ans=;
for(int i=; i<n; i++) {
int x=(a*i+b)%n+;
ans+=sum(x-);
update(x,);
}
printf("Case %d: %lld\n",k++,(n-)*n/-ans);
}
}
最新文章
- 如何在java中拟合正态分布
- c#winform窗体嵌入
- JSONModel - 字符串换转实体类
- hibernate generator class=xxx id详解
- UI学习笔记---第六天
- 【DB】SQLite学习笔记
- 提供他人class文件
- 2015 款 Macbook Pro 的 ForceTouch 触控板开启 三指拖动
- Nginx 配置基于域名的虚拟
- Ionic3学习笔记(五)动画之使用 animate.css
- IntelliJ IDEA如何设置头注释,自定义author和date
- HTML5 CSS3 诱人的实例: 3D立方体旋转动画
- Redis Sentinel集群双机房容灾实施步骤
- window.location.href 传参中文乱码问题!!!
- Cognos无法解密来着内容库的用户名和密码凭证
- centos 7.5安装docker-CE 18
- oracle 的查询问题!!!
- 软工1816 &#183; Beta冲刺(4/7)
- ant-jmeter批量脚本
- 现在就开始使用AngularJS的三个重要原因