考试
T1
给定 (a), (b), (c) 求
(a^b mod c)
1.2 输入格式
一行，空格隔开的三个数字，分别表示 (a); (b); (c)。
1.3 输出格式
一个数字，表示答案。
1.4 样例输入
2 3 3
1.5 样例输出
2
1.6 数据规模及约定
对于 30% 的数据， 1 ≤ (a); (b); (c) ≤ (10^6)
对于 60% 的数据， 1 ≤ (a); (b); (c) ≤ (10^9)
对于 100% 的数据， 1 ≤ (a; b; c) ≤ (10^{15})
显然快速幂搞定，但是(a,b)是(long long)范围，所以再来个龟速乘
一点补充：
如果我们要读高精度且有知道mod,我们可以边读边取模.
(鸣谢毒瘤Water_lift)
(Code)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int inf=2147483647;
inline ll read()
{
char ch=getchar();
ll x=0;bool f=0;//然鹅我这里看着1e15写成了int(甚至不知道自己为什么一共三个数要用快读）
while(ch<'0'||ch>'9')
{
if(ch=='-') f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f?-x:x;
}
ll a,b,c;
ll mul(ll x,ll y)
{
ll r=0;
while(y)
{
if(y&1) r=(r+x)%c;
x=x*2%c;
y>>=1;
}
return r;
}
ll ksm()
{
ll r=1;
while(b)
{
if(b&1) r=mul(r,a);
a=mul(a,a);
b>>=1;
}
return r;
}
int main()
{
freopen("nine.in","r",stdin);
freopen("nine.out","w",stdout);
a=read();b=read();c=read();
printf("%lld",ksm());
}
T2
2.1 问题描述
给定长度为 (n) 的序列 (a_i)。
求满足以下要求的 (i; j) 数对的数量。
• (i<j)
•(a_i > a_j)
• ((a_i + a_j)equiv0mod3)
2.2 输入格式
第一行一个整数 (n) 。
接下来一行，空格隔开的 (n) 个整数，表示 (a_i)。
2.3 输出格式
输出包含一个数字，表示答案。
2.4 样例输入
5
2 3 1 1 4
2.5 样例输出
2
2.6 样例解释
(1,3), (1,4) 满足要求
2.7 数据规模及约定
对于前 30% 的数据，$ n$ ≤ 2000。
对于前 60% 的数据， (n) ≤ 4 × (10^4)。
对于前 100% 的数据， 1 ≤ (n) ≤ (10^5), 0 ≤ (a_i) ≤ (10^6)
显然前两个条件是逆序对
归并做法：
归并排序可求逆序对个数
处理条件3：若((a+b) mod 3=0),则(a mod 3+b mod 3=0),所以我们可以每次都维护一个后缀和，计算(mod 3=0)，(mod 3=1)，(mod 3=2)的数的个数
(Code (from std))
#include<cstdio
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
int n;
int a[100005];
int b[100005];
int sum[100005][3];
LL ans;
void merge_sort(int l,int r){
if(l==r) return;
int mid=(l+r)/2;
merge_sort(l,mid);
merge_sort(mid+1,r);
for(int i=l;i<=r;i++) b[i]=a[i];
for(int i=mid;i>=l;i--){
if(i<mid) for(int j=0;j<3;j++) sum[i][j] = sum[i+1][j];//由于是从mid直接覆盖过来所以不用memset
sum[i][b[i]%3]++;
}
int i = l;
int j = mid+1;
int k = l;
while(i<=mid && j<=r){
if(b[i]<=b[j]){
a[k++]=b[i];
i++;
}else{
// solve
ans += sum[i][(3-b[j]%3)%3];
a[k++]=b[j];
j++;
}
}
while(i<=mid) a[k++] = b[i],i++;
while(j<=r) a[k++] = b[j],j++;//由于i已经到了mid,所以不需要再统计逆序对了
}
int main(){
freopen("teen.in", "r", stdin);
freopen("teen.out", "w", stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
merge_sort(1,n);
printf("%lld
",ans);
return 0;
}
树状数组做法：
可以开3棵树状数组，分别维护(mod 3=0,mod 3=1,mod 3=2)的数。因为树状数组我不会求后缀和，所以树状数组里记录的值(d)是(10^6+1)减原值，这样就要找使得((d+a) mod 3=1)的(a)
(Code)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int inf=2147483647;
inline ll read()
{
char ch=getchar();
int x=0;bool f=0;
while(ch<'0'||ch>'9')
{
if(ch=='-') f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f?-x:x;
}
int n,a[100009],b[1000009][3];
ll ans;
int hv[1000009];
const int all=(int)1e6+1;
void add(int d)
{
int md=d%3;hv[d]++;
while(md<0) md=(md+3)%3;
for(;d<=all;d+=(d&(-d)))
b[d][md]++;
}
ll sum(int d,int md)
{
ll r=0,dd=d;
while(md<0) md=(md+3)%3;
for(;d;d-=(d&(-d)))
r+=b[d][md];
if(dd%3==md&&hv[dd]) r-=hv[dd];
return r;
}
int main()
{
freopen("teen.in","r",stdin);
freopen("teen.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=n;i++)
{
int d=all-a[i];
ans+=sum(d,(1-d+3)%3);
add(d);
}
printf("%lld",ans);
}
T3
3.1 问题描述
给定一个长度为 n 的序列 ai, 和一个数字 k。
如果一个区间 a[l : r] 满足以下条件，称其为 (gamma) 区间。
• (l < r)
• (max_{l≤i≤r}a_i - min_{l≤i≤r}a_i ≤ k)
询问所有 (gamma) 区间的数字和。因为这个值很大，所以输出答案模 (10^9 + 7)的余数就好了。
因输入量较大，推荐使用以下函数进行读入。
inline int read(){
char x;
int num;
while(x=getchar(),x<'0'||x>'9');
num=x-'0';
while(x=getchar(),x>='0'&&x<='9') num*=10,num+=x-'0';
return num;
}
3.2 输入格式
第一行空格隔开的两个整数 n; k 。
接下来一行，空格隔开的 n 个整数，表示 ai。
3.3 输出格式
输出只有一个整数，表示答案。
3.4 样例输入
6 1
2 3 1 1 1 4
3.5 样例输出
12
3.6 样例解释
共四个 (γ) 区间。
a[1..2] = 2,3
a[3..5] = 1,1,1
a[3..4] = 1,1
a[4..5] = 1,1
3.7 数据规模及约定
对于前 30% 的数据， n ≤ 103 。
对于前 60% 的数据， n ≤ 105。
对于前 100% 的数据， 1 ≤ n ≤ 1000000, 0 ≤ ai; k ≤ 109。
先只考虑(gamma)区间的数量
我们发现如果区间([l,r])是合法的，那么([l,r'],l<r'<r)一定是个合法区间，如果([l,r])不合法，那么([l,r''],r''>r)一定不合法。对于每个(l),我们想找一个最靠后的(r)。
所以我们可以在枚举左端点的同时二分右端点
二分+(check):
注意如果区间([l,n])是合法的，那么二分出来的右端点会是(n-1)而不是(n),所以要先判一遍。
复杂度(O(nlogn))
我们想想能不能(O(n))找到(γ)区间。
我们枚举(l)每次(+1),那么新的(r)和原来的(r)肯定有联系。
设(l')为新的(l),(r')为新的(r),则([l',r])肯定是合法区间，那么(r')一定不会比(r)小，所以可以直接移动(r)，每次都判断一下是否合法。
这样移动(l,r)总体是(O(n))的
但是(check)还是(logn)的，所以怎样才能(O(1) check)?
由于(l,r)都是不断往后移，不会往前，所以可以用单调队列。开两个单调队列分别维护(Max)和(Min),(check)一次(O(1)),总复杂度(O(n))
求数字和：
第一个区间可以暴力求出来。
考虑转移。
(l->l+1,r)不变：减去(len imes a[l])，其中(len)是区间([l,r])的长度
(l)不变，(r->r+1):加上(sum[r+1]-sum[l-1]),也就是加上区间([l,r+1])的区间和
(Code) ((from std))
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
int n,k;
int a[1000005];
LL ans;
const LL mod=1e9+7;
struct dddl{
int q[1000005];
int h,t;
void push(int x){
while(h!=t && a[q[t-1]]>=a[x]) t--;
q[t++] = x;
}
void pop(int x){
if(q[h] == x) h++;
}
int ask(){
return a[q[h]];
}
}mn;
struct dddl2{
int q[1000005];
int h,t;
void push(int x){
while(h!=t && a[q[t-1]]<=a[x]) t--;
q[t++] = x;
}
void pop(int x){
if(q[h] == x) h++;
}
int ask(){
return a[q[h]];
}
}mx;
int main(){
freopen("nineteen.in", "r", stdin);
freopen("nineteen.out", "w", stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int first = 1;
LL sum=0;
LL sum_suf=0;
for(int i=1;i<=n;i++){
mn.push(i);
mx.push(i);
sum = (sum+a[i])%mod;
sum_suf = ((sum_suf)%mod+a[i]*(i-first+1)%mod)%mod;
while(mx.ask() - mn.ask()>k){
mx.pop(first);
mn.pop(first);
sum_suf = (sum_suf-sum+mod)%mod;
sum = (sum-a[first]%mod+mod)%mod;
first++;
}
ans += sum_suf;
// printf("# %d %d %lld %lld
",first, i, sum, sum_suf);
}
for(int i=1;i<=n;i++) ans = (ans-a[i]%mod+mod)%mod;
cout<<ans<<endl;
return 0;
}