树hash
1 | // tree 节点0不准使用 |
广义斐波那契循环节
广义斐波那契数递推公式 \[f_i=af_{i-1}+bf_{i-2}(\mod p) (p是奇素数)\]
他的转移矩阵 $$ ^n
p=
$$
如果存在循环节则存在n使得 \[ \left[ \begin{matrix} a & b \\ 1 & 0 \end{matrix} \right]^n= \left[ \begin{matrix} k_1p+1 & k_2p+0 \\ k_3p+0 & k_4p+1 \end{matrix} \right] \]
我们尝试把左边变成相似对角矩阵 先求特征值 \[ (\lambda-a)\lambda-b=0 \Leftrightarrow \lambda=\frac{a\pm\sqrt{a^2+4b}}{2} \]
当且仅当\(a^2+4b=0\)的时候，\(\lambda_1=\lambda_2\)，易证尽管此时\(\lambda\)是二重特征值，但是它对应的特征向量只有一个，即上诉矩阵不可对角化，我们不考虑这种复杂的情况。 当\(a^2+4b\neq0\)的时候，两个特征向量分别为 \[ \left[ \begin{matrix} \lambda_1 \\ 1 \end{matrix} \right] 和 \left[ \begin{matrix} \lambda_2 \\ 1 \end{matrix} \right] \] 那么就有了 \[ \left[ \begin{matrix} a & b \\ 1 & 0 \end{matrix} \right]= \left[ \begin{matrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{matrix} \right] \left[ \begin{matrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{matrix} \right] \left[ \begin{matrix} \frac{1}{\lambda_1-\lambda_2} & \frac{-\lambda_2}{\lambda_1-\lambda_2} \\ \frac{-1}{\lambda_1-\lambda_2} & \frac{\lambda_1}{\lambda_1-\lambda_2} \end{matrix} \right] \] 进而有了 \[ \left[ \begin{matrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{matrix} \right] \left[ \begin{matrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{matrix} \right] \left[ \begin{matrix} \frac{1}{\lambda_1-\lambda_2} & \frac{-\lambda_2}{\lambda_1-\lambda_2} \\ \frac{-1}{\lambda_1-\lambda_2} & \frac{\lambda_1}{\lambda_1-\lambda_2} \end{matrix} \right]= \left[ \begin{matrix} k_1p+1 & k_2p+0 \\ k_3p+0 & k_4p+1 \end{matrix} \right] \] 右乘\(T\)消掉那个一堆分数的矩阵 \[ \left[ \begin{matrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{matrix} \right] \left[ \begin{matrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{matrix} \right]= \left[ \begin{matrix} k_1p+1 & k_2p+0 \\ k_3p+0 & k_4p+1 \end{matrix} \right] \left[ \begin{matrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{matrix} \right] \] 乘开 \[ \left[ \begin{matrix} \lambda_1^{n+1} & \lambda_2^{n+1} \\ \lambda_1^{n} & \lambda_1^{n} \end{matrix} \right]= \left[ \begin{matrix} \lambda_1(k_1p+1)+k_2p & \lambda_2(k_1p+1)+k_2p \\ \lambda_1k_3p+k_4p+1 & \lambda_2k_3p+k_4p+1 \end{matrix} \right] \] ###在这之后我们分两部分讨论 ####\(a^2+4b是二次剩余\) 如果\(a^2+4b\)是二次剩余，那么\(\lambda_1\)和\(\lambda_2\)可以直接写成模意义下对应的整数,则上诉矩阵等式在\(n=p-1\)的时候根据费马小定理恒成立 ####\(a^2+4b不是二次剩余\) 在这里，是绝对不能够直接取模的，因为\(\lambda\)中一旦包含了根号下非二次剩余，这里就是错的，我们不可以取模，直接用根式表达即可。 #####两矩阵相等条件1: \[ \lambda^n=\lambda k_3p+k_4p+1 \] 先看\(\lambda_1\) \[ \lambda_1=\frac{a+\sqrt{a^2+4b}}{2}=\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b} \] 则 \[ (\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b})^n=(\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b})k_3p+k_4p+1 \] 分母有点难受，把它移到右边去 \[ (a+\sqrt{a^2+4b})^n=2^n* ((\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b})k_3p+k_4p+1)\\ \sum_{i=0}^nC_n^ia^i\sqrt{a^2+4b}^{n-i}=2^n* (\frac{a}{2}k_3p+k_4p+1)+2^n* (\frac{1}{2}k_3p)\sqrt{a^2+4b} \] 我们在这里引入一些概念，我们在实数领域解决这个问题，在实数领域，我们把数分为两部分来表示，一部分是有理数部分，称之为有理部，另一部分是无理数部分，称之为无理部，即\(1+2\sqrt{16}\)中，我们称1为有理部，2位无理部。 上式左边显然能够唯一表示为\(x+y\sqrt{a^2+4b}\),那么两式相等的充要条件就是 \[ 存在k_3,k_4使得x=2^n* (\frac{a}{2}k_3p+k_4p+1), y=2^n* \frac{1}{2}k_3p \] 上面的式子的某个充分条件为 \[ \frac{x}{2^n} \equiv1 \mod p\\ \frac{y}{2^n} \equiv0 \mod p \] 更加具体一点如果n是(p-1)的倍数则下面的式子也是充分条件 \[ x \equiv1 \mod p\\ y \equiv0 \mod p \] 为了利用这点，我们保证后面n一定是p-1的倍数，让我们先遗忘掉这些充分条件
然后我们来看看这个规律，注意到\(\sum_{i=0}^nC_n^ia^i\sqrt{a^2+4b}^{n-i}\)中，当\(n=p且i\neq0且i\neq n\)的时候，\(C_n^i|p\)，所以 \[ x\equiv a^p \equiv a\\ y\equiv \sqrt{a^2+4b}^p \] 即 \[ \begin{aligned} &(a+\sqrt{a^2+4b})^p \\=&（a+c_1p)+(\sqrt{a^2+4b}^{p-1}+c_2p)\sqrt{a^2+4b},c_1c_2是整数 \\=& (a+c_1p)+((a^2+4b)^{\frac{p-1}{2}}+c_2p)\sqrt{a^2+4b} \\=& a+(a^2+4b)^{\frac{p-1}{2}}\sqrt{a^2+4b}+c_1p+c_2p\sqrt{a^2+4b} \end{aligned} \] 这时候因为\(a^2+4b\)是一个非二次剩余,所以上式可以表达为 \[ a-\sqrt{a^2+4b}+c_1p+c_2p\sqrt{a^2+4b} \] 我们让他乘上\(\frac{a+\sqrt{a^2+4b}}{2}\),他的无理部就彻底与0同余了，此时的\(n=(p+1)\),在让这个数幂上\(p-1\)，他的有理部就与1同余了，并且我们达到了之前的约定，n是p-1的倍数，此时的\(n=(p+1)(p-1)\) #####两矩阵相等条件2: \[ \begin{aligned} &\lambda^{n+1}=\lambda(k_1p+1)+k_2p\\ \Leftrightarrow&\lambda^{n+1}=(\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b})(k_1p+1)+k_2p\\ \Leftrightarrow&\lambda^{n+1}=(\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b})+\frac{a}{2}k_1p+\frac{1}{2}\sqrt{a^2+4b}k_1pk_2p+k_2p \end{aligned} \] 之前我们证明了\(\lambda^{(p+1)(p-1)}\)的有理部与1同余，无理部与0同余，这里显然\(\lambda^{(p+1)(p-1)+1}\)的有理部与\(\frac{a}{2}\)同余，无理部与\(\frac{1}{2}\)同余, 至于\(\lambda_2\)是同理的。
至此证明了当\(a^2+4b\)是二次剩余的时候,循环节至多为\(n-1\),当\(a^2+4b\)不是二次剩余的时候，循环节至多为\(n^2-1\) 当\(a^2+4b=0\)的时候还有待挖掘
2019牛客多校9A
###name the power of Fibonacci
###description Amy asks Mr. B problem A. Please help Mr. B to solve the following problem. Let Fi be fibonacci number. \(F_0 = 0, F_1 = 1, F_i = F_{i-1} + F_{i-2}\) Given n and m, please calculate \(\sum^n_{i=0}{F_i^m}\)
As the answer might be very large, output it module 1000000000.
###input The first and only line contains two integers n, m(1 <= n <= 1000000000, 1 <= m <= 1000).
###output Output a single integer, the answer module 1000000000.
###sample input 1 5 5
###sample output 1 3402
###sample input 2 10 10
###sample output 2 696237975
###sample input 3 1000000000 1000
###sample output 3 641796875
###toturial 对\(10^9\)进行分解，\(10^9=2^9\*5^9\),然后打表，分别找到循环节的长度，最后用中国剩余定理合并
###code 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#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
const int len5=7812500,len2=768;
int fib5[len5+1],fib2[len2+1];
int qpow(int a,int b,int mod){
int res=1;
for(;b;b>>=1,a=1ll*a*a%mod) if(b&1)res=1ll*res*a%mod;
return res;
}
void Exeuclid(ll a, ll& x, ll b, ll& y, ll c){
if (!b) { x = c / a, y = 0; }
else {
Exeuclid(b, x, a % b, y, c);
x -= a / b * y;
swap(x, y);
}
}
int merge(int x1,int p1,int x2,int p2){
// u*p1+x1=v*p2+x2
// u*p1-v*p2=x2-x1
ll u,v;
Exeuclid(p1,u,p2,v,x2-x1);
ll p=p1*p2;
return ((u*p1+x1)%p+p)%p;
}
int main(){
// cout<<1ll*len5/__gcd(len5,len2)*len2<<endl;
fib2[1]=fib2[2]=fib5[1]=fib5[2]=1;
rep(i,3,len2) fib2[i]=(fib2[i-1]+fib2[i-2])%512;
rep(i,3,len5) fib5[i]=(fib5[i-1]+fib5[i-2])%1953125;
int n,m; scanf("%d%d",&n,&m);
rep(i,1,len2) fib2[i]=(qpow(fib2[i],m,512)+fib2[i-1])%512;
rep(i,1,len5) fib5[i]=(qpow(fib5[i],m,1953125)+fib5[i-1])%1953125;
int ans2=(1ll*fib2[len2]*(n/len2)+fib2[n%len2])%512;
int ans5=(1ll*fib5[len5]*(n/len5)+fib5[n%len5])%1953125;
printf("%d\n",merge(ans2,512,ans5,1953125));
}
中国剩余定理
1 | #define I __int128 |
1 | public class Main { |
虚树
虚树就是把树上一些节点拿下来重新建树，插入一些lca之类的点，deltree会删除一颗树，但不会删掉他的边,所以要注意边的情况
1 | // tree 节点0不准使用 |
二次剩余
1 | typedef long long ll; |
c++快读
1 | //究极读入挂 |
lct
1 | int top,c[N][2],f[N],tim[N],sta[N],rev[N],val[N]; |
2019牛客多校8E
###name explorer
###description Gromah and LZR have entered the fifth level. Unlike the first four levels, they should do some moves in this level.
There are nvertices and m bidirectional roads in this level, each road is in format (u,v,l,r) , which means that vertex u and v are connected by this road, but the sizes of passers should be in interval [l,r] . Since passers with small size are likely to be attacked by other animals and passers with large size may be blocked by some narrow roads.
Moreover, vertex 1 is the starting point and vertex n is the destination. Gromah and LZR should go from vertex 1 to vertex n to enter the next level.
At the beginning of their exploration, they may drink a magic potion to set their sizes to a fixed positive integer. They want to know the number of positive integer sizes that make it possible for them to go from 1 to n .
Please help them to find the number of valid sizes.
###input The first line contains two positive integers n,m , denoting the number of vertices and roads. Following m lines each contains four positive integers u,v,l,r , denoting a bidirectional road (u,v,l,r) . \(1≤n,m≤10^5 ,1≤u\lt v≤n,1≤l≤r≤10^9\)
###output Print a non-negative integer in a single line, denoting the number of valid sizes.
###sample input 5 5 1 2 1 4 2 3 1 2 3 5 2 4 2 4 1 3 4 5 3 4
###sample output 2
###hint There are 2 valid sizes : 2 and 3. For size 2, there exists a path 1→2→3→5. For size 3, there exists a path 1→2→4→5.
###toturial 把l,r看作限制，从小到大枚举区间，则表现为删边加边，然后问图的联通情况。这可以用直接lct维护。
###code 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#include<bits/stdc++.h>
using namespace std;
static const int N=4e5+555;
int X[N],Y[N],L[N],R[N],sa[2][N];
int n,m;
int top,c[N][2],f[N],tim[N],sta[N],rev[N],val[N];
void ini(){
for(int i=0;i<=n;i++)c[i][0]=c[i][1]=f[i]=rev[i]=0,tim[i]=i,val[i]=2e9;
for(int i=n+1;i<=n+m;i++)c[i][0]=c[i][1]=f[i]=rev[i]=0,tim[i]=i,val[i]=R[i-n];
}
inline void pushup(int x){
tim[x]=x;
if(val[tim[c[x][0]]]<val[tim[x]]) tim[x]=tim[c[x][0]];
if(val[tim[c[x][1]]]<val[tim[x]]) tim[x]=tim[c[x][1]];
}
inline void pushdown(int x){
int l=c[x][0],r=c[x][1];
if(rev[x]){
rev[l]^=1;rev[r]^=1;rev[x]^=1;
swap(c[x][0],c[x][1]);
}
}
inline bool isroot(int x){return c[f[x]][0]!=x&&c[f[x]][1]!=x;}
inline void rotate(int x){
int y=f[x],z=f[y],xis=c[y][1]==x,yis=c[z][1]==y;//
if(!isroot(y)) c[z][yis]=x;//son
f[x]=z;f[y]=x;f[c[x][xis^1]]=y;//father
c[y][xis]=c[x][xis^1];c[x][xis^1]=y;//son
pushup(y);
}
inline void splay(int x){
top=1;sta[top]=x;//init stack
for(int i=x;!isroot(i);i=f[i])sta[++top]=f[i];//update stack
for(int i=top;i;i--)pushdown(sta[i]);//pushroad
while(!isroot(x)){
int y=f[x],z=f[y];
if(!isroot(y)) (c[y][0]==x)^(c[z][0]==y)?rotate(y):rotate(x);
rotate(x);
}pushup(x);
}
inline void access(int x){for(int t=0;x;t=x,x=f[x])splay(x),c[x][1]=t,pushup(x);}
inline int treeroot(int x){access(x);splay(x);while(c[x][0])x=c[x][0];return x;}
inline void makeroot(int x){access(x);splay(x);rev[x]^=1;}// 让x变成根
inline void cut(int x,int y){makeroot(x);access(y);splay(y);f[x]=c[y][0]=0;pushup(y);}
inline void link(int x,int y){makeroot(x);f[x]=y;}
inline void cut2(int i){
makeroot(X[i]);
if(treeroot(Y[i])!=X[i]) return;
cut(X[i],n+i),cut(Y[i],n+i);
}
inline void link2(int i){
makeroot(X[i]);
if(treeroot(Y[i])==X[i]) {// access(y) splay(y)
int p=tim[Y[i]]-n;
if(R[p]>=R[i]) return;// 这个非常重要
cut(X[p],n+p),cut(Y[p],n+p);
}
link(X[i],n+i),link(Y[i],n+i);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d%d",X+i,Y+i,L+i,R+i),sa[0][i]=sa[1][i]=i;
ini();
sort(sa[0]+1,sa[0]+1+m,[](int a,int b){return L[a]<L[b];});
sort(sa[1]+1,sa[1]+1+m,[](int a,int b){return R[a]<R[b];});
vector<int>disc;
for(int i=1;i<=m;i++) disc.push_back(L[i]),disc.push_back(R[i]+1);// [)
sort(disc.begin(),disc.end());
disc.erase(unique(disc.begin(),disc.end()),disc.end());
int ans=0;
for(int t=0,i=1,j=1;t<disc.size();t++){// [T,T+1)
while(i<=m&&L[sa[0][i]]==disc[t]) link2(sa[0][i++]);
while(j<=m&&R[sa[1][j]]+1==disc[t]) cut2(sa[1][j++]);
makeroot(1);if(treeroot(n)==1) ans+=disc[t+1]-disc[t];
}
cout<<ans<<endl;
}
树链剖分
1 | const int maxn=1e5+5; |