基础算法
位运算
拆解：例如龟速乘和快速幂。
状态压缩：可以用一个数字表示一个状态，不够长还可以用bitset。
龟速乘
通过对数字的每一位进行拆分，将乘法变成加法。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mul(ll a,ll b,ll p){
ll ans=0;
while(b){
if(b&1)ans=(ans+a)%p;
a=2*a%p;
b>>=1;
}
return ans;
}
int main(){
ll a,b,p;
scanf("%lld%lld%lld",&a,&b,&p);
printf("%lld",mul(a,b,p));
}
快速幂
与龟速乘相类似，将次幂分解成若干次乘法。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p;
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans%p;
}
int main(){
scanf("%lld%lld%lld",&a,&b,&p);
printf("%lld^%lld mod %lld=%lld",a,b,p,qpow(a,b));
}
起床综合困难症
此题秒处是位运算只能影响到当前位，可以单独考虑每位。
奇偶变换
x^1，一般用于建双向边。