树链剖分 #### 标题

题目描述
如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z
操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和

输入格式：
第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。
接下来一行包含N个非负整数，分别依次表示各个节点上初始的数值。
接下来N-1行每行包含两个整数x、y，表示点x和点y之间连有一条边（保证无环且连通）
接下来M行每行包含若干个正整数，每行表示一个操作，格式如下：
操作1： 1 x y z
操作2： 2 x y
操作3： 3 x z
操作4： 4 x

输出格式：
输出包含若干行，分别依次表示每个操作2或操作4所得的结果（对P取模）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
ll w[maxn],root;
ll N,M,R,P;
//线段树///////////////////////////////////////////////////////////////////
ll A[maxn<<2],Sum[maxn<<2],Add[maxn<<2];
void Pushup(ll rt)
{
    Sum[rt] = (Sum[rt<<1] + Sum[rt<<1|1]) % P;
}
void Pushdown(ll rt,ll ln,ll rn)
{
    if(Add[rt])
    {
        Add[rt<<1] = (Add[rt<<1] + Add[rt]) % P;
        Add[rt<<1|1] = (Add[rt<<1|1] + Add[rt]) % P;
        Sum[rt<<1] = (Sum[rt<<1] + ln * Add[rt]) % P;
        Sum[rt<<1|1] = (Sum[rt<<1|1] + rn * Add[rt]) % P;
        Add[rt] = 0;
    }
}
void build(ll l,ll r,ll rt)
{
    if(l == r)
    {
        Sum[rt] = A[l];
        return;
    }
    ll m = (l + r)>>1;
    build(l,m,rt<<1);
    build(m + 1,r,rt<<1|1);
    Pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt)
{
    if(L <= l && R >= r)
    {
        return Sum[rt];
    }
    ll m = (l + r)>>1;
    Pushdown(rt,m - l + 1,r - m);
    ll Ans = 0;
    if(L <= m)  Ans = (Ans + query(L,R,l,m,rt<<1)) % P;
    if(R > m)   Ans = (Ans + query(L,R,m + 1,r,rt<<1|1)) % P;
    return Ans;
}
void update(ll L,ll R,ll C,ll l,ll r,ll rt)
{
    if(L <= l && R >= r)
    {
        Sum[rt] = (Sum[rt] + (r - l + 1) * C) % P;
        Add[rt] = (Add[rt] + C) % P;
        return;
    }
    ll m = (l + r)>>1;
    Pushdown(rt,m - l + 1,r - m);
    if(L <= m)  update(L,R,C,l,m,rt<<1);
    if(R > m)   update(L,R,C,m + 1,r,rt<<1|1);
    Pushup(rt);
}
//////////////////////////////////////////////////////////
预处理///////////////////////////////////////////////////
ll head[maxn],f[maxn],dep[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],id[maxn];
ll tot,cnt;
struct Edge
{
    ll v,next;
}e[maxn * 2];
void addnode(ll u,ll v)
{
    e[tot].v = v;
    e[tot].next = head[u];
    head[u] = tot++;
}
void dfs1(ll u,ll fa,ll deep)
{
    f[u] = fa;
    dep[u] = deep;
    siz[u] = 1;
    for(ll i = head[u];i != -1;i = e[i].next)
    {
        ll v = e[i].v;
        if(v == fa)  continue;
        dfs1(v,u,deep + 1);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]])  son[u] = v;
    }
}
void dfs2(ll u,ll t)
{
    top[u] = t;
    id[u] = ++cnt;
    rk[cnt] = u;
    if(!son[u])  return;
    dfs2(son[u],t);
    for(ll i = head[u];i != -1;i = e[i].next)
    {
        ll v = e[i].v;
        if(v != son[u] && v != f[u])  dfs2(v,v);
    }
}
询问//////////////////////////////////////////
ll getsum(ll x,ll y)
{
    ll ans = 0,fx = top[x],fy = top[y];
    while(fx != fy)
    {
        if(dep[fx] >= dep[fy])
        {
            ans = (ans + query(id[fx],id[x],1,N,1)) % P;
            x = f[fx],fx = top[x];
        }
        else
        {
            ans = (ans + query(id[fy],id[y],1,N,1)) % P;
            y = f[fy],fy = top[y];
        }
    }
    if(id[x] <= id[y])  ans = (ans + query(id[x],id[y],1,N,1)) % P;
    else                ans = (ans + query(id[y],id[x],1,N,1)) % P;
    return ans;
}
void getupdate(ll x,ll y,ll C)
{
    ll fx = top[x],fy = top[y];
    while(fx != fy)
    {
        if(dep[fx] >= dep[fy])
        {
            update(id[fx],id[x],C,1,N,1);
            x = f[fx],fx = top[x];
        }
        else
        {
            update(id[fy],id[y],C,1,N,1);
            y = f[fy],fy = top[y];
        }
    }
    if(id[x] <= id[y])  update(id[x],id[y],C,1,N,1);
    else                update(id[y],id[x],C,1,N,1);
}
ll getsonsum(ll x)
{
    return query(id[x],id[x] + siz[x] - 1,1,N,1);
}
void getsonupdate(ll x,ll z)
{
    update(id[x],id[x] + siz[x] - 1,z,1,N,1);
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%lld %lld %lld %lld",&N,&M,&R,&P);
    for(ll i = 1;i <= N;i++)  scanf("%lld",&w[i]);
    for(ll i = 1;i < N;i++)
    {
        ll u,v;
        scanf("%lld %lld",&u,&v);
        addnode(u,v);
        addnode(v,u);
    }
    dfs1(R,0,1);
    dfs2(R,R);
    for(ll i = 1;i <= N;i++)
    {
        A[i] = w[rk[i]];
    }
    build(1,N,1);
    while(M--)
    {
        ll op,x,y,z;
        scanf("%lld",&op);
        if(op == 1)
        {
            scanf("%lld %lld %lld",&x,&y,&z);
            getupdate(x,y,z);
        }
        if(op == 2)
        {
            scanf("%lld %lld",&x,&y);
            printf("%lld\n",getsum(x,y));
        }
        if(op == 3)
        {
            scanf("%lld %lld",&x,&z);
            getsonupdate(x,z);
        }
        if(op == 4)
        {
            scanf("%lld",&x);
            printf("%lld\n",getsonsum(x));
        }
    }
    return 0;
}

主席树（区间第K大）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int T,n,m,np;
int L[maxn*20],R[maxn*20],Sum[maxn*20],A[maxn],B[maxn],Root[maxn];
int build(int l,int r)
{
    int rt = ++np;
    Sum[rt] = 0;
    if(l < r)
    {
        int mid = (l + r) / 2;
        L[rt] = build(l,mid);
        R[rt] = build(mid + 1,r);
    }
    return rt;
}
int update(int pre,int l,int r,int x)
{
    int rt = ++np;
    L[rt] = L[pre],R[rt] = R[pre],Sum[rt] = Sum[pre] + 1;
    int mid = (l + r) / 2;
    if(l < r)
    {
        if(x <= mid)  L[rt] = update(L[pre],l,mid,x);
        else          R[rt] = update(R[pre],mid + 1,r,x);
    }
    return rt;
}
int query(int u,int v,int l,int r,int k)
{
    if(l >= r)  return l;
    int mid = (l + r) / 2;
    int x = Sum[L[v]] - Sum[L[u]];
    if(x >= k)  return query(L[u],L[v],l,mid,k);
    else        return query(R[u],R[v],mid + 1,r,k - x);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        np = 0;
        scanf("%d %d",&n,&m);
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&A[i]);
            B[i] = A[i];
        }
        sort(B + 1,B + 1 + n);
        int len = unique(B + 1,B + 1 + n) - (B + 1);
        Root[0] = build(1,len);
        for(int i = 1;i <= n;i++)
        {
            int p = lower_bound(B + 1,B + 1 + len,A[i]) - B;
            Root[i] = update(Root[i - 1],1,len,p);
        }
        while(m--)
        {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            int p = query(Root[x - 1],Root[y],1,len,z);
            printf("%d\n",B[p]);
        }
    }
    return 0;
}

线性基

线性基的性质：
1、原序列里面的任意一个数都可以由线性基里面的一些数异或得到。
2、线性基里面的任意一些数异或起来都不能得到0。
3、线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的。

struct LineBase
{
    ll b[66];//上三角矩阵
    ll p[66];//对角矩阵
    int cnt;
    int max_b = 63;
    void init()
    {
        memset(b,0,sizeof(b));
        memset(p,0,sizeof(p));
        cnt = 0;
    }
    bool Insert(ll x)//插入
    {
        for(int i = max_b;i >= 0;i--)
        {
            if((x>>i)&1)
            {
                if(b[i] == 0)
                {
                    b[i] = x;
                    break;
                }
                x = x^b[i];
            }
        }
        if(x > 0)  cnt++;
        return (x > 0);
    }
    LineBase Merge(LineBase n1,LineBase n2)//线性基合并
    {
        LineBase ret = n1;
        for(int i = 0;i <= max_b;i++)
        {
            if(n2.b[i])  ret.Insert(n2.b[i]);
        }
        return ret;
    }
    LineBase Merge2(LineBase A,LineBase B)//线性基求交
    {
        LineBase All,C,D;
        All.init();
        C.init();
        D.init();
        for(ll i = 60;i >= 0;i--)
        {
            All.b[i] = A.b[i];
            D.b[i] = 1ll<<i;
        }
        for(ll i = 60;i >= 0;i--)
        {
            if(B.b[i])
            {
                ll v = B.b[i],k = 0;
                bool can = true;
                for(ll j = 60;j >= 0;j--)
                {
                    if(v & (1ll<<j))
                    {
                        if(All.b[j])
                        {
                            v^=All.b[j];
                            k^=D.b[j];
                        }
                        else
                        {
                            can = false;
                            All.b[j] = v;
                            D.b[j] = k;
                            break;
                        }
                    }
                }
                if(can)
                {
                    ll v = 0;
                    for(ll j = 60;j >= 0;j--)
                    {
                        if(k & (1ll<<j))
                        {
                            v^=A.b[j];
                        }
                    }
                    C.Insert(v);
                }
            }
        }
        return C;
    }
    ll queryMax(ll x)//求最大
    {
        ll ans = x;
        for(int i = max_b;i >= 0;i--)
        {
            if((ans^b[i]) > ans)  ans^=b[i];
        }
        return ans;
    }
    ll queryMin()//求最小
    {
        for(int i = 0;i < max_b;i++)
        {
            if(b[i])  return b[i];
        }
        return 0;
    }
    void rebuild()//化为对角矩阵
    {
        for(int i = max_b;i >= 0;i--)
        {
            for(int j = i - 1;j >= 0;j--)
            {
                if(b[i]&(1ll<<j))  b[i]^=b[j];
            }
        }
        cnt = 0;
        for(int i = 0;i <= max_b;i++)
        {
            if(b[i])  p[cnt++] = b[i];
        }
    }
    ll kthquery(ll k)//求第k大（必须先化为对角矩阵）
    {
        ll ans = 0;
        if(k >= (1ll<<cnt))  return -1;
        for(int i = max_b;i >= 0;i--)
        {
            if(k&(1ll<<i))  ans^=p[i];
        }
        return ans;
    }
};

杜教BM

输入前几项数据，快速求解线性递推式的第n项。

#include <bits/stdc++.h>
using namespace std;
namespace linear_seq
{
    #define rep(i,a,n) for(int i = a;i < n;i++)
    #define per(i,a,n) for(int i = n - 1;i >= a;i--)
    #define pb push_back
    #define mp make_pari
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef pair<int,int> PII;
    typedef long long ll;
    const ll mod = 1e9 + 7;
    const int N = 100010;
    ll res[N],base[N],_c[N],_md[N];
    ll modpow(ll a,ll b,ll mod) {ll res = 1;a %= mod;for(;b;b>>=1){if(b&1)res = res*a%mod;a=a*a%mod;}return res;}
    vector<int> Md;
    void mul(ll *a,ll *b,ll k)
    {
        rep(i,0,k+k) _c[i] = 0;
        rep(i,0,k) if(a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
        for(int i = k+k-1;i>=k;i--) if(_c[i])
            rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
        rep(i,0,k) a[i]=_c[i];
    }
    int solve(ll n,VI a,VI b)
    {
        ll ans=0,pnt=0;
        int k=SZ(a);
        rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
        Md.clear();
        rep(i,0,k) if(_md[i]!=0) Md.push_back(i);
        rep(i,0,k) res[i]=base[i]=0;
        res[0]=1;
        while((1ll<<pnt)<=n) pnt++;
        for(int p=pnt;p>=0;p--)
        {
            mul(res,res,k);
            if((n>>p)&1)
            {
                for(int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
                rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
            }
        }
        rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
        if(ans<0) ans+=mod;
        return ans;
    }
    VI BM(VI s)
    {
        VI C(1,1),B(1,1);
        int L=0,m=1,b=1;
        rep(n,0,SZ(s))
        {
            ll d=0;
            rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
            if(d==0) ++m;
            else if(2*L<=n)
            {
                VI T=C;
                ll c=mod-d*modpow(b,mod-2,mod)%mod;
                while(SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                L=n+1-L;B=T;b=d;m=1;
            }
            else
            {
                ll c=mod-d*modpow(b,mod-2,mod)%mod;
                while(SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                ++m;
            }
        }
        return C;
    }
    int gao(VI a,ll n)
    {
        VI c=BM(a);
        c.erase(c.begin());
        rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
        return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
    }
}
typedef long long ll;
const int MOD = 1e9 + 7;
ll n,k;
ll dp[2050];
ll powMod(ll a,ll b)
{
    ll res = 1;
    while(b)
    {
        if(b % 2 == 1)  res = res * a % MOD;
        a = a * a % MOD;
        b /= 2;
    }
    return res;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
       scanf("%lld %lld",&k,&n);
       if(n == -1)
       {
           ll ans = 2;
           ans = ans * powMod(k + 1,MOD - 2) % MOD;
           printf("%lld\n",ans);
           continue;
       }
       ll p = powMod(k,MOD - 2);
       //把递推式的前2 * k项计算出来并放入vetor中
       vector<int>v;
       v.push_back(1);
       dp[0] = 1;
       for(int i = 1;i <= 2 * k;i++)
       {
           dp[i] = 0;
           for(int j = i - 1;j >= max(0ll,i - k);j--)
           {
               dp[i] = (dp[i] + dp[j] * p % MOD) % MOD;
           }
           v.push_back(dp[i]);
       }
       //调用函数计算得到第n项的值
       ll ans = linear_seq::gao(v,n);
       printf("%lld\n",ans);
    }
    return 0;
}

解线性同余方程

ans * ans =(同余) n % p

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w;
ll p;
bool ok;
ll powMod(ll a,ll b)
{
    ll res = 1;
    while(b)
    {
        if(b&1)  res = res * a % p;
        a = a * a % p;
        b /= 2;
    }
    return res;
}
struct QuadraticField
{
    ll x,y;
    QuadraticField operator*(QuadraticField T)
    {
        QuadraticField ans;
        ans.x = (this->x * T.x % p + this->y * T.y % p * w % p) % p;
        ans.y = (this->x * T.y % p + this->y * T.x % p) % p;
        return ans;
    }
    QuadraticField operator^(ll b)
    {
        QuadraticField ans;
        QuadraticField a = *this;
        ans.x = 1;
        ans.y = 0;
        while(b)
        {
            if(b & 1)
            {
                ans = ans * a;
                b--;
            }
            b /= 2;
            a = a * a;
        }
        return ans;
    }
};
ll Lengender(ll a)
{
    ll ans = powMod(a,(p - 1) / 2);
    if(ans + 1 == p)  return -1;
    else  return ans;
}
ll GetW(ll n,ll a)
{
    return ((a * a - n) % p + p) % p;
}
ll Solve(ll n)
{
    ll a;
    if(p == 2)  return n;
    if(Lengender(n) == -1)  ok = false;
    srand((unsigned)time(NULL));
    while(1)
    {
        a = rand() % p;
        w = GetW(n,a);
        if(Lengender(w) == -1)  break;
    }
    QuadraticField ans,res;
    res.x = a;
    res.y = 1;
    ans = res ^ ((p + 1) / 2);
    return ans.x;
}
int main()
{
    ll n,ans1,ans2;
    while(scanf("%lld %lld",&n,&p) != EOF)
    {
        ok = true;
        n %= p;
        ans1 = Solve(n);
        ans2 = p - ans1;
        if(!ok)  printf("-1\n");
        else  printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}