[关闭]
@Pinetrie 2019-10-20T07:53:22.000000Z 字数 8939 阅读 840

树链剖分 #### 标题

题目描述
如题，已知一棵包含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取模）

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef long long ll;
  6. const int maxn = 100010;
  7. ll w[maxn],root;
  8. ll N,M,R,P;
  10. //线段树///////////////////////////////////////////////////////////////////
  11. ll A[maxn<<2],Sum[maxn<<2],Add[maxn<<2];
  13. void Pushup(ll rt)
  14. {
  15.     Sum[rt] = (Sum[rt<<1] + Sum[rt<<1|1]) % P;
  16. }
  18. void Pushdown(ll rt,ll ln,ll rn)
  19. {
  20.     if(Add[rt])
  21.     {
  22.         Add[rt<<1] = (Add[rt<<1] + Add[rt]) % P;
  23.         Add[rt<<1|1] = (Add[rt<<1|1] + Add[rt]) % P;
  24.         Sum[rt<<1] = (Sum[rt<<1] + ln * Add[rt]) % P;
  25.         Sum[rt<<1|1] = (Sum[rt<<1|1] + rn * Add[rt]) % P;
  26.         Add[rt] = 0;
  27.     }
  28. }
  30. void build(ll l,ll r,ll rt)
  31. {
  32.     if(l == r)
  33.     {
  34.         Sum[rt] = A[l];
  35.         return;
  36.     }
  37.     ll m = (l + r)>>1;
  38.     build(l,m,rt<<1);
  39.     build(m + 1,r,rt<<1|1);
  40.     Pushup(rt);
  41. }
  43. ll query(ll L,ll R,ll l,ll r,ll rt)
  44. {
  45.     if(L <= l && R >= r)
  46.     {
  47.         return Sum[rt];
  48.     }
  49.     ll m = (l + r)>>1;
  50.     Pushdown(rt,m - l + 1,r - m);
  51.     ll Ans = 0;
  52.     if(L <= m)  Ans = (Ans + query(L,R,l,m,rt<<1)) % P;
  53.     if(R > m)   Ans = (Ans + query(L,R,m + 1,r,rt<<1|1)) % P;
  54.     return Ans;
  55. }
  57. void update(ll L,ll R,ll C,ll l,ll r,ll rt)
  58. {
  59.     if(L <= l && R >= r)
  60.     {
  61.         Sum[rt] = (Sum[rt] + (r - l + 1) * C) % P;
  62.         Add[rt] = (Add[rt] + C) % P;
  63.         return;
  64.     }
  65.     ll m = (l + r)>>1;
  66.     Pushdown(rt,m - l + 1,r - m);
  67.     if(L <= m)  update(L,R,C,l,m,rt<<1);
  68.     if(R > m)   update(L,R,C,m + 1,r,rt<<1|1);
  69.     Pushup(rt);
  70. }
  72. //////////////////////////////////////////////////////////
  74. 预处理///////////////////////////////////////////////////
  75. ll head[maxn],f[maxn],dep[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],id[maxn];
  76. ll tot,cnt;
  78. struct Edge
  79. {
  80.     ll v,next;
  81. }e[maxn * 2];
  83. void addnode(ll u,ll v)
  84. {
  85.     e[tot].v = v;
  86.     e[tot].next = head[u];
  87.     head[u] = tot++;
  88. }
  90. void dfs1(ll u,ll fa,ll deep)
  91. {
  92.     f[u] = fa;
  93.     dep[u] = deep;
  94.     siz[u] = 1;
  95.     for(ll i = head[u];i != -1;i = e[i].next)
  96.     {
  97.         ll v = e[i].v;
  98.         if(v == fa)  continue;
  99.         dfs1(v,u,deep + 1);
  100.         siz[u] += siz[v];
  101.         if(siz[v] > siz[son[u]])  son[u] = v;
  102.     }
  103. }
  105. void dfs2(ll u,ll t)
  106. {
  107.     top[u] = t;
  108.     id[u] = ++cnt;
  109.     rk[cnt] = u;
  110.     if(!son[u])  return;
  111.     dfs2(son[u],t);
  113.     for(ll i = head[u];i != -1;i = e[i].next)
  114.     {
  115.         ll v = e[i].v;
  116.         if(v != son[u] && v != f[u])  dfs2(v,v);
  117.     }
  118. }
  121. 询问//////////////////////////////////////////
  123. ll getsum(ll x,ll y)
  124. {
  125.     ll ans = 0,fx = top[x],fy = top[y];
  126.     while(fx != fy)
  127.     {
  128.         if(dep[fx] >= dep[fy])
  129.         {
  130.             ans = (ans + query(id[fx],id[x],1,N,1)) % P;
  131.             x = f[fx],fx = top[x];
  132.         }
  133.         else
  134.         {
  135.             ans = (ans + query(id[fy],id[y],1,N,1)) % P;
  136.             y = f[fy],fy = top[y];
  137.         }
  138.     }
  139.     if(id[x] <= id[y])  ans = (ans + query(id[x],id[y],1,N,1)) % P;
  140.     else                ans = (ans + query(id[y],id[x],1,N,1)) % P;
  142.     return ans;
  143. }
  145. void getupdate(ll x,ll y,ll C)
  146. {
  147.     ll fx = top[x],fy = top[y];
  148.     while(fx != fy)
  149.     {
  150.         if(dep[fx] >= dep[fy])
  151.         {
  152.             update(id[fx],id[x],C,1,N,1);
  153.             x = f[fx],fx = top[x];
  154.         }
  155.         else
  156.         {
  157.             update(id[fy],id[y],C,1,N,1);
  158.             y = f[fy],fy = top[y];
  159.         }
  160.     }
  161.     if(id[x] <= id[y])  update(id[x],id[y],C,1,N,1);
  162.     else                update(id[y],id[x],C,1,N,1);
  163. }
  165. ll getsonsum(ll x)
  166. {
  167.     return query(id[x],id[x] + siz[x] - 1,1,N,1);
  168. }
  170. void getsonupdate(ll x,ll z)
  171. {
  172.     update(id[x],id[x] + siz[x] - 1,z,1,N,1);
  173. }
  175. int main()
  176. {
  177.     memset(head,-1,sizeof(head));
  178.     scanf("%lld %lld %lld %lld",&N,&M,&R,&P);
  179.     for(ll i = 1;i <= N;i++)  scanf("%lld",&w[i]);
  180.     for(ll i = 1;i < N;i++)
  181.     {
  182.         ll u,v;
  183.         scanf("%lld %lld",&u,&v);
  184.         addnode(u,v);
  185.         addnode(v,u);
  186.     }
  187.     dfs1(R,0,1);
  188.     dfs2(R,R);
  189.     for(ll i = 1;i <= N;i++)
  190.     {
  191.         A[i] = w[rk[i]];
  192.     }
  193.     build(1,N,1);
  195.     while(M--)
  196.     {
  197.         ll op,x,y,z;
  198.         scanf("%lld",&op);
  199.         if(op == 1)
  200.         {
  201.             scanf("%lld %lld %lld",&x,&y,&z);
  202.             getupdate(x,y,z);
  203.         }
  204.         if(op == 2)
  205.         {
  206.             scanf("%lld %lld",&x,&y);
  207.             printf("%lld\n",getsum(x,y));
  208.         }
  209.         if(op == 3)
  210.         {
  211.             scanf("%lld %lld",&x,&z);
  212.             getsonupdate(x,z);
  213.         }
  214.         if(op == 4)
  215.         {
  216.             scanf("%lld",&x);
  217.             printf("%lld\n",getsonsum(x));
  218.         }
  219.     }
  220.     return 0;
  221. }

主席树（区间第K大）

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int maxn = 100010;
  5. int T,n,m,np;
  6. int L[maxn*20],R[maxn*20],Sum[maxn*20],A[maxn],B[maxn],Root[maxn];
  8. int build(int l,int r)
  9. {
  10.     int rt = ++np;
  11.     Sum[rt] = 0;
  12.     if(l < r)
  13.     {
  14.         int mid = (l + r) / 2;
  15.         L[rt] = build(l,mid);
  16.         R[rt] = build(mid + 1,r);
  17.     }
  18.     return rt;
  19. }
  21. int update(int pre,int l,int r,int x)
  22. {
  23.     int rt = ++np;
  24.     L[rt] = L[pre],R[rt] = R[pre],Sum[rt] = Sum[pre] + 1;
  25.     int mid = (l + r) / 2;
  26.     if(l < r)
  27.     {
  28.         if(x <= mid)  L[rt] = update(L[pre],l,mid,x);
  29.         else          R[rt] = update(R[pre],mid + 1,r,x);
  30.     }
  31.     return rt;
  32. }
  34. int query(int u,int v,int l,int r,int k)
  35. {
  36.     if(l >= r)  return l;
  37.     int mid = (l + r) / 2;
  38.     int x = Sum[L[v]] - Sum[L[u]];
  39.     if(x >= k)  return query(L[u],L[v],l,mid,k);
  40.     else        return query(R[u],R[v],mid + 1,r,k - x);
  41. }
  43. int main()
  44. {
  45.     int T;
  46.     scanf("%d",&T);
  47.     while(T--)
  48.     {
  49.         np = 0;
  50.         scanf("%d %d",&n,&m);
  51.         for(int i = 1;i <= n;i++)
  52.         {
  53.             scanf("%d",&A[i]);
  54.             B[i] = A[i];
  55.         }
  56.         sort(B + 1,B + 1 + n);
  57.         int len = unique(B + 1,B + 1 + n) - (B + 1);
  58.         Root[0] = build(1,len);
  59.         for(int i = 1;i <= n;i++)
  60.         {
  61.             int p = lower_bound(B + 1,B + 1 + len,A[i]) - B;
  62.             Root[i] = update(Root[i - 1],1,len,p);
  63.         }
  64.         while(m--)
  65.         {
  66.             int x,y,z;
  67.             scanf("%d %d %d",&x,&y,&z);
  68.             int p = query(Root[x - 1],Root[y],1,len,z);
  69.             printf("%d\n",B[p]);
  70.         }
  71.     }
  72.     return 0;
  73. }

线性基

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

  1. struct LineBase
  2. {
  3.     ll b[66];//上三角矩阵
  4.     ll p[66];//对角矩阵
  5.     int cnt;
  6.     int max_b = 63;
  7.     void init()
  8.     {
  9.         memset(b,0,sizeof(b));
  10.         memset(p,0,sizeof(p));
  11.         cnt = 0;
  12.     }
  13.     bool Insert(ll x)//插入
  14.     {
  15.         for(int i = max_b;i >= 0;i--)
  16.         {
  17.             if((x>>i)&1)
  18.             {
  19.                 if(b[i] == 0)
  20.                 {
  21.                     b[i] = x;
  22.                     break;
  23.                 }
  24.                 x = x^b[i];
  25.             }
  26.         }
  27.         if(x > 0)  cnt++;
  28.         return (x > 0);
  29.     }
  30.     LineBase Merge(LineBase n1,LineBase n2)//线性基合并
  31.     {
  32.         LineBase ret = n1;
  33.         for(int i = 0;i <= max_b;i++)
  34.         {
  35.             if(n2.b[i])  ret.Insert(n2.b[i]);
  36.         }
  37.         return ret;
  38.     }
  39.     LineBase Merge2(LineBase A,LineBase B)//线性基求交
  40.     {
  41.         LineBase All,C,D;
  42.         All.init();
  43.         C.init();
  44.         D.init();
  45.         for(ll i = 60;i >= 0;i--)
  46.         {
  47.             All.b[i] = A.b[i];
  48.             D.b[i] = 1ll<<i;
  49.         }
  50.         for(ll i = 60;i >= 0;i--)
  51.         {
  52.             if(B.b[i])
  53.             {
  54.                 ll v = B.b[i],k = 0;
  55.                 bool can = true;
  56.                 for(ll j = 60;j >= 0;j--)
  57.                 {
  58.                     if(v & (1ll<<j))
  59.                     {
  60.                         if(All.b[j])
  61.                         {
  62.                             v^=All.b[j];
  63.                             k^=D.b[j];
  64.                         }
  65.                         else
  66.                         {
  67.                             can = false;
  68.                             All.b[j] = v;
  69.                             D.b[j] = k;
  70.                             break;
  71.                         }
  72.                     }
  73.                 }
  74.                 if(can)
  75.                 {
  76.                     ll v = 0;
  77.                     for(ll j = 60;j >= 0;j--)
  78.                     {
  79.                         if(k & (1ll<<j))
  80.                         {
  81.                             v^=A.b[j];
  82.                         }
  83.                     }
  84.                     C.Insert(v);
  85.                 }
  86.             }
  87.         }
  88.         return C;
  89.     }
  90.     ll queryMax(ll x)//求最大
  91.     {
  92.         ll ans = x;
  93.         for(int i = max_b;i >= 0;i--)
  94.         {
  95.             if((ans^b[i]) > ans)  ans^=b[i];
  96.         }
  97.         return ans;
  98.     }
  99.     ll queryMin()//求最小
  100.     {
  101.         for(int i = 0;i < max_b;i++)
  102.         {
  103.             if(b[i])  return b[i];
  104.         }
  105.         return 0;
  106.     }
  107.     void rebuild()//化为对角矩阵
  108.     {
  109.         for(int i = max_b;i >= 0;i--)
  110.         {
  111.             for(int j = i - 1;j >= 0;j--)
  112.             {
  113.                 if(b[i]&(1ll<<j))  b[i]^=b[j];
  114.             }
  115.         }
  116.         cnt = 0;
  117.         for(int i = 0;i <= max_b;i++)
  118.         {
  119.             if(b[i])  p[cnt++] = b[i];
  120.         }
  121.     }
  122.     ll kthquery(ll k)//求第k大（必须先化为对角矩阵）
  123.     {
  124.         ll ans = 0;
  125.         if(k >= (1ll<<cnt))  return -1;
  126.         for(int i = max_b;i >= 0;i--)
  127.         {
  128.             if(k&(1ll<<i))  ans^=p[i];
  129.         }
  130.         return ans;
  131.     }
  132. };

杜教BM

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

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. namespace linear_seq
  6. {
  7.     #define rep(i,a,n) for(int i = a;i < n;i++)
  8.     #define per(i,a,n) for(int i = n - 1;i >= a;i--)
  9.     #define pb push_back
  10.     #define mp make_pari
  11.     #define all(x) (x).begin(),(x).end()
  12.     #define fi first
  13.     #define se second
  14.     #define SZ(x) ((int)(x).size())
  15.     typedef vector<int> VI;
  16.     typedef pair<int,int> PII;
  17.     typedef long long ll;
  18.     const ll mod = 1e9 + 7;
  19.     const int N = 100010;
  20.     ll res[N],base[N],_c[N],_md[N];
  21.     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;}
  22.     vector<int> Md;
  23.     void mul(ll *a,ll *b,ll k)
  24.     {
  25.         rep(i,0,k+k) _c[i] = 0;
  26.         rep(i,0,k) if(a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
  27.         for(int i = k+k-1;i>=k;i--) if(_c[i])
  28.             rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
  29.         rep(i,0,k) a[i]=_c[i];
  30.     }
  31.     int solve(ll n,VI a,VI b)
  32.     {
  33.         ll ans=0,pnt=0;
  34.         int k=SZ(a);
  35.         rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
  36.         Md.clear();
  37.         rep(i,0,k) if(_md[i]!=0) Md.push_back(i);
  38.         rep(i,0,k) res[i]=base[i]=0;
  39.         res[0]=1;
  40.         while((1ll<<pnt)<=n) pnt++;
  41.         for(int p=pnt;p>=0;p--)
  42.         {
  43.             mul(res,res,k);
  44.             if((n>>p)&1)
  45.             {
  46.                 for(int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
  47.                 rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
  48.             }
  49.         }
  50.         rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
  51.         if(ans<0) ans+=mod;
  52.         return ans;
  53.     }
  54.     VI BM(VI s)
  55.     {
  56.         VI C(1,1),B(1,1);
  57.         int L=0,m=1,b=1;
  58.         rep(n,0,SZ(s))
  59.         {
  60.             ll d=0;
  61.             rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
  62.             if(d==0) ++m;
  63.             else if(2*L<=n)
  64.             {
  65.                 VI T=C;
  66.                 ll c=mod-d*modpow(b,mod-2,mod)%mod;
  67.                 while(SZ(C)<SZ(B)+m) C.pb(0);
  68.                 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
  69.                 L=n+1-L;B=T;b=d;m=1;
  70.             }
  71.             else
  72.             {
  73.                 ll c=mod-d*modpow(b,mod-2,mod)%mod;
  74.                 while(SZ(C)<SZ(B)+m) C.pb(0);
  75.                 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
  76.                 ++m;
  77.             }
  78.         }
  79.         return C;
  80.     }
  81.     int gao(VI a,ll n)
  82.     {
  83.         VI c=BM(a);
  84.         c.erase(c.begin());
  85.         rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
  86.         return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
  87.     }
  89. }
  92. typedef long long ll;
  93. const int MOD = 1e9 + 7;
  94. ll n,k;
  95. ll dp[2050];
  97. ll powMod(ll a,ll b)
  98. {
  99.     ll res = 1;
  100.     while(b)
  101.     {
  102.         if(b % 2 == 1)  res = res * a % MOD;
  103.         a = a * a % MOD;
  104.         b /= 2;
  105.     }
  106.     return res;
  107. }
  110. int main()
  111. {
  112.     int T;
  113.     scanf("%d",&T);
  114.     while(T--)
  115.     {
  116.        scanf("%lld %lld",&k,&n);
  117.        if(n == -1)
  118.        {
  119.            ll ans = 2;
  120.            ans = ans * powMod(k + 1,MOD - 2) % MOD;
  121.            printf("%lld\n",ans);
  122.            continue;
  123.        }
  124.        ll p = powMod(k,MOD - 2);
  125.        //把递推式的前2 * k项计算出来并放入vetor中
  126.        vector<int>v;
  127.        v.push_back(1);
  128.        dp[0] = 1;
  129.        for(int i = 1;i <= 2 * k;i++)
  130.        {
  131.            dp[i] = 0;
  132.            for(int j = i - 1;j >= max(0ll,i - k);j--)
  133.            {
  134.                dp[i] = (dp[i] + dp[j] * p % MOD) % MOD;
  135.            }
  136.            v.push_back(dp[i]);
  137.        }
  138.        //调用函数计算得到第n项的值
  139.        ll ans = linear_seq::gao(v,n);
  140.        printf("%lld\n",ans);
  141.     }
  142.     return 0;
  143. }

解线性同余方程

ans * ans =(同余) n % p

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef long long ll;
  5. ll w;
  6. ll p;
  7. bool ok;
  9. ll powMod(ll a,ll b)
  10. {
  11.     ll res = 1;
  12.     while(b)
  13.     {
  14.         if(b&1)  res = res * a % p;
  15.         a = a * a % p;
  16.         b /= 2;
  17.     }
  18.     return res;
  19. }
  21. struct QuadraticField
  22. {
  23.     ll x,y;
  24.     QuadraticField operator*(QuadraticField T)
  25.     {
  26.         QuadraticField ans;
  27.         ans.x = (this->x * T.x % p + this->y * T.y % p * w % p) % p;
  28.         ans.y = (this->x * T.y % p + this->y * T.x % p) % p;
  29.         return ans;
  30.     }
  31.     QuadraticField operator^(ll b)
  32.     {
  33.         QuadraticField ans;
  34.         QuadraticField a = *this;
  35.         ans.x = 1;
  36.         ans.y = 0;
  37.         while(b)
  38.         {
  39.             if(b & 1)
  40.             {
  41.                 ans = ans * a;
  42.                 b--;
  43.             }
  44.             b /= 2;
  45.             a = a * a;
  46.         }
  47.         return ans;
  48.     }
  49. };
  52. ll Lengender(ll a)
  53. {
  54.     ll ans = powMod(a,(p - 1) / 2);
  55.     if(ans + 1 == p)  return -1;
  56.     else  return ans;
  57. }
  59. ll GetW(ll n,ll a)
  60. {
  61.     return ((a * a - n) % p + p) % p;
  62. }
  64. ll Solve(ll n)
  65. {
  66.     ll a;
  67.     if(p == 2)  return n;
  68.     if(Lengender(n) == -1)  ok = false;
  69.     srand((unsigned)time(NULL));
  70.     while(1)
  71.     {
  72.         a = rand() % p;
  73.         w = GetW(n,a);
  74.         if(Lengender(w) == -1)  break;
  75.     }
  76.     QuadraticField ans,res;
  77.     res.x = a;
  78.     res.y = 1;
  79.     ans = res ^ ((p + 1) / 2);
  80.     return ans.x;
  81. }
  84. int main()
  85. {
  86.     ll n,ans1,ans2;
  87.     while(scanf("%lld %lld",&n,&p) != EOF)
  88.     {
  89.         ok = true;
  90.         n %= p;
  91.         ans1 = Solve(n);
  92.         ans2 = p - ans1;
  93.         if(!ok)  printf("-1\n");
  94.         else  printf("%lld %lld\n",ans1,ans2);
  95.     }
  96.     return 0;
  97. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注