SAM模板

#include<bits/stdc++.h>using namespace std;const int maxn=1e6+5;const int mod=1e9+7;#define pb push_back#define all(x) (x).begin(),(x).end()type

FFT,NTT,FWT模板

-------------"<<T<<endl;int len=2;for(i=1;(1<<i)<(n+m-1);i++)len<<=1;getrev(i);solve('P',len,n,m);solve('S',len,n,m);s

HDU3949 XOR（线性基）

HDU3949 XOR(线性基)题目：给你$n$个数，从其中随便取任意数问你第$k$小的异或和是多少。题解：这题是线性基的应用之一。我们知道一个集合的线性基可以异或出这个集合的所有异或和，并且方法唯一。对于一个数x能否被异或出来，我们可以这样做，假设x的最高位为r，那么在线性基里面找到最高为也为r的

codeforces 616F Expensive Strings

codeforces 616F Expensive Strings （广义后缀自动机）https://codeforces.com/contest/616/problem/F题意：给你n个字符串串，串$S_i$的权值为$c_i$，对于一个字符串$s$有函数$$F(s)=\sum_^c_ip_{s,i

Bzoj2440 完全平方数(莫比乌斯容斥)

###Bzoj2440 完全平方数(莫比乌斯容斥)####题意：找第k个不含完全平方数因子的数####题解：二分+莫比乌斯系数+容斥#include<bits/stdc++.h>using namespace std;const int maxn=1e5+5;bool isprime[m

Blocks(组合数学——生成函数)

Blockshttps://cn.vjudge.net/problem/POJ-3734题意：一排有n块砖，每块砖可以染成A,B,C,D四种颜色的其中一种，现在问你A颜色砖块有偶数个，B颜色砖块有偶数个的染色方法有几种？题解：这题虽然可以用矩阵快速幂的方法做，但也存在一种能秒杀这题的方法———生成函

AC自动机模板

struct AC_Automaton {int next[maxn][26];int fail[maxn];int end[maxn];int sz, root;int newNode() {for(int i = 0; i < 26; i++) {next[sz][i] = -1;}fai