[关闭]
@Pinetrie 2019-08-25T14:48:19.000000Z 字数 17882 阅读 866

模板

数位dp

l到r的数字中没有4和62的数有多少个

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,m,dp[20][2],num[20];
  5. int dfs(int pos,int if6,int limit)
  6. {
  7.     if(pos == 0) return 1;
  8.     if(!limit && dp[pos][if6] != -1) return dp[pos][if6];
  9.     int up = limit ? num[pos] : 9;
  11.     int temp = 0;
  12.     for(int i = 0;i <= up;i++)
  13.     {
  14.         if(i == 4) continue;
  15.         if(if6 == 1 && i == 2) continue;
  17.         temp += dfs(pos - 1,i == 6,limit && i == num[pos]);
  18.     }
  20.     if(!limit) dp[pos][if6] = temp;
  21.     return temp;
  22. }
  24. int solve(int x)
  25. {
  26.     int tot = 0;
  27.     while(x)
  28.     {
  29.         num[++tot] = x % 10;
  30.         x /= 10;
  31.     }
  32.     return dfs(tot,0,1);
  33. }
  35. int main()
  36. {
  37.     while(scanf("%d %d",&n,&m) && (n + m))
  38.     {
  39.         memset(dp,-1,sizeof(dp));
  40.         printf("%d\n",solve(m) - solve(n - 1));
  41.     }
  42.     return 0;
  43. }

二分图最大匹配算法

求最小顶点覆盖集的方法：

如果是拿匈牙利跑的话，需要求出最大匹配后，从左部的每个非匹配点再跑dfs，最终左边未被标记的点，与右边被标记的点就是覆盖的点集。如果是拿dinic分层跑的话，左部的点就是d[]为0的点，右部就是d[]不为0的点。

  1. #include <bits/stdc++.h>
  2. #define MAX_V 1100
  3. using namespace std;
  5. int V,P;
  6. vector<int> G[MAX_V];
  7. int match[MAX_V];
  8. bool used[MAX_V];
  10. void add_edge(int u,int v)
  11. {
  12.     G[u].push_back(v);
  13.     G[v].push_back(u);
  14. }
  16. bool dfs(int v)
  17. {
  18.     used[v] = true;
  19.     for(int i = 0;i < (int)G[v].size();i++)
  20.     {
  21.         int u = G[v][i];
  22.         if(!used[u])
  23.         {
  24.             used[u] = 1;
  25.             if(match[u] == -1 || dfs(match[u]))
  26.             {
  27.                 match[u] = v;
  28.                 match[v] = u;
  29.                 return 1;
  30.             }
  31.         }
  32.     }
  33.     return false;
  34. }
  36. int binary_match()
  37. {
  38.     int res = 0;
  39.     memset(match,-1,sizeof(match));
  40.     for(int v = 0; v < V; v++)
  41.     {
  42.         if(match[v] < 0)
  43.         {
  44.             memset(used,0,sizeof(used));
  45.             if(dfs(v))
  46.             {
  47.                 res++;
  48.             }
  49.         }
  50.     }
  51.     return res;
  52. }
  54. int main()
  55. {
  56.     int T;
  57.     scanf("%d",&T);
  58.     while(T--)
  59.     {
  60.         for(int i = 1;i <= MAX_V;i++) G[i].clear();
  62.         scanf("%d %d",&P,&V);
  63.         V += P;
  64.         for(int i = 1;i <= P;i++)
  65.         {
  66.             int n;
  67.             scanf("%d",&n);
  68.             for(int j = 1;j <= n;j++)
  69.             {
  70.                 int x;
  71.                 scanf("%d",&x);
  72.                 add_edge(i,x + P);
  73.             }
  74.         }
  75.         int edge_num = binary_match();
  77.         if(edge_num == P)    printf("YES\n");
  78.         else                 printf("NO\n");
  79.     }
  80.     return 0;
  81. }

高斯消元

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const double EPS = 1E-8;
  5. typedef vector<double> vec;
  6. typedef vector<vec> mat;
  8. //求解Ax = b，其中A是方阵//
  9. //当方程无解或无穷多解时，返回一个长度为0的数组//
  10. vec gauss_jordan(const mat& A,const vec& b)
  11. {
  12.     int n = A.size();
  14.     mat B(n,vec(n + 1));
  15.     for(int i = 0; i < n; i++)
  16.         for(int j = 0; j < n; j++)
  17.             B[i][j] = A[i][j];
  19.     //把b存放在A的右边方便一起处理//
  20.     for(int i = 0; i < n; i++)
  21.         B[i][n] = b[i];
  23.     for(int i = 0; i < n; i++)
  24.     {
  25.         //把正在处理的未知数系数最大的式子换到第i行//
  26.         int pivot = i;
  27.         for(int j = i; j < n; j++)
  28.         {
  29.             if(abs(B[j][i] > abs(B[pivot][i])))
  30.                 pivot = j;
  31.         }
  32.         swap(B[i],B[pivot]);
  34.         //无解或者无穷多解//
  36.         if(abs(B[i][i]) < EPS)
  37.             return vec();
  39.         //把正在处理的未知数系数边为1//
  40.         for(int j = i + 1; j <= n; j++)
  41.             B[i][j] /= B[i][i];
  42.         for(int j = 0; j < n; j++)
  43.         {
  44.             if(i != j)
  45.             {
  46.                 //从第j个式子中消去第i个未知数//
  47.                 for(int k = i + 1; k <= n; k++)
  48.                     B[j][k] -= B[j][i] * B[i][k];
  49.             }
  50.         }
  51.     }
  52.     vec x(n);
  53.     //存放在右边的b就是答案//
  54.     for(int i = 0; i < n; i++)
  55.         x[i] = B[i][n];
  56.     return x;
  57. }
  59. int main()
  60. {
  61.     int n;
  62.     scanf("%d",&n);
  63.     mat A(n,vec(n));
  64.     vec B(n);
  66.     for(int i = 0; i < n; i++)
  67.     {
  68.         for(int j = 0; j < n; j++)
  69.         {
  70.             double val;
  71.             scanf("%lf",&val);
  72.             A[i][j] = val;
  73.         }
  74.     }
  76.     for(int i = 0; i < n; i++)
  77.     {
  78.         double val;
  79.         scanf("%lf",&val);
  80.         B[i] = val;
  81.     }
  83.     vec C = gauss_jordan(A,B);
  85.     for(int i = 0; i < n; i++)
  86.         printf("%f ",C[i]);
  88.     return 0;
  89. }
  90. /*
  91. 输入:
  92. 3
  93. 1 -2 3
  94. 4 -5 6
  95. 7 -8 10
  96. 6 12 21
  97. 输出:
  98. 1.00000 2.00000 3.00000
  99. */

LCA targan离线

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int maxn = 40010;
  5. int n,m,tot,qtot;
  6. int head[maxn * 2],qhead[maxn * 2],dis[maxn],vis[maxn],fa[maxn],LCA[maxn];
  8. struct NODE
  9. {
  10.     int v,next,w;
  11. }node[maxn * 2];
  13. struct QNODE
  14. {
  15.     int v,next,w;
  16. }qnode[maxn * 2];
  18. struct ASK
  19. {
  20.     int x1,x2;
  21. }ask[maxn];
  23. void init()
  24. {
  25.     memset(head,-1,sizeof(head));
  26.     memset(qhead,-1,sizeof(qhead));
  27.     memset(dis,0x3f3f3f3f,sizeof(dis));
  28.     dis[1] = 0;
  29.     memset(vis,0,sizeof(vis));
  30.     for(int i = 1;i <= n;i++)  fa[i] = i;
  31.     tot = qtot = 0;
  32. }
  34. void addnode(int u,int v,int w)
  35. {
  36.     node[tot].v = v;
  37.     node[tot].w = w;
  38.     node[tot].next = head[u];
  39.     head[u] = tot++;
  40. }
  42. void addnodeq(int u,int v,int w)
  43. {
  44.     qnode[qtot].v = v;
  45.     qnode[qtot].w = w;
  46.     qnode[qtot].next = qhead[u];
  47.     qhead[u] = qtot++;
  48. }
  50. int Find(int x)
  51. {
  52.     if(x == fa[x])  return x;
  53.     return fa[x] = Find(fa[x]);
  54. }
  56. void tarjan(int u)
  57. {
  58.     vis[u] = 1;
  59.     for(int i = qhead[u];i != -1;i = qnode[i].next)
  60.     {
  61.         int v = qnode[i].v;
  62.         if(vis[v])  LCA[qnode[i].w] = Find(fa[v]);
  63.     }
  64.     for(int i = head[u];i != -1;i = node[i].next)
  65.     {
  66.         int v = node[i].v,w = node[i].w;
  67.         if(!vis[v])
  68.         {
  69.             dis[v] = dis[u] + w;
  70.             tarjan(v);
  71.             fa[v] = u;
  72.         }
  73.     }
  74. }
  76. int main()
  77. {
  78.     int T;
  79.     scanf("%d",&T);
  80.     while(T--)
  81.     {
  82.         scanf("%d %d",&n,&m);
  83.         init();
  84.         //for(int i = 1;i <= n;i++)  printf("%d\n",fa[i]);//
  85.         for(int i = 1;i < n;i++)
  86.         {
  87.             int u,v,w;
  88.             scanf("%d %d %d",&u,&v,&w);
  89.             addnode(u,v,w);
  90.             addnode(v,u,w);
  91.         }
  92.         for(int i = 1;i <= m;i++)
  93.         {
  94.             int u,v;
  95.             scanf("%d %d",&u,&v);
  96.             addnodeq(u,v,i);
  97.             addnodeq(v,u,i);
  98.             ask[i].x1 = u,ask[i].x2 = v;
  99.         }
  100.         tarjan(1);
  101.         for(int i = 1;i <= m;i++)
  102.         {
  103.             int u = ask[i].x1,v = ask[i].x2;
  104.             printf("%d\n",dis[u] + dis[v] - 2 * dis[LCA[i]]);
  105.         }
  106.     }
  108.     return 0;
  109. }

高精度+,-,*,/,%

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5. using namespace std;
  6. #define maxn 2000
  7. #define base 10000
  9. struct Bign
  10. {
  11.     int c[maxn],len,sign;
  12.     //初始化
  13.     Bign(){memset(c,0,sizeof(c)),len = 1,sign = 0;}
  14.     //高位清零
  15.     void Zero()
  16.     {
  17.         while(len > 1 && c[len] == 0)len--;
  18.         if(len == 1 && c[len] == 0)sign = 0;
  19.     }
  20.     //压位读入
  21.     void Write(char *s)
  22.     {
  23.         int k = 1,l = strlen(s);
  24.         for(int i = l - 1;i >= 0;i--)
  25.         {
  26.             c[len] += (s[i] - '0') * k;
  27.             k *= 10;
  28.             if(k == base)
  29.             {
  30.                 k = 1;
  31.                 len++;
  32.             }
  33.         }
  34.     }
  35.     void Read()
  36.     {
  37.         char s[maxn] = {0};
  38.         scanf("%s",s);
  39.         Write(s);
  40.     }
  41.     //输出
  42.     void Print()
  43.     {
  44.         if(sign)printf("-");
  45.         printf("%d",c[len]);
  46.         for(int i = len - 1;i >= 1;i--)printf("%04d",c[i]);
  47.         printf("\n");
  48.     }
  49.     //重载 = 运算符，将低精赋值给高精
  50.     Bign operator = (int a)
  51.     {
  52.         char s[100];
  53.         sprintf(s,"%d",a);
  54.         Write(s);
  55.         return *this;//this只能用于成员函数，表示当前对象的地址
  56.     }
  57.     //重载 < 运算符
  58.     bool operator < (const Bign &a)const
  59.     {
  60.         if(len != a.len)return len < a.len;
  61.         for(int i = len;i >= 1;i--)
  62.         {
  63.             if(c[i] != a.c[i])return c[i] < a.c[i];
  64.         }
  65.         return 0;
  66.     }
  67.     bool operator > (const Bign &a)const
  68.     {
  69.         return a < *this;
  70.     }
  71.     bool operator <= (const Bign &a)const
  72.     {
  73.         return !(a < *this);
  74.     }
  75.     bool operator >= (const Bign &a)const
  76.     {
  77.         return !(*this < a);
  78.     }
  79.     bool operator != (const Bign &a)const
  80.     {
  81.         return a < *this || *this < a;
  82.     }
  83.     bool operator == (const Bign &a)const
  84.     {
  85.         return !(a < *this) && !(*this < a);
  86.     }
  87.     bool operator == (const int &a)const
  88.     {
  89.         Bign b;b = a;
  90.         return *this == b;
  91.     }
  93.     //重载 + 运算符
  94.     Bign operator + (const Bign &a)
  95.     {
  96.         Bign r;
  97.         r.len = max(len,a.len) + 1;
  98.         for(int i = 1;i <= r.len;i++)
  99.         {
  100.             r.c[i] += c[i] + a.c[i];
  101.             r.c[i + 1] += r.c[i] / base;
  102.             r.c[i] %= base;
  103.         }
  104.         r.Zero();
  105.         return r;
  106.     }
  107.     Bign operator + (const int &a)
  108.     {
  109.         Bign b;b = a;
  110.         return *this + b;
  111.     }
  112.     //重载 - 运算符
  113.     Bign operator - (const Bign &a)
  114.     {
  115.         Bign b,c;// b - c
  116.         b = *this;
  117.         c = a;
  118.         if(c > b)
  119.         {
  120.             swap(b,c);
  121.             b.sign = 1;
  122.         }
  123.         for(int i = 1;i <= b.len;i++)
  124.         {
  125.             b.c[i] -= c.c[i];
  126.             if(b.c[i] < 0)
  127.             {
  128.                 b.c[i] += base;
  129.                 b.c[i + 1]--;
  130.             }
  131.         }
  132.         b.Zero();
  133.         return b;
  134.     }
  135.     Bign operator - (const int &a)
  136.     {
  137.         Bign b;b = a;
  138.         return *this - b;
  139.     }
  140.     //重载 * 运算符
  141.     Bign operator * (const Bign &a)
  142.     {
  143.         Bign r;
  144.         r.len = len + a.len + 2;
  145.         for(int i = 1;i <= len;i++)
  146.         {
  147.             for(int j = 1;j <= a.len;j++)
  148.             {
  149.                 r.c[i + j - 1] += c[i] * a.c[j];
  150.             }
  151.         }
  152.         for(int i = 1;i <= r.len;i++)
  153.         {
  154.             r.c[i + 1] += r.c[i] / base;
  155.             r.c[i] %= base;
  156.         }
  157.         r.Zero();
  158.         return r;
  159.     }
  160.     Bign operator * (const int &a)
  161.     {
  162.         Bign b;b = a;
  163.         return *this * b;
  164.     }
  165.     //重载 / 运算符
  166.     Bign operator / (const Bign &b)
  167.     {
  168.         Bign r,t,a;
  169.         a = b;
  170.         //if(a == 0)return r;
  171.         r.len = len;
  172.         for(int i = len;i >= 1;i--)
  173.         {
  174.             t = t * base + c[i];
  175.             int div,ll = 0,rr = base;
  176.             while(ll <= rr)
  177.             {
  178.                 int mid = (ll + rr) / 2;
  179.                 Bign k = a * mid;
  180.                 if(k > t)rr = mid - 1;
  181.                 else
  182.                 {
  183.                     ll = mid + 1;
  184.                     div = mid;
  185.                 }
  186.             }
  187.             r.c[i] = div;
  188.             t = t - a * div;
  189.         }
  190.         r.Zero();
  191.         return r;
  192.     }
  193.     Bign operator / (const int &a)
  194.     {
  195.         Bign b;b = a;
  196.         return *this / b;
  197.     }
  198.     //重载 % 运算符
  199.     Bign operator % (const Bign &a)
  200.     {
  201.         return *this - *this / a * a;
  202.     }
  203.     Bign operator % (const int &a)
  204.     {
  205.         Bign b;b = a;
  206.         return *this % b;
  207.     }
  208. };
  210. int main()
  211. {
  212.     Bign a,b,c,d,e,f,g;
  213.     a.Read();
  214.     b.Read();
  215.     c = a + b;
  216.     c.Print();
  217.     d = a - b;
  218.     d.Print();
  219.     e = a * b;
  220.     e.Print();
  221.     f = a / b;
  222.     f.Print();
  223.     g = a % b;
  224.     g.Print();
  225.     return 0;
  226. }

exgcd

  1. #include<iostream>
  2. using namespace std;
  4. int exgcd(int a,int b,int &x,int &y)
  5. {
  6.      if(b==0)
  7.     {
  8.         x=1;
  9.         y=0;
  10.         return a;
  11.     }
  12.     int gcd=exgcd(b,a%b,x,y);
  13.     int x2=x,y2=y;
  14.     x=y2;
  15.     y=x2-(a/b)*y2;
  16.     return gcd;
  17. }
  19. int main()
  20. {
  21. int x,y,a,b;
  22. cout<<"请输入a和b:"<<endl;
  23. cin>>a>>b;
  24. cout<<"a和b的最大公约数:"<<endl;
  25. cout<<exgcd(a,b,x,y)<<endl;
  26. cout<<"ax+by=gcd(a,b) 的一组解是:"<<endl;
  27. cout<<x<<" "<<y<<endl;
  28. return 0;
  29. }

manacher

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int maxn = 100010;
  5. char s[maxn],temp[2 * maxn];
  6. int p[2 * maxn];
  8. void init()  {
  9.     int n = strlen(s);
  10.     temp[0] = '$';
  11.     for(int i = 1;i <= n;i++)  {
  12.         temp[i * 2] = s[i - 1];
  13.         temp[i * 2 - 1] = '#';
  14.     }
  15.     temp[n * 2 + 1] = '#';
  16.     temp[n * 2 + 2] = '\0';
  17. }
  19. int manacher()  {
  20.     int n = 2 * strlen(s) + 1;
  21.     int mx = 0,ans = 0,mark = 0;
  22.     for(int i = 1;i <= n;i++)  {
  23.         if(mx > i)  p[i] = min(mx - i,p[mark * 2 - i]);
  24.         else        p[i] = 1;
  26.         while(temp[i + p[i]] == temp[i - p[i]])  p[i]++;
  28.         if(i + p[i] > mx)  {
  29.             mx = p[i] + i;
  30.             mark = i;
  31.         }
  32.         ans = max(ans,p[i]);
  33.     }
  34.     return ans - 1;
  35. }
  37. int main()  {
  38.     while(scanf("%s",s) != EOF)  {
  39.         init();
  40.         printf("%d\n",manacher());
  41.     }
  42.     return 0;
  43. }

RMQ

快速查询区间最值

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  5. const int maxn = 100010;
  6. int Min[maxn][20],Max[maxn][20],a[maxn];
  7. int n,q;
  9. struct RMQ
  10. {
  11.     int log2[maxn];
  12.     void init()
  13.     {
  14.         for(int i = 0;i <= n;i++)  log2[i] = (i == 0 ? -1 : log2[i>>1] + 1);
  15.         for(int j = 1;j < 20;j++)
  16.         {
  17.             for(int i = 1;i + (1<<j) <= n + 1;i++)
  18.             {
  19.                 Min[i][j] = min(Min[i][j - 1],Min[i + (1<<(j - 1))][j - 1]);
  20.                 Max[i][j] = max(Max[i][j - 1],Max[i + (1<<(j - 1))][j - 1]);
  21.             }
  22.         }
  23.     }
  24.     int Min_query(int l,int r)
  25.     {
  26.         int k = log2[r - l + 1];
  27.         return min(Min[l][k],Min[r - (1<<k) + 1][k]);
  28.     }
  29.     int Max_query(int l,int r)
  30.     {
  31.         int k = log2[r - l + 1];
  32.         return max(Max[l][k],Max[r - (1<<k) + 1][k]);
  33.     }
  34. };
  36. int main()
  37. {
  38.     scanf("%d %d",&n,&q);
  39.     for(int i = 1;i <= n;i++)
  40.     {
  41.         scanf("%d",&a[i]);
  42.         Min[i][0] = a[i];
  43.         Max[i][0] = a[i];
  44.     }
  45.     RMQ rmq;
  46.     rmq.init();
  47.     for(int i = 1;i <= q;i++)
  48.     {
  49.         int l,r;
  50.         scanf("%d %d",&l,&r);
  51.         printf("%d\n",rmq.Max_query(l,r) - rmq.Min_query(l,r));
  52.     }
  53.     return 0;
  54. }

莫队算法

离线解决区间询问
q*sqrt(n)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 500100;
  7. struct Que
  8. {
  9.     ll l,r,id,block;
  10.     Que() {}
  11.     Que(ll l,ll r,ll id):l(l),r(r),id(id) {}
  12.     bool operator < (const Que &rhs) const
  13.     {
  14.         if(block == rhs.block)  return r < rhs.r;
  15.         return block < rhs.block;
  16.     }
  17. }ques[maxn];
  19. ll n,m,len;
  20. ll a[maxn];
  21. ll ansx[maxn],ansy[maxn],sum;
  22. ll cor[maxn];
  24. void add(ll x)
  25. {
  26.     sum += 2 * cor[x];
  27.     cor[x]++;
  28. }
  30. void sub(ll x)
  31. {
  32.     sum -= (2 * cor[x] - 2);
  33.     cor[x]--;
  34. }
  36. ll gcd(ll x,ll y)
  37. {
  38.     return y == 0 ? x : gcd(y,x % y);
  39. }
  41. int main()
  42. {
  43.     scanf("%lld %lld",&n,&m);
  44.     len = sqrt(n);
  45.     for(int i = 1;i <= n;i++)  scanf("%lld",&a[i]);
  46.     for(int i = 1;i <= m;i++)
  47.     {
  48.         ll l,r;
  49.         scanf("%lld %lld",&l,&r);
  50.         ques[i] = Que(l,r,i);
  51.         ques[i].block = l / len;
  52.     }
  53.     sort(ques + 1,ques + 1 + m);
  55.     ll L = 1,R = 1;
  56.     cor[a[1]]++;
  57.     sum = 0;
  58.     for(int i = 1;i <= m;i++)
  59.     {
  60.         ll l = ques[i].l,r = ques[i].r,id = ques[i].id;
  61.         while(R < r)  add(a[++R]);
  62.         while(L > l)  add(a[--L]);
  63.         while(R > r)  sub(a[R--]);
  64.         while(L < l)  sub(a[L++]);
  66.         ll cnt1 = sum;
  67.         ll cnt2 = (ll)(r - l + 1) * (r - l);
  68.         if(cnt1 == 0)
  69.         {
  70.             ansx[id] = 0,ansy[id] = 1;
  71.             continue;
  72.         }
  73.         ll k = gcd(cnt1,cnt2);
  74.         ansx[id] = cnt1 / k,ansy[id] = cnt2 / k;
  75.     }
  77.     for(int i = 1;i <= m;i++)
  78.     {
  79.         printf("%lld/%lld\n",ansx[i],ansy[i]);
  80.     }
  81.     return 0;
  82. }

树链剖分

题目描述
如题，已知一棵包含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. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注