CXJY-Day 3
FLAG: T2还不会做，记得填坑
锻炼（exercise）
【题目描述】
小A作为一个游戏高手，但是平日里却缺乏一些必要的锻炼，而为了锻炼的积极性，它号召了n个一起玩游戏的朋友陪他一起锻炼。
他们准备在一张n个点m条边的无向连通图中进行他们的锻炼，第i个人的目标是从第1个点跑到第i个点，因为他们并不是很想锻炼，所以他们会选择最短的道路跑到目的地。
但是第二天，他们惊奇地发现所有边竟然都增长了1米，在接下来的时间里，他们发现每一天每条边都增长了1米，所以他们想要知道，在计划的T天里，他们总共要跑的距离之和。
【输入数据】
三个整数n,m,T表示图中节点个数，边数，总共的天数。
接下来m行，每行三个整数Xi,Yi,Di表示Xi与Yi之间有一条长度为Di米的边。
【输出数据1】
一个整数ans，表示在T天里，所有人跑的距离之和，答案要对(1e9+7)取模。
【样例输入1】
2 1 597855229
1 2 1【样例输出2】
469240783【样例输入2】
5 6 0
1 2 1
2 3 2
1 5 1
1 3 2
1 4 4
3 4 1【样例输出】
7【数据范围】
对于30%的数据，$n≤50,T≤100$。
对于60%的数据，$n≤50$。
对于100%的数据，$n≤2500,m≤5000, 0≤T≤1e9,Di≤800000$。
【后记】
什么？你问我小A的锻炼效果？
作为游戏中的第一人，他当然也是要在这次锻炼里当做那个终点为1号节点的人啦。
训练效果肯定是很显著的啦。
题解
可以用$dis[i][j]$表示从1到达i点，经过j条边所需费用
直接分层dp即可
然后可以发现一开始是j较大处比较优，然后逐渐j减小，因此可以发现每个$dis[i][j]$对应直接坐标系中的一条直线$y=ax+b,a=j,b=dis[i][j]$
题目所求的就是对于$1<=i<=t$,所有直线的纵坐标最小值之和，可以发现每次选中的就是最底下的一圈，即一个凸包
凸包用单调栈维护即可，具体还是看代码把
注意很多地方要强转long long
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int Next,y,v;
}Pth[10005];
struct seg{
ll a,b;
}st[2505];
int head[2505],cnt;
void add(int x,int y,int v){
cnt++;
Pth[cnt]={head[x],y,v};
head[x]=cnt;
}
int n,m,t;
ll dis[2505][2505],dig[2505],INF=0x3f3f3f3f3f3f3f3fLL,ans,mod=1e9+7;
int top;
void dp(){
for (int i=1;i<=n;++i){
for (int j=0;j<n;++j){
dis[i][j]=INF;
}
}
dis[1][0]=0;
for (int i=0;i<n;++i){
for (int j=1;j<=n;++j){
for (int ii=head[j];ii;ii=Pth[ii].Next){
int y=Pth[ii].y;
dis[y][i+1]=min(dis[y][i+1],dis[j][i]+Pth[ii].v);
}
}
}
}
ll calc(int s1,ll a,ll b){
ll l1=st[s1].b-b;
ll l2=a-st[s1].a;
return (ll)ceil((double)l1/l2);
}
int main(){
freopen("exercise.in","r",stdin);
freopen("exercise.out","w",stdout);
cin>>n>>m>>t;
for (int i=1;i<=m;++i){
int x,y,d;
scanf("%d%d%d",&x,&y,&d);
add(x,y,d);add(y,x,d);
}
dp();
for (int i=2;i<=n;++i){
top=0;
for (int j=n-1;j>=0;--j){
if (dis[i][j]==INF) continue;
if (top==0){
st[++top]={j,dis[i][j]};
dig[top]=0;
}else{
while (top>=1 && calc(top,j,dis[i][j])<=dig[top]) top--;
st[++top]={j,dis[i][j]};
if (top>=2) dig[top]=calc(top-1,j,dis[i][j]);
else dig[top]=0;
}
}
int last=0;
dig[top+1]=INF;
for (int i=1;i<=top;++i){
ll l=dig[i],r=dig[i+1]-1;
if (l>t) break;
r=min(r,(ll)t);
ll tt=(ll)(l+r)*(r-l+1)/2; tt%=mod;
ans+=tt*st[i].a%mod+(ll)(r-l+1)*st[i].b%mod;
ans%=mod;
}
}
cout<<ans<<endl;
return 0;
}大佬的计算（calc）
【题目描述】
小A还在玩他的游戏，但是小B却在认真地学习，有一天，小A拿着一个问题去问小B：给定一个区间，求每一个区间的最大值之和。
小B马上回答了这个问题，并给了小A这个问题的加强版，但是小A最近的时间都荒废在游戏上面去了，导致他居然不会这个问题，所以他想要让你帮他来回答。
问题是：
给定一个长度为n的序列A，求对于$i<j,Max(A_i \dots A_j)*(A_i\&A_j=A_i|A_i\&A_j=A_j)$。
$Max(Ai,…,Aj)$的意思就是这些数的最大值。
&，|的含义和c++中符号的含义相同。
【输入数据】
一个整数n，表示序列的长度。
下一行n个整数，表示序列。
【输出数据】
一个整数表示答案。
【样例输入】
5
2 3 7 4 1【样例输出】
38【数据范围】
对于20%的数据，$n≤1000$。
对于另20%的数据，保证对于任意i,j均成立。
对于另20%的数据，$Ai<2^7$。
对于另10%的数据，$Ai=i\%2^{14}$。
对于100%的数据，$n≤100000，Ai<2^{14}$。
题解
20% 暴力+ST表
+20% 所有区间都对答案有贡献，即用单调栈求出每个点左右第一个比自己大的数，区间数乘上该点值即可。
+20% 找到总区间的最大值，把序列分成左右两部分，先递归较小的一段，分治求出该段中的答案，然后向另一边递归，求出以最大值为贡献的答案数，累加即可（dsu on the tree）
+10% 打表，求出$x=2^{14}$整数倍时的答案，求值时用前面的答案加上剩下暴力求解即可
100% 把$A_i$分成前7位和后7位，按上一种情况做即可
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
template <class T>void Max(T &x,T y){
if(x<y)x=y;
}
#define M 100005
int n,A[M];
struct STable{
int num[M][20],lg2[M];
void Init(){
memset(num,0,sizeof(num));
lg2[0]=-1;
for(int i=1;i<=n;i++)num[i][0]=i,lg2[i]=lg2[i>>1]+1;
for(int i=0;i+1<20;i++){
for(int j=1;j<=n;j++){
if(j+(1<<i)>n){num[j][i+1]=num[j][i];continue;}
int p1=num[j][i],p2=num[j+(1<<i)][i];
if(A[p1]>A[p2])num[j][i+1]=p1;
else num[j][i+1]=p2;
}
}
}
int Query(int l,int r){
int lg=lg2[r-l+1];
int p1=num[l][lg],p2=num[r-(1<<lg)+1][lg];
return A[p1]>A[p2]?p1:p2;
}
}ST;
vector<int>fa[1<<7],sn[1<<7];
void Add_edge(int f,int s){
sn[f].push_back(s);
fa[s].push_back(f);
}
void Init(){
// cout<<"Y"<<endl;
for(int i=0;i<(1<<7);i++){
Add_edge(i,0);
for(int j=i;j;j=(j-1)&i)
Add_edge(i,j);
}
}
int C[3][(1<<14)];
void Add(int a,int b,int v){
for(int i=0,up=fa[a].size();i<up;i++)C[0][(fa[a][i]<<7)|b]+=v;
for(int i=0,up=sn[a].size();i<up;i++)C[1][(sn[a][i]<<7)|b]+=v;
// cout<<a<<" "<<b<<" "<<v<<endl;
C[2][(a<<7)|b]+=v;
}
long long ans;
void Ask_fa(int a,int b,int v){
for(int i=0,up=fa[b].size();i<up;i++)
ans+=1ll*v*C[1][(a<<7)|fa[b][i]];
}
void Ask_sn(int a,int b,int v){
for(int i=0,up=sn[b].size();i<up;i++)
ans+=1ll*v*C[0][(a<<7)|sn[b][i]];
}
void DFS(int L,int R){
if(L>=R){
for(int i=L;i<=R;i++){
Add(A[i]>>7,A[i]&127,1);
int mx=A[i];
for(int j=i+1;j<=R;j++){
Max(mx,A[j]);
int x=A[i]&A[j];
if(x==A[i]||x==A[j])ans+=mx;
}
}
return;
}
int p=ST.Query(L,R),mid=(L+R)>>1;
if(p<=mid){
DFS(L,p-1);
for(int i=L;i<=p-1;i++)Add(A[i]>>7,A[i]&127,-1);
DFS(p+1,R);
for(int i=L;i<=p;i++)Ask_sn(A[i]>>7,A[i]&127,A[p]);
for(int i=L;i<=p-1;i++)ans-=1ll*A[p]*C[2][A[i]];
Add(A[p]>>7,A[p]&127,1);
for(int i=L;i<=p-1;i++)Ask_fa(A[i]>>7,A[i]&127,A[p]);
for(int i=L;i<=p-1;i++)Add(A[i]>>7,A[i]&127,1);
}else{
DFS(p+1,R);
for(int i=p+1;i<=R;i++)Add(A[i]>>7,A[i]&127,-1);
DFS(L,p-1);
for(int i=p;i<=R;i++)Ask_sn(A[i]>>7,A[i]&127,A[p]);
for(int i=p+1;i<=R;i++)ans-=1ll*A[p]*C[2][A[i]];
Add(A[p]>>7,A[p]&127,1);
for(int i=p+1;i<=R;i++)Ask_fa(A[i]>>7,A[i]&127,A[p]);
for(int i=p+1;i<=R;i++)Add(A[i]>>7,A[i]&127,1);
}
}
int main(){
freopen("calc.in","r",stdin);
freopen("calc.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
ST.Init();
Init();
DFS(1,n);
printf("%lld\n",ans);
return 0;
}自走棋（chess）
【题目描述】
小A最近沉迷自走棋，但是他玩的自走棋十分的奇怪，棋子在n*m的方形的棋盘上自己走，其中有k个空位，如果棋子走上去就死了，棋子的目标是从左上角走到右下角，走到的话就获胜了，如果两方棋子碰到一起则会触发战斗。
在一句对局中，小A有一个棋子疑似打假赛，在起点一直不动，而他的其他棋子与对方的棋子进行着激烈的战斗，最后，小A居然只剩下了这一个棋子，所以这枚棋子也开始动了，而对方的棋子也全部阵亡，只需要这个棋子走到右下角，小A就能得到胜利，但是对方的一个棋子对这个棋子释放了亡语：地缚神的诅咒，使得这个棋子只能往右或者往下走，因为这局基本已经稳赢了，所以小A想要知道他的棋子有多少种行走的方案能够使其获得最后的胜利。
【输入数据】
第一行三个整数n,m,k,表示棋盘大小，空位数量。
接下来k行每行两个整数x,y,表示一个空位的坐标。
【输出数据】
输出一个整数表示方案个数，对(1e9+7)取模。
【样例输入1】
3 4 2
2 2
2 3【样例输出1】
2【样例输入2】
100 100 3
15 16
16 15
99 88【样例输出2】
545732279【数据范围】
对于20%的数据，$1≤n,m,k≤8$。
对于40%的数据，$1≤n,m≤1000$。
对于另20%的数据，$1≤n≤2$。
对于100%的数据，$1≤n,m≤100000,1≤k≤1000$。
起点和终点一定不会是空位。
题解
40% 暴力DP计算即可
+20% 直接想一想或者DP
100% $dp[i]$表示没有经过空格，到达第i个空格的方案数，把$（1，1）$和$（n，n）$也看成空格
计算$dp[i]$时，从$dp[j]$转移来时，$dp[i]=C_{x_i+y_i-2}^{x_i-1}-dp[j]*C_{x_i-x_j+y_i-y_j}^{y_i-y_j}$（即到达i点的总方案数减掉经过一个空格的方案数），先对点按x,y排序
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int x,y;
}a[1005];
bool cmp(node x,node y){
if (x.x==y.x) return x.y<y.y;
return x.x<y.x;
}
ll dp[1005],mod=1e9+7,p[200005];
int n,m,k;
ll power(ll a,int b){
ll ret=1;
while (b){
if (b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
ll inv(ll t){return power(t,mod-2);}
ll C(int n,int m){
return p[n]*inv(p[m])%mod*inv(p[n-m])%mod;
}
int main(){
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
cin>>n>>m>>k;
p[0]=1;
for (int i=1;i<=n+m;++i) p[i]=p[i-1]*i%mod;
for (int i=1;i<=k;++i){
scanf("%d%d",&a[i].x,&a[i].y);
}
a[k+1]={n,m};
k+=1;
sort(a+1,a+k+1,cmp);
for (int i=1;i<=k;++i){
for (int j=1;j<i;++j){
if (a[i].x>=a[j].x && a[i].y>=a[j].y){
dp[i]+=dp[j]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].y-a[j].y);
dp[i]%=mod;
}
}
dp[i]=(C(a[i].x+a[i].y-2,a[i].x-1)-dp[i])%mod;
if (dp[i]<0) dp[i]+=mod;
}
cout<<dp[k]<<endl;
return 0;
}其他
因数和，因数个数
$a=b_1^{p_1}*b_2^{p_2}* \dots *b_n^{p_n}$
因数个数
$(p_1+1)*(p_2+1)* \dots *(p_n+1)$
因数和
$(1+b_1^1+b_1^2+ \dots +b_1^{p_1})* \dots *(1+b_n^1+b_n^2+ \dots +b_n^{p_n})$
$gcd(a,b)=gcd(b,a mod b)$
int gcd(int a,int b){
if (!b) return a;
return gcd(b,a%b);
}扩展欧几里得
$ax+by=c$有整数解的充要条件是$gcd(a,b)|c$
ll exgcd(ll a,ll b,ll &x,ll &y){
if (!b){x=1;y=0;return a;}
ll d=exgcd(b,a%b,x,y);
ll z=x;x=y;y=z-y*(a/b);
return d;
}类欧几里得算法
给定n,a,b,c,求$f(n,a,b,c)=\sum _{i=0}^n \lfloor \frac{ai+b}{c} \rfloor$
费马小定理
$$a^{p-1}=1 \mod p$$
欧拉定理
对于正整数n,令q(n)表示比n小的与n互质的数的个数，有 $$gcd(a,n)=1,a^{\varphi(n)} = 1(mod n)$$ 其中(n)称为欧拉函数。 
中国剩余定理
质数
线性基
其他
Lacus定理
矩阵乘法
高斯消元
线性基
Perm 排列计数
BZOJ4403 序列统计
BJWC2011 元素
BZOJ2844
luogu3292 SCOI2016 幸运数字
BZOJ2115 WC2011 Xor
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-3/
