# 杂题乱做2

### Dirichlet k-th root

f^k \equiv g \pmod p，已知g,pf

g=f^k

g'=kf'f^{k-1}

g'f=kf'g

g是一个K-1次多项式（原因待填

### Mergesort Strikes Back

f_{l,r,i}表示l,r没匹配，一共用了i个字符的方案数。

### 二分图染色

f_{n}=2nf_{n-1}-(n-1)^2f_{n-2}

### Misaka Network 与求和

\sum_{i=1}^n\sum_{j=1}^n f(gcd(i,j))^k，其中f表示次大因子。

min25筛的时候，分类讨论：在状态S(n,j)，钦定第二大因子在这里产生的方案，就是比p_j大的质数乘p_j。剩下的直接加就好了。

### A Sequence of Permutations

a_{p_i}=q_i,a_{i}=q_ip^{-1}_i。后面是找规律，这个我也没办法了

### Easy win

const int N = 130;
std::bitset<N> A[N], B[N];
long long ans, w[N];
int cnt;
bool ins[N];
inline void insert(std::bitset<N> a, int v) {
std::bitset<N> b;
for (int i = 128; ~i; --i) {
if (!a[i]) continue;
if (!ins[i]) {
ins[i] = 1;
ans += v;
w[++cnt] = v;
b[cnt] = 1;
A[i] = a;
B[i] = b;
return;
} else {
a ^= A[i];
b ^= B[i];
}
}
int pos = -1;
for (int i = 1; i <= cnt; ++i)
if (b[i] && (pos == -1 || (w[i] < w[pos])))
pos = i;
if (~pos && v > w[pos]) {
ans += v - w[pos];
w[pos] = v;
b[pos] = 0;
for (int i = 128; ~i; --i)
if (ins[i] && B[i][pos])
B[i] ^= b;
}
}
{"ft_lang_label":"__label__zh","ft_lang_prob":0.9198477,"math_prob":0.99971765,"size":11461,"snap":"2021-31-2021-39","text_gpt3_token_len":10765,"char_repetition_ratio":0.040237408,"word_repetition_ratio":0.010928961,"special_character_ratio":0.24989094,"punctuation_ratio":0.06467662,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99987423,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-08-04T17:08:37Z\",\"WARC-Record-ID\":\"<urn:uuid:2ba45cbb-00f7-477b-9be9-39cd3fb56efb>\",\"Content-Length\":\"58342\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:233003e1-9797-4256-90cf-49ffc37a85b2>\",\"WARC-Concurrent-To\":\"<urn:uuid:aa047f37-4a33-45e8-8fda-7d41834c8f42>\",\"WARC-IP-Address\":\"66.42.65.8\",\"WARC-Target-URI\":\"https://baka.online/noi%E5%89%8D%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95/\",\"WARC-Payload-Digest\":\"sha1:S2XV33YPFVIYNIST5YNAPESOTKTPX3GB\",\"WARC-Block-Digest\":\"sha1:PZGVP2E7AJQRHFUODYL4LBFYAEQHPEZL\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-31/CC-MAIN-2021-31_segments_1627046154878.27_warc_CC-MAIN-20210804142918-20210804172918-00428.warc.gz\"}"}