题解
首先声明……其实我们的答案跟没太大关系，这一部分只需要在最后的时候对应乘上即可，此题最核心的部分是计算选择了i种颜色的方案数。
首先我们来看如果我们选择了i种颜色使它们恰好出现了S次，那么选择颜色种类的方案数即为,然后我们去用这i个颜色涂这n个位置的时候，实际上就是一个可重排列的计算数，方案总数为,然后剩下的位置任意涂色，一共还剩n-i*S个位置，每个位置有m-i种颜色选择，所以方案数为。
我们记
然而这并不是恰好有i种颜色恰好都出现k次。实际上在我们在后面自由涂色的时候，我们依旧有可能会将一种颜色涂成恰好出现k次。
So……这时候我们就用到容斥原理了。假设为恰好i种颜色都恰好出现k次,由容斥原理有：
#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int maxm = 1e5+5;
const int maxn = 1e7+5;
typedef long long ll;
const ll mod = 1004535809;
ll fac[maxn],inv[maxn],w[maxm],f[maxm<<2],finv[maxn];
ll b[maxm<<2];
int rev[maxm<<2];
void init(int x){
fac[0] = fac[1] = inv[0] = inv[1] = finv[0] = finv[1] = 1ll;
for(int i = 2;i <= x;++i){
fac[i] = fac[i-1] * i % mod;
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
finv[i] = finv[i-1] * inv[i] % mod;
}
return;
}
ll quick_pow(ll a,ll b,ll mod){
ll ret = 1;
while(b){
if(b & 1)
ret = (ret * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ret;
}
ll g;
int len,lg;
void NTT_init(int k){
len = 1;lg = 0;
for(len = 1;len < k;len <<= 1,lg++);
for(int i = 0;i < len;++i)
rev[i] = (rev[i>>1]>>1) | ((i & 1) << (lg - 1));
}
void NTT(ll *a,int len,int f){
for(int i = 0;i < len;++i){
if(i < rev[i])
swap(a[i],a[rev[i
题目大意
给定一个n个点的DAG（有向无环图），每个点一开始都是白色，每一次操作会改变一个指定的点的颜色，并询问当前有多少对白点对(u,v)互相可达（存在一条从u到v的有向路径使得路径上全部为白色的点）。
题解
可以认为黑色点与其他点都不连通。
所以我们每一次更改点的颜色实际都是再更改图的联通关系。
我们可以通过搜索、topsort、floyd-warshell算法等计算两点间的联通关系（这时候就通过位运算或|来代替Floyd原先的+就好了，因为位运算或即为逻辑加操作）。
但是我们发现这样复杂度是不对的……
这三种最快的topsort复杂度也是O(qnm)的，明显不符合我们的复杂度要求。
这时候我们注意到对于联通关系，两点间的联通关系也即用0表示不连通，1表示联通。
我们对于更新也是这样的：
假设当前检索点为u，下一个点为v，则对于所有联通u的点k，假设mp[i][j]表示是否可从i联通到j，则有
mp[k][v] = mp[k][u]; ----> mp[k][v] |= mp[k][u];
可以看到这个更新过程实际上只有位运算的或操作，只有0和1的运算，所以可以用bitset进行加速。
当我们检索到当前的点u时，先预处理设定mp[u][u] = 1，表示当前点可以到达当前点。最终因为答案是算不相同的点u和v联通个数，所以最后进行统计的时候答案整体-n即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int d[maxn],tmp[maxn];
bitset<305>con[maxn];
queue<int>qk;
vector<int>g[maxn];
int n,m,q;
int a,b;
int c[maxn],vis[maxn];
void topsort(){
for(int i = 1;i <= n;++i)
con[i].reset();
for(int i = 1;i <= n;++i){
if(!c[i])
con[i][i] = 1;
vis[i] = 0;
}
for(int i = 1;i <= n;++i){
tmp[i] = d[i];
题目大意
给两个可重集合A，B，求问有多少个数x同时属于A的异或集和B的异或集。
此处的异或集指，从原集合中人与选出若干个数异或出的所有可能结果构成的集合。
题解
如果要我们去枚举每一个数选或者不选，那么一个集合的异或集最多会有250个种元素。这样枚举每种情况的代价太大了，我们如何能够构造一种能够表示异或集内所有可能的值呢？
这里很自然的想到可以对原集合构造异或线性基，线性基的插入就可以判断当前这个数能否被当前构造出的线性基表示。
如果一个数x属于当前集合的异或集，那么x一定能够用线性基向量中的所有位和系数0/1（代表选不选）的组合表示出来。
通过以下韦恩图，我们可以更轻松的理解容斥原理|A∩B| = |A| + |B| - |A∪B|：
其中|A|表示A的秩，也即元素个数。
我们对A、B、A∪B分别构造线性基，并分别求出秩ra，rb，rab，由于同时属于A和B的异或集的元素x一定由A∩B的异或集的线性基向量的各项及0/1系数组合构成，所以最终答案实际上就是2|xor_set(A∩B)|，也即2ra+rb-rab。
最终测试的是long long 就能过。
这里的秩当然也可以用高斯消元来解释（高斯消元实际上就对应着方程组矩阵的秩，有大学线性代数基础的同学可能比较清楚），不过高斯消元感觉比线性基更麻烦一些，所以我比赛的时候选择了线性基。
代码
#include <bits/stdc++.h>
int n;
typedef long long ll;
const int maxn = 55;
ll ans,a[maxn],b[maxn];
const int upper = 64;
ll xor_shift[upper];
bool add(ll x){
bool flag = false;
for(int i = upper-1;i >= 0;--i){
if(x & (1ll<<i)){
if(!xor_shift[i]){
xor_shift[i] = x;
flag = true;
break;
}
else{
x ^= xor_shift[i];
题目大意
给出n个数，要你从中选出一些数，使得他们的乘积mod 2017的余数为r，问总方案数mod 2的值。
题解
对于一些数的乘法，我们可以用log把他转化乘加法。
但是是在模意义下，就是需要离散模对数了。
这时候我们要求2017的原根，2017的原根是5，我们就可以自然而然的把原来的所有数都化为他们的离散模对数了。
首先如果数据范围很小，我们该怎么写呢？
那么我们可以用dp[i][j]表示当前为第枚举到第i个数，选出的前面的（包括i）所有数的乘积的离散模对数为j的方案数。
那么dp方程就很容易能够想到了：
dp[i][j] = dp[i-1][j] + (dp[i-1][(j-lg[a[i]])%2016]);
这两项分别代表当前项选/不选的情况。
可以看到第i位的值只跟他的前一位有关，所以空间可以滚动掉一维。
但是这样的时间仍然是O(n*2016)，n的数据范围让我们无法直接这样去做dp（而且由于依赖性无法使用多线程，这里我又在说胡话了）。
那我们该怎么办？
我们注意一下，答案只需要输出总方案数mod 2的值，所以注意一下dp方程，我们就可以这样去改了：
dp[i][j] = dp[i-1][j] ^ (dp[i-1][(j-lg[a[i]])%2016]);（二进制中的异或运算实际上就是加法对2取模）
也就是dp[j] = dp[j] ^ dp[(j-lg[a[i]])%2016];
计算机系统在进行二进制运算的时候是非常快的，所以可以用二进制的一些东西来加速这个运算，让枚举2016次的复杂度降低成为一个更小的常数，但是通常的数据类型不支持我们这么做。
这时候我们可以用C++中的bitset来对上面的式子进行加速。
如果我们用一个2016位的bitset<2016>f,那么上面的递推式就要写成以下形式：
f ^= (f<<lg[a[i]]) ^ (f>>(2016-lg[a[i]]));
这样由于计算机系统在对于bitset运算的速度较快，我们就可以通过此题了。
注意一定要用cout输出，printf输出会有问题。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; int lg[2020],a[2000005],n,r; bitset<2016>f; int main(
题解
如果你曾经经过大量的FFT/NTT的生成函数训练，应该一眼能够看出这道题一定是个多项式卷积用NTT优化……
如果是相加的话，我们可以直接设多项式S = Σaixi，（生成函数在这）其中ai表示数字i出现过多少次。
如果我们是选2个数的话，对于每一个和的方案数，很明显就是将S卷上S，然后取对应多项式项的系数即为方案数。
因为这个题是乘积，而且对于乘积还有对质数m取模操作，所以我们不能简单的按照上面的方法进行生成函数构造。
如何解决乘积问题呢？
我们知道多项式FFT/NTT都是建立在指数（下标）相加的基础上（也就是普通的多项式乘法的法则）进行的，所以我们想能不能把乘积变成加法，这样就可以按照经典套路进行生成函数构造了。
想了一下，取对数貌似可以把乘法变成加法来算了……
但是因为此处还是对质数m取模之后结果的统计，而且NTT也不支持浮点数，所以我们需要考虑在模意义下的对数，也就是离散模对数。
如何处理离散模对数呢……这里如果不了解的话就需要补一下基础的数论知识了。
这里我们需要求m的原根，求法也非常简单，直接暴力枚举的每个数，看对于每个质数pi | （m-1），是否g的(m-1)/pi次方mod m等于1，如果等于则说明不是原根，否则说明是原根，原根通常非常小，所以不用担心会在处理原根的时候TLE。
运用原根，我们可以把每个数在mod m意义下的离散模对数求出来，然后就变成正常的多项式卷积啦！
于是这个时候我们就可以用NTT来做啦。
但是由于要选N次，而N的数据范围到了1e9次，所以我们不能直接暴力NTT，要用快速幂的思想对多项式进行快速幂形式的卷积操作。
这里要注意每一次卷积完成的时候（IDNT之后），我们只是正常的进行了一次多项式卷积，统计答案的时候还是有问题的，因为指数并不能取模，所以每一卷积，都会有答案落在[m-1,2*m-2]上，我们要把这一区域上的答案对应地加到前面[0,m-2]上（对应了题目中的乘积取模操作）。
总时间复杂度为O(nlog2n)。
代码
#include <bits/stdc++.h> using namespace std; const int maxm = 16005; typedef long long ll; const ll gf = 3; int n,m,x,s; ll tmp; int sq; const ll mod = 1004535809; ll f
题目大意
给定一个字符集仅含a和b的字符串s，求字符串中不连续的回文子序列个数mod 1000000007的值。
题解
如果是连续的回文子序列，也就是回文串，那就很好求了，直接运用Manacher算法就可以了。
但是这题是让算所有的不连续的回文子序列……
然而这个是没法直接算出来的……
所以我们反过来想，我们可以把所有回文子序列的数量求出来，然后减去回文子串的数量，就是不连续的回文子序列的数量。
上面说了，如果是回文子串的数量，可以直接用Manacher算法算出来。
所以现在我们考虑的就是全体回文子序列的数量该怎么算。
对一个回文子序列，一定有一个中心，假设两个对应字符位置分别为x，y，那么，中心的位置一定是(x+y)/2。
我们可以将那个/2拿掉，这样算出来的新的中心位置也是唯一确定的，也就是和本质的回文中心位置一一对应。
对于一个位置，假设有x对（两个字符在同一位置也算一对）对应字符确定的中心位置在此位置，那么一定有以此位置为回文中心的回文子序列个数为2^x - 1。
如果我们直接暴力求出，那么复杂度是O(n2)的，n是100000的数据是吃不消的。
注意到字符集只含两个字符，再观察对应字符确定的新的中心位置的计算公式(pos = x + y)，我们可以对于字符a和字符b分别构造生成函数：
假设我们当前对字符c进行计算，则有生成函数f(x) = Σ((s[i] == c) ? 1 : 0) * xi。
可以看出，对字符c，有多少对对应字符的中心位置确定在所有的位置的数量与f(x)对f(x)的卷积在对应位置的系数值是有关系的（其实是一个近似于/2的关系，不过涉及到要讨论位置的奇偶，这里不再赘述）。
卷积可以所以相当于我们对字符a和b分别构造生成函数，分别进行FFT，然后对于每一个位置，将两个FFT算出的结果相加，然后+1，再除以2，即为当前位置为中心位置的对应字符对数（这里+1再/2（整除）是一个巧妙地避开对两个对应字符在相同位置（也就是说这一对字符完全就是一个字符）的讨论的做法，请自行理解）。之后按照上面的公式处理以下即可。
这样我们就求出了所有回文子序列的个数。
至于回文子串的个数，可以直接用Manacher算法来解。
但是……
博主不会Manacher……而且也懒得学……
可是我会PAM（回文自动机）啊！回文自动机可比Manacher好用多了（个人观点不代表官方意见）!
回文自动机里面的cnt[i]
题目大意
给定一个正整数n，有三个数组A,B,C，每个数组有n个数，求问有多少个三元组(i,j,k)满足|Ai-Bj|≤Ck，|Ck-Bj|≤Ai，|Ai-Ck|≤Bj
题解
首先我们发现，其实三元组满足的条件其实非常像三角形的构成条件，所以我们可以叙述成
“最小值 + 中间值 ≤ 最大值”
满足这样的三元组个数。
官方题解是正着算的，然后还有什么去重什么麻烦的东西，看起来令人头大……
所以我们为何不反过来算呢？
首先所有的取法总数是n3，然后我们只需要计算以下不满足的三元组总数即可了。
但是怎么做？
大概的思路就是对于某一个数组中的所有数，我们对每一个进行枚举，把当前枚举的数作为三元组的最大值，看剩下两个数组中有多少个二元组满足两个数加起来小于当前这个数。
具体的思路就是这样，但是暴力算时间复杂度会崩，是O(n3)的。
我们可以把所有二元组的和都预处理出来，用桶计数，表示当前二元组的和为i的组数有多少个。然后我们对要枚举的数列先从小到大排序，再进行枚举，用前缀和的思想找上述的不满足条件的二元组的个数即可，这样的做法是O(n2)的。
但是还不够，因为n最大是1e5。
这时候我们就要应用生成函数的思想，对于每一个数y，把y放在x的指数上，y在这个数组中出现的次数作为这一项的系数。这样任意两项乘在一起就相当于一个加和。
我们要算所有二元组的加和，用上面的生成函数的思想，就可以把暴力转化成为一个普通卷积，而卷积可以用FFT来加速。于是就可以优化为O(nlogn)。
整体需要3次DFT和3次IDFT。
然后按照上述方法前缀和枚举即可。
but……因为FFT是用桶的思路，所以每一次FFT都是用最大值代入的时间复杂度中的n，而且FFT常数巨大，这就导致我们直接FFT会超时。
我们关注到题目中N > 1000的数据组最多只有20组，于是我们可以分数据范围，n<1000 的直接n2暴力，n > 1000的使用FFT。这样就不会超时了。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
const double pi = acos(-1.0);
struct comp{
double r,i;
comp(double a = 0,double b = 0):r(a),i(b){};
题目大意
求一个分数x，使得其分母不超过100000并且f(x)与g(x)在x处最接近。
题解
首先很明确这是个二分的题目，不过分数怎么二分……。
首先我们二分出x3>k2的最小的整数x，然后这样进行分数二分：
首先设左端点分子为lz = x-1，分母为lm = 1，右端点分子为rz = x，分母为rm = 1.
二分的时候，我们取分子midz = lz + rz，分母midm = lm + rm。
判断是否小于当前差值最小值，如果是记录此时答案。
然后判断当前分数的三次方是否比k2大，如果是，区间右端点左移，否则区间左端点右移。
当分母midm > 100000的时候终止二分，输出答案即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double u,v;
ll lz,rz,lm,rm;
ll val,k;
int t;
ll mz,mm;
const long double INF = 1e19;
long double _abs(long double x){
return (x < 0) ? -x : x;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
cin >> k;
val = 0;
ll l = 1,r = 1e5;
while(l <= r){
ll mid = (l + r) >> 1;
if(mid * mid * mid >= k * k){
val = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(val * val * val == k * k){
cout << val << "/1" << "\n";
continue;
}
lm = rm
题目大意
给出一个字符串，求出所有回文串的字符种类数之和。
题解
考场上他们都有回文自动机的板子而我没有QAQ
首先对于一个子串，其对应一个子区间，这个子区间的数据的种类数的多少我们是可以用主席树来维护的，这是众所周知的。
具体维护方法：
从第1位置往后扫，如果之前出现过相同的数据，我们就在之前出现过的位置-1，在当前位置计数+1，然后把当前位置记录下来。
但是我们怎么求所有回文串的长度和数目？Manacher是不行的，效率太低了。
于是有一个神奇的PAM，也就是回文自动机。
回文自动机中，cnt[i]表示以i结尾的最长的回文串的数目，len[i]表示以i结尾的回文串的长度为多少，pos[i]表示以i为结尾的回文串在原串的位置是哪里。
这样的PAM的时间复杂度是O（n*log（字符集大小））的
这样我们就很容易能够求得答案了。
最终答案是ans = n + Σ query(root[pos[i]],1,siz,pos[i]-len[i]+1,pos[i]) * cnt[i];
据说还有后缀自动机SAM的做法，这个我也不怎么会……所以就不写了，等以后学QAQ。
如果对回文自动机不了解的可以去找博客https://www.cnblogs.com/nbwzyzngyl/p/8260921.html
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
typedef long long ll;
struct seg{
int ch[2];
int val;
}tr[maxn*25];
int root[maxn];
char s[maxn];
int siz = 0;
struct PAM{
int p,last,cur,n,S[maxn],len[maxn],pos[maxn],cnt[maxn],fail[maxn];
int nt[maxn][26];
int new_node(int l){
for(int i = 0;i < 26;++i)
nt[p][i] = 0;
len[p] = l;
cnt[p] = 0;
return p++;
}
inline v