未央の童话镇

风格迁移问题中，我们需要实现从输入图片到输出图片的映射，那么在训练一个Generator的时候我们需要成对的训练集，然而成对的训练集并不容易获得 因此我们希望采用GAN的形式处理风格迁移问题，$G$负责学习映射，$D$负责判别是否为规定风格 然而GAN处理的问题就在于自由度过大，可能一张清明上河图进到GAN里面风格转化的结果是一张梵高的自画像，即G完全可以为了骗过$D$将Domain X中的所有内容映射到Domain Y中的一张图，使得损失函数无效化 那么我们需要的就不仅是风格上的正确了，而是图片的分布也不能发生太大的变化 所以除去生成器$G(X\to Y)$之外，我们再建立一个生成器$G(Y \to X)$，我们希望在一张图片被映射到Domain Y之后能够被映射回Domain X，且与原来的图片大致相同 与此同时，一张图片在通过$G(Y \to X)$映射到Domain X之后，也应该能通过$G(X \to Y)$得到一张和原图大致相同的图片 定义一个循环一致性损失$L_{cyc}(F,G,X,Y)=E_{x \sim p_{data(x)}}[||G(F(x))-x||1]+E{ ...

CGAN(Conditional Generative Adversarial Nets)指的是带有附加条件的GAN网络 (GAN的介绍戳此处) 用传统的方法去训练一个输入为text输出的image的generator最后的学习结果会是同一类图片的平均，图片通常非常的模糊 CGAN的Generator是通过一个接受一个正态分布z和目标限定词$c$得到对应的产出$G(c,z)$，额外信息$c$的引入对生成增加了条件来指导生成，将原先无监督的GAN模型变成了一个有监督的学习过程 与此同时Discriminator也要发生相应的变化，因为如果采用原始GAN的Discriminator的话难以起到对限定词$c$的训练效果，因为不管你的限定词是猪或者是狗，$G$发现只要生成一张清晰的猫的图片，$D$就能给出高分，那么$G$就可以无视限定词直接去学习生成猫就可以了（completely ignore the input conditions） 因此CGAN中，Discriminator不能只接受Generator的输出，还要接受G的输入，Discriminator需要做的不仅是判断图片是否是真实的 ...

GAN(generative adversarial networks)指生成对抗网络 GAN包含一个Generator(以下简称$G$)和一个Discriminator(以下简称$D$) $G$是一个生成器，其本质是一个多层感知机，接收一个向量，将其映射到新的数据空间(输出为图片，句子或者其它) $D$是一个判别器，也是一个多层感知机，输出一个标量，表示输入数据属于真实数据的概率 GAN就是$G$和$D$协同演化的过程 用图像生成作为例子，就是$G$不断去生成图片企图混淆真实图片，欺骗过$D$ 而$D$呢，则是不断提高自己的辨别能力，尝试分辨出真实图片和$G$产生的虚假图片 那么GAN作为整体的最优化问题该如何去表示？ 判别器$D$需要做的事情是判定x是来自数据集$Data$的概率，因此我们需要最大化$E_{x\sim p_{data}(x)}[logD(x)]$ 再考虑企图去欺骗$D$的$G$，有$E_{z\sim p_{z}(z)}[1-logD(G(z))]$，判别器希望这项最大化，而生成器$G$希望这项最小化 所以我们得到了GAN的目标函数 $min_Gmax_DV(D,G) ...

概率分布概率分布指的是变量X取值及其对应的概率 其包含所有取值和对应的概率 概率函数指的是用函数的形式来表示概率 $P_i=P(X=a_i)(i=1,2,3,4,5,6)$ 概率分布函数$F(x)=P(X \le x)$ 即概率分布函数是累积概率函数 分布参数$\hat\Theta$是一个概率分布的量化指数，它是样本总数的数值特征或一个统计模型，分布参数为一个或者多个，比如泊松分布只需要一个参数$\lambda$，正态分布则需要两个参数来决定均值和方差 KL散度KL散度又被称为相对熵 是一种衡量两个分布之间匹配程度的方法 $D_{KL}(P||Q)=\sum_{i=1}^NP(x_i)log(\frac{P(x_i)}{Q(x_i)})$ 其计算的是给定分布偏离真实分布的程度 在深度学习中通常用来评估模型输出的预测值分布与真值分布之间的差异 在公式中，我们用$P(x_i)$对$log(\frac{P(x_i)}{Q(x_i)})$加权 即概率越高的匹配区域的偏离系数更加重要 KL散度并不像范数一样是对称的，也就是其不是真正的度量值 即$D_{KL}(P||Q) \neq D_{KL}( ...

Problem给定四种颜色，去给一个长度为$n(n \le 10^5)$的环染色 有$m$种长度为$4$的序列不能在环中出现 通过旋转能够重合的环染色记做同一种染色法，求不同的染色方案数 Solution通过旋转能够产生n种置换，将置换按照$gcd(step,n)$分类 则答案为$\frac{\sum_{d|n}f(d)*phi(\frac{n}{d})}{n}$ 考虑计算$f(d)$，即统计长度为$d$的带$ban$位置的环染色方案数 我们建立一个$64*64$的矩阵$M$，表示长度为$3$的序列之间的转移情况 则$f(d)$为$M^d$的斜对角数字之和，即$blk=\sqrt{n}$ 我们用$BSGS$来处理$M^d=(M^{blk})^{\frac{d}{blk}}*M^{d % blk}$ 每次通过两个矩阵的乘积来计算$f(d)$即可 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566 ...

Problem给定一个长度为$n(1 \le n \le 3*10^5)$的序列，问有多少个子序列可以作为一个合法的森林输入数据 一个合法的森林输入数据可以是多组数据，每组第一个数字给出边的数量，然后给出若干条边，要求这些边连接后构成森林 Solution每组数据包含一个数字$m$表示边数，$2*m$个数字表示边 我们发现边可以分为两类，起始节点下标为奇数和起始节点下标为偶数 我们分两类用尺取法和动态树来维护有效数据位置 相邻的有效数据可以合并成为新的方案，我们记录有效数据始末端点，$dp$即可 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119 ...

Problem给定两张有$n(n \le 10^5)$个点的图，原图中至多$k(k \le 10^5)$条边 给定$m(m \le 10^5)$个操作，操作分三类： 1. 在第一张图中增加一条边 2. 在第二张图中增加一条边 3. 查询a点在第二张图中直接相连的点中，能够在第一张图中直接或者间接到达的数量 Solution我们用并查集维护第一张图，在对应的集合上记录在第二张图中出现但在第一张图中未连通的点对 当发生操作一时我们对集合进行启发式合并，将未连通点对数量少的集合并入未连通点对数量多的点对 发生点对连通时，我们修改对应两个点的答案，并将点对记录删去 总复杂度$O(Mlog(M))$，其中$M=2*(m+k)$ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <bits/stdc++.h>#define fi first#define se secondusing ...

Problem两个字符串$a$和$b$相似当且仅当两个串长度相等 且$a_i = a_j$时$b_i = b_j， a_i \neq a_j$时$b_i \neq b_j$ 给定一个字符串，多次询问其某个子串在原串中相似匹配的次数 Solution对于每个子串，我们根据每个字母第一次出现的位置对其标号 用标号来表示这个子串，那么如果标号序列的哈希值相同则子串相等 当子串起始位置不同时，我们会得到不同的标号，我们发现标号序列存在后缀递推关系 因此我们从后往前预处理这个标号，得到每个位置作为子串起点时标号对字母的映射 维护每个字符的位置哈希，对于两个子串的比较，只要比较子串区间内所有对应标号的字符的位置哈希是否相同即可 我们对所有后缀按照相似匹配的定义进行排序，那么包含与查询子串相似的串的后缀一定是连续的段 对于查询一个子串相似匹配的次数，我们只要在后缀排名中二分找到这样的相似段的左右端点即可 即两个后缀的最长匹配大于等于子串长度的最远位置，求最长匹配的过程可以二分加速 复杂度$O(knlognlogn)$，$k$为字符集大小 1234567891011121314151617181920 ...

Problem现在给定一个母串，询问多个子串 对于每个子串，求母串中最短的子串使得子串在其中出现至少$k$次 子串长度和 $\le 10^5$，母串长度 $\le 10^5$ Solution我们将询问串按照长度分组，对于每种分组，我们计算母串中对应长度的哈希值 将每个哈希值在分组中找对应的询问子串，把下标保存在对应询问上，用保存的下标计算答案 考虑子串长度和限制，复杂度均摊，最坏情况$O(n\sqrt{n})$ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <bits/stdc++.h>using namespace std;typedef unsigned long long ull;using PI = pair<ull, int>;const ull base = 131;const int N = 100000 + 10;ull p[N], Hash[N], h[N];vector<PI> v[N]; ...

Problem规定一个字符串和另一个字符串匹配的条件为首尾两个字符相同，且所有字符的出现次数相同 现在给定一个母串，询问多个子串，问子串在母串中的匹配次数 子串长度和 $\le 10^5$，母串长度 $\le 10^5$ Solution我们将询问串按照长度分组，对于每种分组，我们计算母串中对应长度的哈希值 然后统计对应组询问在该长度子串的哈希值中出现次数即可 我们对除串首尾做字符的集合哈希，串首尾特殊处理累加到哈希值上去 考虑子串长度和限制，复杂度均摊，最坏情况$O(n\sqrt{n})$ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <bits/stdc++.h>using namespace std;typedef unsigned long long ull;const ull base = 131;const int N = 100000 + 10;int n, T, L[N], ans[N];ull p[125 ...

Problem给定三个长度为$n(n \le 10^5)$的数组$A,B,C$，数字范围$1 \le m \le 10^5$ 求三个数组各选出一个数字使得最大的数字小于等于剩余两个数字相加的方案数 数据组数$T\le 100$，保证至多只有$20$组$n$大于$1000$ Solution考虑求补集，枚举最大的数字来自的集合，考虑求其大于剩余两个数字相加的方案 对于$n$大于$1000$的情况我们求剩余两个集合的权值数组卷积，求前缀和之后用最大数字集合查询即可 对于$n$小于等于$1000$的情况，我们暴力枚举剩余两个集合的数字组合，查询最大数字集合的权值数组前缀和 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610 ...

Problem构造一个长度为$n(n \le 10^{18})$数列，每个数字属于$[1,m]$$(m \le 2*10^5)$，要求每个偶数出现次数均为偶数次 Solution多重集排列问题，用指数型生成函数处理 $G(x)=(1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots)$ 本题的指数型生成函数为 $G(x)=(1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots)^{\frac{m+1}{2}}(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}+\dots)^{\frac{m}{2}}$ 根据泰勒公式 $e^x=(1+\frac{x^1}{1!}+\frac{x^2}{2}+\frac{x^3}{3!}+\dots)$ $e^{-x}=(1-\frac{x^1}{1!}+\frac{x^2}{2!}-\frac{x^3}{3!}+\dots)$ 得$G(x)=(e^x)^{\frac{m+1}{2}}(\frac{e^x+e^ ...

Problem求每一种旋转串的最长回文子串，串长小于等于$10^6$ Solution倍长字符串，转化为区间回文子串，$manacher$预处理倍长后的回文串 对于查询区间$[L,R]$最长回文子串 我们可以二分答案，检验区间$[L+x-1,R-x+1]$中是否存在长度大于$x$的回文中心即可 $ST$表预处理$r$数组的区间最大值，复杂度$O(nlogn)$ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <bits/stdc++.h>using namespace std;const int N = 1000000 + 10;int n, f[N << 1], r[N << 1];char s[N], c[N << 1];int dp[N << 1][21], lg2[N << 1];void Init(int n) { ...

Problem给定$F_1=1$，$F_n=a*F_{n-1}+1$ 有一个有$n$个元素的多重集合$S$ $value(s)=F_{\sum{s_i}}$ 定义$ans(k)=\sum_{s \subset S \ and \ |s|=k}value(s)$ 求$ans(1),ans(2),……,ans(n) \ mod \ 100003$ $n \le 10^5，2 \le a \le 1000，1 \le s_i \le 1e9$ Solution$F_n=\frac{a^n-1}{a-1}$ 对于给定的$k$，我们计算出不同方案下的$a^{sum}$之和，$sum$由$k$个$s$相加得到，减去方案数$C_n^k$，然后除以$(a-1)$即可 前者为母函数$(x+a^{s_1})(x+a^{s_2})……(x+a^{s_n})$的$x^{n-k}$前的系数 所以我们计算这个母函数前的系数，$FFT$计算即可 我们可以通过分治区间优化多次等长数组的卷积，复杂度$O(nlognlogn)$ 此题精度不足需要用$long \ double$ 123456789101112131415 ...

Problem给定长度为$n(n \le 10^5)$的字符串求区间本质不同的子串数量 Solution我们用线段树维护每个节点为左端点的，到r为右端点为止的本质不同子串数量 每个相同的子串只将值保留在最后一次出现的左端点 当一个字符被新增到原串的末尾时，会在某些左端点增加新的本质不同的串 同时部分子串最后一次出现的左端点将移动到串尾 我们对$[1,pos]$前缀的所有左端点答案$+1$，考虑减去重复的串 对于串$[v,r]$，如果出现在$[l,r-v+l]$，那么两者在后缀自动机$fail$树上的$lca$就是两者的重复串集 在每个串位置记录最后一次出现的位置$ps$，我们从根到当前叶节点按照长度处理重复串，更新对应$right$集新的位置 我们发现重复串和$LCT$的$access$操作一致，只会发生$O(logn)$段$ps$的变动 我们通过$LCT$的$access$操作保存在$fail$链上上一次串的出现位置，提取变动段，用线段树维护即可 均摊复杂度$O(nlog^2n)$ 123456789101112131415161718192021222324252627282930 ...

Problem我们定义一个字符串$a$比一个字符串$b$酷 当$b$在$a$中作为子串出现至少两次 现在给定一个字符串$S$，要求找到最长的子串序列$S_1$,$S_2$,$S_3$…… 要求对于任意$i$，$S_{i+1}$比$S_i$酷 Solution我们发现，如果我们要找一个字符串$b$，使得字符串$a$作为子串在其中出现至少两次 即$a$的$endpos$集合在$[pos[b]-len[b]+len[a],pos[b]]$中出现至少两次 最短的$b$串一定是以$a$为前缀且以$a$为后缀的，可以得出结论$a$为$b$的$border$ 那么只要$a$的$endpos$集合在$[pos[b]-len[b]+len[a],pos[b]-1]$中出现即可 用线段树维护$endpos$，将$endpos$按$fail$链进行线段树合并得到每个节点的$endpos$集合，在对应集合查询区间$[pos[b]-len[b]+len[a],pos[b]-1]$是否有值即可 我们需要在$fail$链节点上保存最长子序列的最后一位，每次扩展时在这一位的线段树上查询 123456789101112 ...

Problem给定a,b,c,d四条边的取值范围，求能构成的合法四边形数量 $a,b,c \le 10^5,d \le 10^3$ Solution考虑求答案的补集，即不合法四边形数量 假定最长边为$a$，则我们需要对于每个取值统计$b+c+d$不超过$a$的数量 因为是连续取值范围，我们可以用差分数组维护$b+c+d$ 首先对于每个$b$，产生区间值$[b+l_c,b+r_c]$，差分数组处理得到$b+c$ 此时$b+c$是离散的，但是$d$是连续的，所以可以考虑枚举$b+c$，对区间$[b+c+l_d,b+c+r_d]$产生贡献，差分数组处理 二次前缀和之后得到$b+c+d$的权值数组的前缀和，$O(n)$枚举$a$，$O(1)$查询贡献 因为要不合法是$b+c+d<=a$，所以在差分过程中，只要保留$a$值域范围的权值数组 枚举其余边作为最长边，按照上述方法计算，从总方案中减去即可 总复杂度$O(n)$ 12345678910111213141516171819202122232425262728293031323334353637383940#include <bi ...

Problem一个机器人在一张n个点m条边的有向无环图上行走，每天等概率地在原地不动或者移动到相邻的位置 每天消耗的能量为已经过去的天数，问从起点抵达终点最小耗能 $2 \le n \le 10^5,1 \le m \le 2 \ast 10^5$ Solution因为从起点出发到终点转移是等概率的，所以考虑按照从终点到起点的拓扑序转移 记$g_u$为$u$点到终点的期望步数，$f_u$为$u$点到终点的期望代价 考虑在路径序列前端多加一个点，其之后每一天的代价都会增加1 那么其和有向图上的后继节点关系有： $g_u=(\sum(g_v+1)+g_u+1)/(sz_u+1)$ $f_u=(\sum(f_v+g_v+1)+f_u+g_u+1)/(sz_u+1)$ 按照从终点到起点拓扑序转移计算即可 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <bits/stdc++.h>using namespace std;const in ...

Problem定义函数$f_n(k)=\sum_{l_1=1}^n\sum_{l_2=1}^n\dots\sum_{l_k=1}^n(gcd(l_1,l_2,\dots,l_k))^2$ 求$S=\sum_{i=2}^kf_n(i)$ 答案对$10^9+7$取模 $1 \le n \le 10^9,2 \le k \le 10^{10^5}$ Solution$f_n(k)=\sum_{g=1}^ng^2\sum_{l_1=1}^n\sum_{l_2=1}^n\dots\sum_{l_k=1}^n[gcd(l_1,l_2,\dots,l_k)==g]$ 设$F(x)=\sum_{l_1=1}^n\sum_{l_2=1}^n\dots\sum_{l_k=1}^n[x \mid gcd(l_1,l_2,\dots,l_k)]$ $g(x)=\sum_{l_1=1}^n\sum_{l_2=1}^n\dots\sum_{l_k=1}^n[gcd(l_1,l_2,\dots,l_k)==x]$ $F(x)=\sum_{x \mid d}g(d)=\lfloor\frac{n}{x}\rfloor ...

Problem给定一个排列，对于每个位置$i$，求出除这个位置之外有多少个位置$j$，如果删去$j$位置上的数会使得包含位置$i$的$LIS$变短 Solution我们对排列求一遍$LIS$，在过程中对每个长度的$LIS$保存结束位置，则其位置上数字的大小单调递减 对于位置$i$来说，若其$LIS$长度为$len$，一定是从$LIS$长度为$len-1$且数值小于$a_i$的位置转移过来的 我们将$LIS$转移对应的两端点连边，构成一张拓扑图，那么求$i$位置前面有哪些数字删除会导致包含位置$i$的$LIS$变短，就等价于求这张拓扑图的支配树上$i$节点的深度 我们正反做两遍$LIS$，将对应支配树深度相加就是答案 支配树的构造可以在$LIS$的同时完成，所有长度为$len-1$的小于$a_i$的点$LCA$向$i$点连边即可 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include & ...