路终会有尽头，但视野总能看到更远的地方。

方法一

沿用快速幂的方法，将乘法改为加法，时间复杂度$O(\log b)$

1
2
3
4
5

LL Quick_Mul(LL a,LL b,LL p) {
	LL sum=0;
	for(; b; b>>=1,a=(a+a)%p)if(b&1)sum=(sum+a)%p;
	return sum;
}

推荐Menci!的学习笔记
这里是我的模板，喜欢就给个star吧。

题目大意

    魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心，于是他想了一道数学题。
    $S$是一个可重集合，$S=\lbrace a_1,a_2,\ldots,a_n\rbrace$。
    等概率选取$S$的一个子集$A=\lbrace {a_i}_1,\ldots,{a_i}_m\rbrace$。
    计算出$A$中所有元素的异或和$x$，求$x^k(1\le k\le5)$的期望。

一些记号

在本文中，为了描述方便，我们使用以下记号：

• $\bigoplus$：异或。$2\bigoplus3=1$。
• $\vec v$：向量，本文中的向量是抽象的数学概念，而非简单的带方向的数。

题目大意

    给出一棵树，求这棵树两点之间路径上点权的异或和最大值。

题目大意

    给定$n(n\le10000)$个数$a_i$，以及一个数$Q$。将$a$的所有子集（可以为空）的异或值从小到大排序得到序列$B$，请问$Q$在$B$中第一次出现的下标是多少？保证$Q$在$B$中出现。

题目大意

    有一个长度为$n$的序列，支持两种操作：
      $0\,x\,y$：把$x$位置上的数换成$y$。
      $1\,x\,y$：在$[x,y]$中，请你任选一些数使他们的异或和最大。

题目大意

    给出一个边权非负的无向连通图，求一条从$1\rightarrow n$的路径，使得路径边权的$xor$和最大。
    若一条边在路径中多次出现，权值也要被累加相应多次。

题目大意

    给由$n$个数组成的一个可重集$S$，每次给定一个数$k$，求一个集合$T\subseteq S$，使得集合$T$在$S$的所有非空子集的不同的异或和中，其异或和$T_1\,xor\,T_2\,xor\ldots\,xor\,T_{|T|}$是第$k$小的。

题目大意

    给由$n$个数组成的一个可重集$S$，求一个集合$T\subseteq S$ ，使$T_1\,xor\,T_2\,xor\ldots\,xor\,T_{|T|}$最大。