第45届ICPC 昆明站 临时模板补充
【摘要】
昆明站模板补充
__int128
typedef __int128 LL;
inline __int128 read(){
__int128 x=0,f=1;
char ch=getchar();...
昆明站模板补充
__int128
typedef __int128 LL;
inline __int128 read(){
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void print(__int128 x){
if(x<0){putchar('-');x=-x;}
if(x>9)print(x/10);
putchar(x%10+'0');
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
快速读入
int readint(){
int x=0, op=1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch=='-')op=-1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x=x*10+ch-'0'; ch = getchar(); }
return x*op;
}
- 1
- 2
- 3
- 4
- 5
- 6
并查集
int fa[maxn+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int count(int n){int cnt=0; for(int i = 1; i <= n; i++)if(fa[i]==i)cnt++;return cnt;}
- 1
- 2
- 3
- 4
- 5
树状数组
//求逆序对
#include<iostream>
#include<algorithm>
#define maxn 50000
using namespace std;
struct node{int val, num;}a[maxn];
bool cmp(node a, node b){return a.val<b.val;}
int n, b[maxn];
void add(int x, int v){ for(int i = x; i <= n; i+=i&(-i))b[i]+=v;}
int query(int x){ int ans=0;for(int i=x;i>0;i-=i&(-i))ans+=b[i];return ans;}
/*
int n, m, a[maxn];
void add(int x, int k){
for(int i = x; i <= n; i += i&-i)
a[i] += k;
}
int query(int x){
int ans = 0;
for(int i = x; i >= 1; i -= i&-i)ans += a[i];
return ans;
}
*/
int main(){
cin>>n;
for(int i = 1; i <= n; i++)
cin>>a[i].val,a[i].num=i;
sort(a+1,a+n+1,cmp);
int ans = 0;
for(int i = n; i >= 1; i--){
add(a[i].num,1);
ans += query(a[i].num-1);
}
cout<<ans<<'\n';
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
线段树
//支持区间乘，区间加，区间取模
#include<iostream>
using namespace std;
struct SegmentTree{
typedef long long LL;
#define maxn 500010
#define lch p<<1
#define rch p<<1|1
struct node{
LL val, addmark, mulmark;
}sgt[maxn<<2];
int mod;
void build(int p, int l, int r){
sgt[p].addmark = 0, sgt[p].mulmark = 1;
if(l == r){
cin>>sgt[p].val;
return ;
}
int mid = l+r>>1;
build(lch,l,mid);
build(rch,mid+1,r);
sgt[p].val = (sgt[lch].val+sgt[rch].val)%mod;
return ;
}
void pushdown(int p, int l, int r){
if(sgt[p].addmark==0&&sgt[p].mulmark==1)return ;
//父节点标记
LL t1 = sgt[p].addmark, t2 = sgt[p].mulmark;
sgt[p].addmark = 0, sgt[p].mulmark = 1;
//维护标记
int mid = l+r>>1;
sgt[lch].mulmark *= t2, sgt[lch].mulmark %= mod;
sgt[rch].mulmark *= t2, sgt[rch].mulmark %= mod;
sgt[lch].addmark = (sgt[lch].addmark*t2+t1)%mod;
sgt[rch].addmark = (sgt[rch].addmark*t2+t1)%mod;
//更新值
sgt[lch].val = (sgt[lch].val*t2+t1*(mid-l+1))%mod;
sgt[rch].val = (sgt[rch].val*t2+t1*(r-mid))%mod;
return ;
}
void add(int p, int l, int r, int L, int R, LL v){
if(L<=l && r<=R){
sgt[p].val += (r-l+1)*v;
sgt[p].val %= mod;
sgt[p].addmark += v;
sgt[p].addmark %= mod;
return ;
}
pushdown(p,l,r);
int mid = l+r>>1;
if(L<=mid)add(lch,l,mid,L,R,v);//是L不是l
if(R>mid)add(rch, mid+1, r,L,R,v);
sgt[p].val = (sgt[lch].val+sgt[rch].val)%mod;
}
void times(int p, int l, int r, int L, int R, LL v){
if(L<=l && r<=R){
sgt[p].val *= v;
sgt[p].val %= mod;
sgt[p].mulmark *= v;
sgt[p].mulmark %= mod;
sgt[p].addmark *= v;
sgt[p].addmark %= mod;
return ;
}
pushdown(p,l,r);
int mid = (l+r)/2;
if(L<=mid)times(lch,l,mid,L,R,v);
if(R>mid)times(rch,mid+1,r,L,R,v);
sgt[p].val = (sgt[lch].val+sgt[rch].val)%mod;
}
LL query(int p, int l, int r, int L, int R){
if(L<=l && r<=R)return sgt[p].val;
pushdown(p,l,r);
LL mid = l+r>>1, ans = 0;
if(L<=mid)ans += query(lch,l,mid,L,R);
if(R>mid)ans += query(rch,mid+1,r,L,R);
return ans%mod;
}
}sgt;
int main(){
int n, m, q;
cin>>n>>q;
sgt.mod = q;
sgt.build(1,1,n);
cin>>m;
for(int i = 1; i <= m; i++){
int op, l, r, v;
cin>>op;
if(op==1){
cin>>l>>r>>v;
sgt.times(1,1,n,l,r,v);
}else if(op==2){
cin>>l>>r>>v;
sgt.add(1,1,n,l,r,v);
}else{
cin>>l>>r;
cout<<(sgt.query(1,1,n,l,r))<<'\n';
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
卢卡斯组合数
LL fac[maxn], inv[maxn];
LL mpow(LL a, LL x) {
if(x==0)return 1;
LL t = mpow(a, x>>1);
if(x%2==0)return t*t%mod;
return t*t%mod*a%mod;
}
LL init(){
fac[0]=inv[0]=1;
for(int i = 1; i < maxn; i++){
fac[i]=fac[i-1]*i%mod; inv[i]=mpow(fac[i],mod-2);
}return 0;
}
LL C(int x, int y) {
if(y<0 || y>x)return 0;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
数学杂项
//素数
int pri[N];
void get_prime(int n){ //诶氏筛法
pri[1] = 1;
for(int i = 2; i*i <= n; i++)if(!pri[i])
for(int j = 2*i; j <= n; j+=i)
pri[j] = 1;
}
//数论
LL gcd(LL a, LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a, LL b){ return a/gcd(a,b)*b; }
LL exgcd(LL a, LL b, LL &x, LL &y){
if(!b){
x = 1, y = 0;
return a;
}
LL r = exgcd(b, a%b, x, y);
LL t = x;
x = y;
y = t-a/b*y;
return r;
}
//快速幂，快速乘
LL mul(LL a, LL b, LL p){
LL x = 0;
while(b){
if(b&1)x=(x+a)%p;
a = (a<<1)%p;
b >>= 1;
}
return x;
}
LL mul(LL a, LL b){
LL x = 0;
while(b){
if(b&1)x += a;
a <<= 1;
b >>= 1;
}
return x;
}
LL pow(LL a, LL b, LL p){
LL x = 1;
while(b){
if(b&1)x = mul(x,a,p)%p;
a = mul(a,a,p)%p;
b >>= 1;
}
return x%p;
}
LL pow(LL a, LL b){
LL x = 1;
while(b){
if(b&1)x = mul(x,a);
a = mul(a,a);
b >>= 1;
}
return x;
}
//计算几何学
struct Point{ double x, y; }; //点
typedef Point Vector; //向量
struct Segment{ Point p1, p2; }; //线段
typedef Segment Line; //直线
class Circle{
public: Point c; double r;
Circle(Point c = Point(), double r = 0.0):c(c),r(r){}
};
//typedef vector<int> Polygon; //多边形
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
高斯消元
#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
const double eps=1e-7;
int n; double a[maxn][maxn], ans[maxn];
int Gauss(){
//1. 用第i个式子消去第i个系数，求得倒三角
for(int i = 1; i <= n; i++){
//找第i列中系数最大的式子并交换
int r = i;
for(int j=i+1; j<=n; j++){
if(abs(a[r][i])<abs(a[j][i]))r=j;
}
if(i!=r)swap(a[i],a[r]);
//如果下面的都是0，则存在多解.(n-i+1)为自由元个数
if(abs(a[i][i])<eps)return 0;
//用这个式子去消自己和其他的式子
double div = a[i][i];
for(int j = i; j <= n+1; j++)a[i][j] /= div;
for(int j = i+1; j <= n; j++){
div = a[j][i];
for(int k = i; k <= n+1; k++)
a[j][k] -= a[i][k]*div;
}
}
//2. 回代求答案值
ans[n] = a[n][n+1];
for(int i = n-1; i >= 1; i--){
ans[i] = a[i][n+1];
for(int j = i+1; j <= n; j++)
ans[i] -= a[i][j]*ans[j];
}
return 1;
}
int main(){
cin>>n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n+1; j++)
cin>>a[i][j];
int ok = Gauss();
if(ok==1){
for(int i = 1; i <= n; i++)
printf("%.2lf\n",ans[i]);
}else{
printf("No Solution\n");
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
离散化模板
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int a[maxn], b[maxn], c[maxn], sum[maxn];
int cnt, arr[maxn*3];
void discrete(){
sort(arr+1,arr+cnt+1);
cnt = unique(arr+1,arr+cnt+1)-arr-1;
}
int query(int x){
return lower_bound(arr+1,arr+cnt+1,x)-arr;
}
int main(){
//input
ios::sync_with_stdio(false);
int n; cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i]; arr[++cnt] = a[i];
}
int m; cin>>m;
for(int i = 1; i <= m; i++){
cin>>b[i]; arr[++cnt] = b[i];
}
for(int i = 1; i <= m; i++){
cin>>c[i]; arr[++cnt] = c[i];
}
//solve
discrete();
int ans = 0, bt = -1, ct = -1;
for(int i = 1; i <= n; i++)sum[query(a[i])]++;//会每种语言的人数
for(int i = 1; i <= m; i++){//更新能被看懂最多的电影
int x = query(b[i]), y = query(c[i]);
if(sum[x]>bt){
ans = i; bt = sum[x]; ct = sum[y];
}else if(sum[x]==bt && sum[y]>ct){
ans = i; bt = sum[x]; ct = sum[y];
}
}
cout<<ans<<endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
/*
给定一个n*m的网格，每条边上有一个权值。给定每个机器人的出发位置和目标位置。求权值最大。
+ 拆边，每条边拆成2条，第一条容量1，费用c[i]，第二条容量inf,费用0；
+ 建超级源汇（s到每个出发位置容量1，费用0，每个目标位置到t容量1，费用0），跑最大费用最大流即可
*/
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1100, M = 100010, inf = 1<<30;
//Grape
int tot=1, head[N], Next[M], ver[M], cap[M], cost[M];
void AddEdge(int x, int y, int z, int c){
//正向边，初始容量z，单位费用c
ver[++tot] = y, cap[tot] = z, cost[tot] = c;
Next[tot] = head[x], head[x] = tot;
//反向边，初始容量0，单位费用-c，与正向边成对存储
ver[++tot] = x, cap[tot] = 0, cost[tot] = -c;
Next[tot] = head[y], head[y] = tot;
}
//Cost flow
int s, t, incf[N], pre[N];
int dist[N], vis[N];
bool spfa(){
queue<int>q;
memset(dist,0xcf,sizeof(dist));//-inf
memset(vis,0,sizeof(vis));
q.push(s); dist[s]=0; vis[s]=1;
incf[s] = 1<<30; //到s为止的增广路上各边的最小的剩余容量
while(q.size()){
int x = q.front(); q.pop(); vis[x] = 0;
for(int i = head[x]; i; i = Next[i]){
if(!cap[i])continue; //剩余容量为0，不再残量网络中，不遍历
int y = ver[i];
if(dist[y]<dist[x]+cost[i]){//流量都为1，不用乘
dist[y] = dist[x]+cost[i];
incf[y] = min(incf[x], cap[i]);
pre[y] = i;//记录前驱，用于找方案
if(!vis[y])vis[y]=1, q.push(y);
}
}
}
if(dist[t] == 0xcfcfcfcf)return false;//汇点不可达，已求出最大流
return true;
}
int MaxCostMaxflow(){
int flow = 0, cost = 0;
while(spfa()){
int x = t;
while(x != s){
int i = pre[x];
cap[i] -= incf[t];
cap[i^1] += incf[t];//成对存储
x = ver[i^1];
}
flow += incf[t];
cost += dist[t]*incf[t];
}
return cost;
}
//Timu
int a, b, n, m, mp[N][N];
void input(){
cin>>a>>b;
cin>>n>>m;
s = 0, t = (n+1)*(m+1)+1;
int cnt = 0;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++)
mp[i][j] = ++cnt;
for(int i = 0; i <= n; i++){
for(int j = 0; j < m; j++){
int x; cin>>x;
AddEdge(mp[i][j],mp[i][j+1],1,x);
AddEdge(mp[i][j],mp[i][j+1],inf,0);
}
}
for(int j = 0; j <= m; j++){
for(int i = 0; i < n; i++){
int x; cin>>x;
AddEdge(mp[i][j],mp[i+1][j],1,x);
AddEdge(mp[i][j],mp[i+1][j],inf,0);
}
}
for(int i = 0; i < a; i++){
int x, y, z; cin>>z>>x>>y;
AddEdge(s,mp[x][y],z,0);
}
for(int i = 0; i < b; i++){
int x, y, z; cin>>z>>x>>y;
AddEdge(mp[x][y],t,z,0);
}
return ;
}
int main(){
ios::sync_with_stdio(false);
input();
cout<<MaxCostMaxflow()<<'\n';
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
最小费用最大流
/*
一个有n个数的环。每次只能向相邻的数移动，移动一个数代价为1。求让所有数相等的最小代价。
+ 从s向每个点连容量为库存量，费用为0的边
+ 从每个点向t连容量为平均库存量，费用为0的边
+ 在相邻两个点之间连容量为inf，费用为1的边
+ 然后跑最小费用最大流即可
*/
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N = 110*2+10, M = 1000+10, inf = 1<<30;
//Grape
struct Edge{
int from, to, cap, flow, cost;
}e[M];
int tot=1, head[N], Next[M];
void AddEdge(int u, int v, int w, int c){
//正向边，初始容量w，单位费用c
e[++tot].from = u, e[tot].to = v, e[tot].cap = w, e[tot].flow = 0, e[tot].cost = c;
Next[tot] = head[u], head[u] = tot;
//反向边，初始容量0，单位费用-c，与正向边成对存储
e[++tot].from = v, e[tot].to = u, e[tot].cap = 0, e[tot].flow = 0, e[tot].cost = -c;
Next[tot] = head[v], head[v] = tot;
}
//Cost flow
int s, t, incf[N], pre[N];
int dist[N], vis[N];
bool spfa(){
queue<int>q;
memset(dist,0x3f,sizeof(dist));//inf
memset(vis,0,sizeof(vis));
q.push(s); dist[s]=0; vis[s]=1;
incf[s] = inf; //到s为止的增广路上各边的最小的剩余容量
while(q.size()){
int x = q.front(); q.pop(); vis[x] = 0;
for(int i = head[x]; i; i = Next[i]){
if(e[i].flow==e[i].cap)continue; //剩余容量为0，不再残量网络中，不遍历
int y = e[i].to;
if(dist[y]>dist[x]+e[i].cost){
dist[y] = dist[x]+e[i].cost;
incf[y] = min(incf[x], e[i].cap-e[i].flow);
pre[y] = i;//记录前驱，用于找方案
if(!vis[y])vis[y]=1, q.push(y);
}
}
}
if(dist[t] == 0x3f3f3f3f)return false;//汇点不可达，已求出最大流
return true;
}
int maxflow(){
int flow = 0, cost = 0;
while(spfa()){
int x = t;
while(x != s){
int i = pre[x];
e[i].flow += incf[t];
e[i^1].flow -= incf[t];
x = e[i].from;
}
flow += incf[t];
cost += dist[t]*incf[t];
}
return cost;
}
//Timu
int n, a[110], sum, ans;
int main(){
ios::sync_with_stdio(false);
cin>>n; for(int i = 1; i <= n; i++)cin>>a[i],sum+=a[i]; sum/=n;
s = 0, t = n+1;
for(int i = 1; i <= n; i++){
AddEdge(s,i,a[i],0);
AddEdge(i,t,sum,0);
AddEdge(i,i+1>n?1:i+1,inf,1);
AddEdge(i,i-1<1?n:i-1,inf,1);
}
cout<<maxflow()<<'\n';
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
图论杂项
//图论算法模板
struct UndirectedEdge{ //图的边集存储
int u, v, w;
UndirectedEdge(){}
UndirectedEdge(int u, int v, int w): u(u),v(v),w(w){}
bool operator < (const UndirectedEdge & other)const{
return w < other.w;
}
};
//Kruskal
struct Kruskal{
int n, m;
UndirectedEdge edges[N];
inline int kruskal(){
int sum = 0, count = 0;
UnionFindSet ufs(n);
std::sort(edges, edges+m); //对所有边进行排序
for(int i = 1; i <= m; i++){
if(ufs.find(edges[i].u) != ufs.find(edges[i].v)){
ufs.merge(edges[i].u,edges[i].v);
sum += edges[i].w;
count++;
if(count == n-1) break;
}
}
return sum;
}
};
//有向图强连通分量
namespace Kosaraju{
int n, m;
vector<int>G[N], rG[N];
vector<int>vs, cmp[N];
int vis[N], book[N], cnt;
void dfs(int u){
if(vis[u])return ;
vis[u] = 1;
for(int i = 0; i < G[u].size(); i++)dfs(G[u][i]);
vs.push_back(u);
}
void rdfs(int u){
if(book[u])return ;
book[u] = cnt;
cmp[cnt].push_back(u);
for(int i = 0; i < rG[u].size(); i++)rdfs(rG[u][i]);
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
STL速查
priority_queue<int, vector<int>, greater<int> >q; //小根堆
priority_queue<int, vector<int>, less<int> >q; //大根堆
struct node{int x, y;};//比较函数
struct cmp{
bool operator()(node a, node b){
return a.x > b.x;
}
};
priority_queue<node, vector<node>, cmp>q;
//lower_bound：返回第一个大于等于x的位置
int p1=lower_bound(a,a+n,x)-a;
//upper_bound：返回第一个大于x的位置
int p2=upper_bound(a,a+n,x)-a;
//lower_bound2：返回数组中第一个小于或等于x的值
int p3=lower_bound(a,a+n,x,greater<int>())-a;
//upper_bound2：返回数组中第一个小于x的值
int p4=upper_bound(a,a+n,x,greater<int>())-a;
struct cmp_lower{
bool operator () (int a,int b){
return index[a]<b;
}
};
int lower_result=lower_bound(ar.begin(),ar.end(),x+1,cmp_lower())-ar.begin();
int count = unique(a, a+n)-a;
for(int i = 0; i < count; i++)printf("%d ", a[i]);
multiset
multimap
unordered_set/unordered_multiset
unordered_map/unordered_multimap
void setting(){
set<int>myset; //声明int类型的集合(突然发现重名好像不会炸233333)
//1. 基本操作
myset.insert(233); //往里面添加元素(重复插入无效)
myset.erase(233); //删除里面的某个元素(如果不存在该元素则不操作)(这里也可以用迭代器删除区间)
myset.count(233); //查询集合中是否存在某个元素
myset.clear(); //清空集合
//2. 迭代器
myset.insert(233); myset.insert(322);
set<int>::iterator it; //如果重名声明迭代器的时候会炸掉
set<int>::reverse_iterator rit; //反向迭代器
for(it = myset.begin(); it != myset.end(); it++){
cout<<*it<<" ";
}
cout<<"\n";
for(rit = myset.rbegin(); rit != myset.rend(); rit++){
cout<<*rit<<" ";
}
cout<<"\n";
//3. 熟练搞事
cout<< (myset.find(233)==myset.begin()) <<" \n"; //查找键值的位置并返回迭代器
cout<< *myset.lower_bound(234)<<"\n"; //返回第一个>=key的元素的迭代器
cout<< *myset.upper_bound(233)<<"\n"; //返回第一个>key的元素的迭代器
}
void maping(){
map<int,int>mymap; //左键右值
//1. 基本操作，，同为关联容器,基本和set差不多吧
mymap[5] = 7; //添加元素(注意 "mymap[0];" 同样往map中添加了元素，只是没有赋值而已)
//2. 迭代器
map<int,int>::iterator it = mymap.begin();
cout<<(it->first)<<" "<<(it->second)<<"\n"; //map遍历时访问的是pair类型
}
void stringing(){
string str = "123456789"; char ch[110]="233";
//构造函数
str = string(ch); //用c语言字符串s初始化
str = string(5,'c'); //用5个字符c初始化
string s1 = str; //赋值操作
//基本特性
str.size(); //返回大小
//各种操作
str.substr(0, 2); //返回子串,返回0开始的由两个字符组成的字符串
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
矩阵快速幂
/*
题意：给你一个233矩阵，横纵坐标都是从0开始，第一行为0 233 2333 23333…… 依次往下延续，第一列除(0,0)坐标点之外，让你自由输入n个数，整个矩阵满足关系式：
a(i,j)= a(i-1,j)+a(i,j-1) ( i,j ≠ 0 且 a(i,j)表示矩阵中坐标为(i,j)的点的值)
求坐标为(n,m)的数的值。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=10000007;
const int N=1e9+10;
ll n,M,arr[15],ans;
struct Matrix{
ll m[15][15];
Matrix(){
memset(m,0,sizeof(m));
for(int i=0;i<=n+1;i++){
m[i][n+1]=1;
if(i==n+1) continue;
m[i][0]=10;
for(int j=1;j<=i;j++)
m[i][j]=1;
}
}
void clear(){
memset(m,0,sizeof(m));
for(int i=0;i<=n+1;i++)
m[i][i]=1;
}
void display(){
cout<<"Matrix's begin:"<<endl;
for(int i=0;i<=n+1;i++)
for(int j=0;j<=n+1;j++)
if(j<n+1) cout<<m[i][j]<<" ";
else cout<<m[i][j]<<endl;
cout<<"Matrix's end:"<<endl;
}
friend Matrix operator*(Matrix a,Matrix b){
Matrix ans;
for(int i=0;i<=n+1;i++)
for(int j=0;j<=n+1;j++){
ans.m[i][j]=0;
for(int k=0;k<=n+1;k++)
ans.m[i][j]+=a.m[i][k]*b.m[k][j]%mod;
}
return ans;
}
friend Matrix operator^(Matrix base,ll k){
Matrix ans;
ans.clear();
while(k){
if(k&1) ans=ans*base;
base=base*base;
k>>=1;
}
return ans;
}
};
int main(){
// cout<<"hello"<<endl;
while(~scanf("%lld%lld",&n,&M)){
Matrix base;ans=0;
arr[0]=23;arr[n+1]=3;
for(int i=1;i<=n;i++){
scanf("%lld",&arr[i]);
}
base=base^M;
// base.display();
for(int i=0;i<=n+1;i++){
ans+=arr[i]*base.m[n][i];
// cout<<base.m[n][i]<<endl;
}
printf("%d\n",ans%mod);
}
return 0;
}
/*
3 1
1 2 3
23 10 0 0 0 1 233
a1 10 1 0 0 1 a1+23*10+3
a2 * 10 1 1 0 1 ^m = a2+a1+23*10+3 ^(m-1)
a3 10 1 1 1 1 a3+a2+a1+23*10+3
3 0 0 0 0 1 3
*/
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
ACM常用单词
abbreviation省略;缩写
adjacent sequence elements相邻的元素串
algebraic term代数项
alphabetical order字典序
alternately rise and fall交替上升和下降
approximate string matching 模糊匹配
arbitrary precision arithmetic 高精度计算
arithmetic mean 算数平均值
ascending order升序
aspect ratio固定长宽比
axis;axes轴
bandwidth reduction 带宽压缩
base 底边；幂的底数
calculate计算
calendrical calculations 日期
clique 最大团
clockwise order顺时针方向顺序
columns列
combinatorial problems 组合问题
comma逗号
composite numbers 合数
computational geometry 计算几何
concave 凹的
connected components 连通分支
constrained and unconstrained optimization 最值问题
convex hull 凸包
convex凸
coordinates坐标
cryptography 密码
cubes立方
data structures 基本数据结构
deformed变形的
denote表示；标志；预示；象征
determinants and permanents 行列式
diagonal对角
dial钟面，拨打
dictionaries 字典
difference 差
digit位数;数字
discrete fourier transform 离散傅里叶变换
distinct 不同的；独一无二的
divisor 因子，除数
divisor 因子;分母
drawing graphs nicely 图的描绘
drawing trees 树的描绘
edge and vertex connectivity 割边/割点
edge coloring 边染色
embed插入
equation方程式;等式
equivalent equation同解方程;等价方程
eulerian cycle欧拉循环
even偶数
executed 执行的；生效的
exponent 指数；幂
factorial 阶乘
factorial 阶乘; 因子的，阶乘的
factoring 因子分解
feedback edge/vertex set 最大无环子图
finite state machine minimization 有穷自动机简化
foggiest idea概念
follow by跟随，其后
fraction:分数;小部分
generating graphs 图的生成
generating partitions 划分生成
generating permutations 排列生成
generating subsets 子集生成
graph data structures 图
graph isomorphism 同构
graph partition 图的划分
graph problems-polynomial 图论-多项式算法
grid网格；方格；（地图上的）坐标方格
horizontal or vertical direction水平和垂直方向
improper fraction 假分数
in the range of 在....范围内
in the shape of a cross十字形
indentical相同的
independent set 独立集
inequality不等式
intersection detection 碰撞测试
intersection横断;横切;交叉
intersect相交
interval区间
kd-trees 线段树
knapsack problem 背包问题
like terms ,similar terms同类项
linear equation线性方程
linear programming 线性规划
literal coefficient字母系数
logarithm 对数
longest common substring 最长公共子串
loop环
maintaining line arrangements 平面分割
matching 匹配
matrix multiplication 矩阵乘法
matrix 矩阵
matrix矩阵
mean 平均值
medial-axis transformation 中轴变换
median and selection 中位数
minimal volume最小体积
minimum spanning tree 最小生成树
mixed number 带分数
motion planning 运动规划
motion多边形
nearest neighbor search 最近点对查询
negative负
network flow 网络流
numerator 分子
numerical coefficient 数字系数
numerical problems 数值问题
odd奇数
optimal最佳的
original equation原方程
origin原点
overbrim溢出
parity property奇偶性
planarity detection and embedding 平面性检测和嵌入
ploygon-shaped faces/ polygon多边形
point location 位置查询
polygon partitioning 多边形分割
positive正
present error呈现错误
prime 质数
priority queues 优先队列
proceed运行
process处理
proper fraction真分数
quadrant象限，四分之一圆
quotient 商
random number generation 随机数生成
range search 范围查询
range值域
rate of convergence 收敛速度
robustness 鲁棒性
root sign 根号
round()四舍五入（当取舍位为5时，若取舍位数前的小数为奇数则直接舍弃，若为偶数则向上取舍）
rounded to n decimal places 精确到小数点后n位
rows 行
scenario方案；(可能发生的)情况；
searching 查找
segment 段;分割
serial连续的
series系列
set and string problems 集合与串的问题
set cover 集合覆盖
set data structures 集合
set packing 集合配置
shape similarity 相似多边形
common superstring公共父串
shortest path 最短路径
simplifying polygons 多边形化简
solving linear equations 线性方程组
sorting 排序
specify 指定
stack overflow堆栈溢出
steiner tree steiner树
string matching 模式匹配
text compression 压缩
there are no special punctuation symbols or spacingrules没有特殊标点符号或间距的规则
times乘
topological sorting 拓扑排序
transitive closure and reduction 传递闭包
triangle inequality三角不等式
triangulation 三角剖分
two-dimensional array二维数组
union 并集
unique identifier唯一的标识符
variable变量
vertex coloring 点染色
vertex cover 点覆盖
vertex顶点
voronoi diagrams voronoi图
weighted average 加权平均值
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。
原文链接：gwj1314.blog.csdn.net/article/details/115441412
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）