如果大家不知道调整法是什么，可以去复习我非常民科的集训队论文。

CTS的数据表明，很多网友不太知道调整法咋用。这里分享一点诀窍。

首先，调整法主要用于限制较松散的题目，要找到性质中松散/容易满足的那股劲。如果题目中有些限制难以满足，你就用人类智慧把它们先满足了，剩下的部分交给调整。不要让调整去摁做很严格的限制。

其次，要找到容易变动且和目标相符的估值。这一部分有时是简单的（比如：不满足的条件个数），有时需要用力对着组合结构构造一下（例如：将哈密顿路转化成一些较容易满足的条件）。一般来说，对具体问题需要用具体的估值，不要都转到某个NPC硬做。

一个简单的例题是今年WC T2。做法很简单。容易看出，最大的集合的限制可能很紧，其他集合的限制都很松散。我们首先规定最大的集合中元素放置在哪些位置（例如：放两个空一个，放两个空一格，以此类推）。之后可以调整，调整的内容为不满足的对子数。每次找一个有矛盾的位置，随机选取一个别的和它同在/同不在最大集合的位置，看看换完后矛盾会不会变少。这样一下子就过了，很快啊。

大家学会了吗？

另一道例题：

将 1 ~ nm 放置在 n * m 的方格表中，使得相邻位置互素。

考虑这样一种哈希方式。对于一棵以 $a$ 为根的子树，假设儿子是 $v_1, v_2, \cdots, v_k$，定义子树的哈希 $h(a)=1+\sum_{1\le i\le k} f(h(v_i))$。其中$h(v_i)$ 是 $v_i$ 对应子树的哈希，$f$ 为一个待定函数。

可以证明：如果 $f$ 为随机函数，这样的哈希在自然溢出下的期望冲突数不超过 $O(n^2/2^w)$。只需考虑最深的一对冲突点即可。

上述哈希最大的优势是好写。如果需要换根，第二次 dp 时只需把子树哈希减掉即可。

实践中，我们并不能取一个真正的随机函数当 $f$。但事实上，没有特殊性质的 $f$ 几乎都卡不掉；因为随便找个 $f$ 大概率很随机。

有一些反例：如果 $f$ 取多项式，可能因为一直保持 $2^k$ 同余关系而白给。但是经过我的实验，似乎只要扰动一下改掉这个性质即可。例如下述函数：

ll h(ll x) {
    return x * x * x * 1237123 + 19260817;
}
ll f(ll x) {
    ll cur = h(x & ((1 << 31) - 1)) + h(x >> 31);
    return cur;
}

我认为应当是卡不掉的，如果有网友能卡掉欢迎找我。

今天学了一下 Lovasz Local Lemma 的构造性证明，感觉算法流程和调整法很像。

这里毛估估写一点过程。以下内容是从俺的博客 https://www.cnblogs.com/cauchysheep/p/16587302.html 直接抄过来的。

LLL 证明

Lovasz-Local lemma: 有一堆事件，每个事件有标号 $X_i$。如果对任意 $i$, 记 $V_i$ 满足：删掉 $V_i$ 之后 $i$ 与剩余事件完全独立，且 $P(A_i) \le X_i \prod_{j\in V_i} (1-x_j)$, 则有至少 $\prod (1-X_i)$ 的概率所有事件均不发生。

证明：对每个集合 $A$ 和 $a\notin A$, 我们证明 $A\cup \{a\}$ 均不发生的概率至少为 $A$ 均不发生的概率乘以 $(1-x_a)$。对 $|A|$ 归纳。注意到 $A\cup \{a\}$ 均不发生的概率为 $A$ 不发生的概率减去 $A$ 不发生且 $a$ 发生的概率，后者不超过 $A \backslash V_a$ 均不发生且 $a$ 发生的概率。而 $A \backslash V_a$ 与 $a$ 独立，两概率可以直接相乘。 又由归纳假设 $A \backslash V_a$ 均不发生的概率除以 $A$ 均不发生的概率不超过 $1/\prod_{j\in V_a} (1-x_j)$，化简得证。

$k-SAT$ 构造性证明

考虑构造每个 Clause 与不超过 $2^{k-2}$ 个其余 Clause 相交的 $k$-SAT 的解。

考察一个操作 $f(A)$，效果为：经过一些处理，使得 Clause $A$ 从不满足变成满足，原先满足的仍然满足。 具体执行定义如下：首先我们重新随机 sample $A$ 涉及到的变量。而后当存在 $A$ 有交 (含 $A$ 自己) 的 Clause $B$ 未满足，我们递归调用 $f(B)$。

$f$ 的正确性显然成立，我们希望证明 $f$ 的执行时间。事实上，我们只需要说明：$f$ 的调用时间 $\ge 2\log m$ 的概率不超过 $O(1/m^2)$ （于是，可以在某次超过 $2\log m$次调用后完全从头再来）。考虑固定一棵（给定根）的调用树，大小为 $t$。我们声称：这棵调用树出现的概率不超过 $1/2^{kt}$。这是因为每当树上节点用过一些变量，这些变量会立即被sample成新的值，所以树上节点的事件是完全独立的。而大小为 $t$ 的调用树个数有界：因为每次只有最多 $2^{k-2}+1$ 个邻点可供选择；为了回溯，也只需记录这个点是不是当前子树最后一个点即可。因此方法数不超过 $(2(2^{k-2}+1))^t$。

于是，大概率从外部 $m$ 次 $f$ 的调用后，每次调用的时间均不超过 $m\log m$。于是我们可以在不超过 $O(m^2\log m)$ 的时间给出构造。

一般的 LLL 构造性证明

考虑如下设定: 每个事件与 $\Omega$ 中若干个变量相关，$\Omega$ 中的变量两两独立。

我们考虑如下算法：初始给 $\Omega$ 中的变量随机赋值。当有事件发生时，我们将该事件涉及的变量重新 sample，一直执行知道所有事件均不发生。

我们证明：事件 $i$ 被重新 sample 的期望次数不超过 $x_i/(1-x_i)$。证明如下：记 $a_i$ 为事件 $i$ 重新 sample 的期望次数。我们将事件 $i$ 的每次 sample charge 到最近一次涉及到其中变量的修改上。那么容易发现， $a_i\le P_i (1+a_i+\sum_{j\in V_i}a_j)$. 化简后只需证明 $1\ge \prod (1-x_j) + \sum_j x_j \sum_{k\ne j} (1-x_k)$，显然得证。

最近和朋友聊到多项式科技，朋友指出市面上的博客很多，但不少很繁琐、很不直观

那我来推一个憨憨博客啊！虽然东西不多，但大部分时候好像够用了

~在这个博客子集里的题就可以不出了；不在的题会被更新进去的~

https://www.cnblogs.com/cauchysheep/p/15161252.html

又到了UOJ换届环节！

过去的一年中， 由zhouyuyang, AprilGrimoire和我担任UOJ管理员。nike0good 哥哥和前管理员们为我们提供了许多帮助w

这一年里，UOJ共举办了Goodbye Jihai, UOJ Round #19，UOJ NOI Round #4 这三场比赛（以及以UOJ为平台的美团杯）。许多前辈及同侪为它们付出了大量心血。

UOJ完全用爱发电。这决定了它的本质。

UOJ的比赛题目往往经过精心准备，博客区更是许多人发布算法研究的首选。用心出一道好题、钻研引入新的理论，功利地来看对OI成绩没什么用。它们只是出于纯粹的热情，而恰巧适合UOJ这样纯粹的地方。

我常常想起我作为用户第一次参加UOJ Round的样子。彼时我什么都不会，但很热爱OI。14岁的我并不会考虑收益和前程，只是单纯地喜欢编程和算法、享受思考和创造的快乐。那次我想题想了一整晚，第二天凌晨就起床看结果和rating变化。这种状态（不包括啥也不会）或许是许多用户的缩影。

这一年当管理员时，我总想着：我不能辜负这个纯粹的OJ，更不能辜负有着纯粹热忱的人们。所幸在各位的帮助下做得不算太糟。

我们几个将要卸下管理员的大锅了ww 感谢周队长一次次力挽狂澜，感谢好风哥哥有趣的题目和题面；也希望未来的某一天，线性NPC会像多项式技巧一样为人熟知（雾

无论如何，总会有可爱的人们热爱着算法竞赛，也总会有可爱的人们愿意将这个OJ的精神传承下去。

下一届的管理员是：

mayaohua, rushcheyo, skip2004

祝泥萌一切顺利！

昨天UNR考完之后，有许多小朋友问我标程怎么写的owo

那我挂一下好了

//Awwawa! Dis cold yis ratten buy tEMMIE!
#include <bits/stdc++.h>
#define ll long long
#define maxn 100005 /*rem*/
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

using namespace std;
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
int out[maxn], in[maxn];
vector<pi> eg;
mt19937 x;
int gt(int a, int b) {
    if (a == b) return 1;
    if (!a) return 0;
    return gt(out[a], b);
}
int main() {
    for (int t = 1/*1*/; t <= 10; t++) {
        char nm[30];
        sprintf(nm, "hamil%d.in", t);
        ifstream rd(nm);
        sprintf(nm, "hamil%d.ans", t);
        cout << "WORK" << t << endl;
        ofstream ot(nm);
        int n, m;
        rd >> n >> m;
        eg.clear();
        for (int i = 1; i <= m; i++) {
            int u, v;
            rd >> u >> v;
            eg.pb(mp(u, v));
        }
        shuffle(eg.begin(), eg.end(), x);
        while (1) {
            int tot = 0, cnt = 0;
            memset(out, 0, sizeof(out));
            memset(in, 0, sizeof(in));
            while (1) {
                int fl = 0;
                shuffle(eg.begin(), eg.end(), x);
                for (auto v : eg) {
                    if (in[v.se] && out[v.fi]) continue;
                    if (gt(v.se, v.fi)) continue;
                    if (in[v.se] || out[v.fi]) 
                        if (x() & 1) continue;
                    if (!in[v.se] && !out[v.fi])
                        tot++, fl = 1;
                    if (in[v.se]) {
                        out[in[v.se]] = 0;
                        in[v.se] = 0;
                    }
                    if (out[v.fi]) {
                        in[out[v.fi]] = 0;
                        out[v.fi] = 0;
                    }
                    in[v.se] = v.fi;
                    out[v.fi] = v.se;
                }
                if (tot == n - 1) break;
                if (fl) cnt = 0;
                else {
                    cnt++;
                    if (cnt >= 3000000) break;
                }
                if (x() % 20 == 0)cout << tot << endl;
            }
            if (tot == n - 1) break;
            cout << "AGAIN" << endl;
        }
        for (int i = 1; i <= n; i++) 
            if (!in[i]) {
                int pl = i;
                while (pl)
                    ot << pl << ' ', 
                    pl = out[pl];
                break;
            } 
        ot << endl;
    }
    return 0;
}

这是当时的标程w 由于我很懒，什么优化也没加

今天空闲时拷了个LCT的板子，又封装了一下，现在可以在4s跑完UNR4 D2T3

代码如下

//Awwawa! Dis cold yis ratten buy tEMMIE!
#include <bits/stdc++.h>
/*这是一份UNR4 D2T3示例代码 只需要几秒就能AC该题
hamil::work是封装好的函数，不需初始化可直接调用
其参数为: int n, vector<pair<int, int> > edges, int mx_ch = -1
其中n为有向图点数（从1开始标号），edges为有向边的集合（edges中元素pair<u, v>表示从u到v有向边），mx_ch为最大调整次数。如果不设初值，默认为(n+100)*(n+50)
这个函数时间复杂度不超过mx_ch * log(n) 如果能找到哈密顿链，往往远快于这个上界
如果有哈密顿链，函数有较大概率返回一条。链经过的节点按照经过的顺序储存在返回的vector<int> 中。
如果函数未能找到，会返回空的vector<int>。这时可以调大mx_ch阈值，或者多试几次w
欢迎大家喂各种图调戏它x
*/

using namespace std;
namespace hamil {
    template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
    template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
    #define vi vector<int>
    #define pb push_back
    #define mp make_pair
    #define pi pair<int, int>
    #define fi first
    #define se second
    #define ll long long
    namespace LCT {
        vector<vi> ch;
        vi fa, rev;
        void init(int n) {
            ch.resize(n + 1);
            fa.resize(n + 1);
            rev.resize(n + 1);
            for (int i = 0; i <= n; i++)
                ch[i].resize(2), 
                ch[i][0] = ch[i][1] = fa[i] = rev[i] = 0;
        }
        bool isr(int a)
        {
            return !(ch[fa[a]][0] == a || ch[fa[a]][1] == a);
        } 
        void pushdown(int a)
        {
            if(rev[a])
            {
                rev[ch[a][0]] ^= 1, rev[ch[a][1]] ^= 1;
                swap(ch[a][0], ch[a][1]);
                rev[a] = 0;
            }
        }
        void push(int a)
        {
            if(!isr(a)) push(fa[a]);
            pushdown(a); 
        }
        void rotate(int a)
        {
            int f = fa[a], gf = fa[f];
            int tp = ch[f][1] == a;
            int son = ch[a][tp ^ 1];
            if(!isr(f)) 
                ch[gf][ch[gf][1] == f] = a;    
            fa[a] = gf;

            ch[f][tp] = son;
            if(son) fa[son] = f;

            ch[a][tp ^ 1] = f, fa[f] = a;
        }
        void splay(int a)
        {
            push(a);
            while(!isr(a))
            {
                int f = fa[a], gf = fa[f];
                if(isr(f)) rotate(a);
                else
                {
                    int t1 = ch[gf][1] == f, t2 = ch[f][1] == a;
                    if(t1 == t2) rotate(f), rotate(a);
                    else rotate(a), rotate(a);    
                } 
            } 
        }
        void access(int a)
        {
            int pr = a;
            splay(a);
            ch[a][1] = 0;
            while(1)
            {
                if(!fa[a]) break; 
                int u = fa[a];
                splay(u);
                ch[u][1] = a;
                a = u;
            }
            splay(pr);
        }
        void makeroot(int a)
        {
            access(a);
            rev[a] ^= 1;
        }
        void link(int a, int b)
        {
            makeroot(a);
            fa[a] = b;
        }
        void cut(int a, int b)
        {
            makeroot(a);
            access(b);
            fa[a] = 0, ch[b][0] = 0;
        }
        int fdr(int a)
        {
            access(a);
            while(1)
            {
                pushdown(a);
                if (ch[a][0]) a = ch[a][0];
                else {
                    splay(a);
                    return a;
                }
            }
        }
    }
    vi out, in;
    vi work(int n, vector<pi> eg, ll mx_ch = -1) { // mx_ch : 最大调整次数  如果不设初值，默认为(n + 100) * (n + 50) 
        // 如果存在，有较大概率返回一条路径 
        // 如果失败 返回0 
        out.resize(n + 1), in.resize(n + 1);
        LCT::init(n);
        for (int i = 0; i <= n; i++) in[i] = out[i] = 0;
        if (mx_ch == -1) mx_ch = 1ll * (n + 100) * (n + 50); //时间上限 
        vector<vi> from(n + 1), to(n + 1);
        for (auto v : eg)
            from[v.fi].pb(v.se), 
            to[v.se].pb(v.fi);
        unordered_set<int> canin, canout;
        for (int i = 1; i <= n; i++)
            canin.insert(i), 
            canout.insert(i); 
        mt19937 x(time(0));
        int tot = 0;
        while (mx_ch >= 0) {
        //    cout << tot << ' ' << mx_ch << endl;
            vector<pi> eg;
            for (auto v : canout)
                for (auto s : from[v])
                    if (in[s] == 0) {
                        assert(canin.count(s));
                        continue;
                    }
                    else eg.pb(mp(v, s));
            for (auto v : canin)
                for (auto s : to[v])
                    eg.pb(mp(s, v));
            shuffle(eg.begin(), eg.end(), x);
            if (eg.size() == 0) break;
            for (auto v : eg) {
                mx_ch--;
                if (in[v.se] && out[v.fi]) continue;
                if (LCT::fdr(v.fi) == LCT::fdr(v.se)) continue;
                if (in[v.se] || out[v.fi]) 
                    if (x() & 1) continue;
                if (!in[v.se] && !out[v.fi]) 
                    tot++;
                if (in[v.se]) {
                    LCT::cut(in[v.se], v.se);
                    canin.insert(v.se);
                    canout.insert(in[v.se]);
                    out[in[v.se]] = 0;
                    in[v.se] = 0;
                }
                if (out[v.fi]) {
                    LCT::cut(v.fi, out[v.fi]);
                    canin.insert(out[v.fi]);
                    canout.insert(v.fi);
                    in[out[v.fi]] = 0;
                    out[v.fi] = 0;
                }
                LCT::link(v.fi, v.se);
                canin.erase(v.se);
                canout.erase(v.fi);
                in[v.se] = v.fi;
                out[v.fi] = v.se;
            }
            if (tot == n - 1) {
                vi cur;
                for (int i = 1; i <= n; i++) 
                    if (!in[i]) {
                        int pl = i;
                        while (pl) {
                            cur.pb(pl), 
                            pl = out[pl];
                        }
                        break;
                    } 
                return cur;
            }
        }
        //fail to find a path
        return vi();
    }
}
int main() {
    for (int t = 1; t <= 10; t++) {
        char nm[30];
        sprintf(nm, "hamil%d.in", t);
        ifstream rd(nm);
        sprintf(nm, "hamil%d.out", t);
        cout << "WORK" << t << endl;
        ofstream ot(nm);
        int n, m;
        rd >> n >> m;
        vector<pi> eg;
        for (int i = 1; i <= m; i++) {
            int u, v;
            rd >> u >> v;
            eg.pb(mp(u, v));
        }
        l1: 
        vi ed = hamil::work(n, eg);
        if (!ed.size()) goto l1;
        ot << ed.size() << endl;
        for (auto v : ed)
            ot << v << ' ';
        ot << endl;
    }
    return 0;
}

一些附加说明：

如果给定起点终点，只需新建两个点$U,V$ ； 然后 $U$ 到起点连一条边，终点到 $V$ 连一条边

如果要求哈密顿圈，可以枚举一条边，转化成给定起点终点情形。

如果是无向图，只需正反边各加一遍即可。

这次的题目背景大部分是vfleaking写的。

出题人 01,02,03 只是主人公的名字，和真实出题人没有任何的关系。

同构判定鸭

from Picks，标程 by Aprilgrimoire，数据、题解 by zhouyuyang 和 vfleaking。

算法0

这题好不可做啊!

交个简单的代码跑路吧:

print 'Same'

期望得分:$0$

算法1

我会爆搜！

在wc上学了高超的搜索技巧感觉充满了力量！

期望得分:$15 \sim 35$。

算法2

对于 DAG 的情况，显然若存在坏串则坏串长度不超过 $\max\{n_1,n_2\}$。

适当选取一种对字符串集合的哈希函数之后，我们就可以对于每一个结点 $v$ 和每一个 $k$，递推计算出从 $v$ 出发可匹配的且长度为 $k$ 的字符串集合的哈希值。然后就容易根据哈希值计算出坏串的最短长度了。

输出字典序最小的最短坏串可以通过按位贪心来实现。

时间复杂度$O(n^2m)$或$O(nm)$。

期望得分:$20 \sim 40$。

算法3

DAG 的情况启发我们去思考：如果存在坏串，那么最短的坏串长度是否比较短呢？

注意如果不是比较短的话，题目也不会让我们输出方案的。不然岂不是出题人亲自邀请大家炸测评机？

实际上我们确实能证出如下结论：

结论：如果存在坏串，则最短的坏串长度不超过 $n_1+n_2$。

证明是这样的。首先我们可以把 $G_1, G_2$ 拼成一个$n_1+n_2$个点的大图 $G$（$G_2$ 的结点编号都加上 $n_1$）。给定一个字符串 $s = s_1s_2 \cdots s_L$，想统计 $s$ 在 $G_1$ 和 $G_2$ 中的出现次数之差，我们可以用 $f_{k,v}$ 表示 $G$ 中长度为 $k$ 且与 $s_1 \cdots s_k$ 匹配且最后一个结点是 $v$ 的路径条数，然后递推求出 $f$。最后如果 $$ \sum_{1 \le v \le n_1} f_{L,v} - \sum_{n_1 < v \le n_1 + n_2} f_{L,v} = 0 $$ 则出现次数相等，否则不相等。

仔细分析递推式可以发现这是个线性的递推式，且相同的 $k$ 的转移只跟 $s_k$ 和 $v$ 有关。那么我们可以把转移写成 $26$ 个矩阵 $M_a, M_b, \cdots, M_z$。若把初始的 $f_{0, v}$ 写成一个行向量 $u_I^{\top}$（一个元素均为 $1$ 的行向量），那么最终 $f_{L, v}$ 就是 $u_I^{\top}M_{s_1}M_{s_2} \cdots M_{s_L}$。令 $u_O$ 为前 $n_1$ 个元素都是 $1$，其他元素都为 $-1$ 的向量，则 $s$ 在 $G_1, G_2$ 中出现次数相等当且仅当 $u_I^{\top}M_{s_1}M_{s_2} \cdots M_{s_L} u_O = 0$。

现在我们令 $V_K$ 为所有 $L \le K$ 的 $s$ 对应的行向量 $u_I^{\top}M_{s_1}M_{s_2} \cdots M_{s_L}$ 组成的集合。如果 $G_1, G_2$ 不等价，就说明存在一个 $K$ 使得 $V_K$ 内有元素 $u^{\top}$ 满足 $u^{\top} u_O \ne 0$。

下面要用到一点点向量空间的概念。对于一个行向量集合 $V$，我们用 $\mathrm{span}(V)$ 表示所有 $V$ 中元素的线性组合组成的集合，也即 $V_K$ 张成的向量空间。数学表达式为： $$ \mathrm{span}(V) = \left\{ \sum_{i=1}^{m} \lambda_i u_i^{\top} : m \ge 1, u_1^{\top}, \cdots, u_m^{\top} \in V, \lambda_1, \cdots, \lambda_m \in \mathbb{R} \right\} $$ 比如共线的向量张成的是一条线，共面的向量张成的是一个平面。对于每个 $V_K$，我们令 $U_K = \mathrm{span}(V_K)$。容易看出，$V_K$ 内有元素 $u^{\top}$ 满足 $u^{\top} u_O \ne 0$ 当且仅当 $U_K$ 内有元素 $u^{\top}$ 满足 $u^{\top} u_O \ne 0$。

对于一个行向量集合 $V$ 和一个矩阵 $M$，我们用 $VM$ 表示 $\{ u^{\top}M : u \in V \}$。那么 $V_K$ 是可以递推的：$V_K = V_{K-1} \cup \left(\bigcup_{c \in \{\texttt{a}, \cdots, \texttt{z}\}} (V_{K-1} M_c)\right)$。因此 $\mathrm{span}(V_K)$ 也是可以递推的： $$ U_K = \mathrm{span}\left(U_{K-1} \cup \left(\bigcup_{c \in \{\texttt{a}, \cdots, \texttt{z}\}} (U_{K-1}M_c)\right) \right) $$

根据定义，$U_1 \subseteq U_2 \subseteq U_3 \subseteq \cdots$。那么 $U_K$ 是否会随着 $K$ 的增大而一直变大呢？根据向量空间的性质和上面的 $U_K$ 的递推式，答案是不会的。

这里要用到向量空间的维数的概念。直观上一个向量空间 $U$ 的维数就是你直观所以为的那个维数（线是 $1$，面是 $2$）。数学上，维数的一个等价定义是你在 $U$ 中最大的线性无关组的大小。其中线性无关组是指一组向量 $u_1, \dots, u_d$，满足性质：任意线性组合 $\sum_{i=1}^{d} \lambda_i u_i$ 等于 $0$ 当且仅当 $\lambda_i$ 全为 $0$。对于两个有限维的向量空间 $U \subseteq U'$，可以证明要么 $U$ 的维数比 $U'$ 大，要么 $U = U'$。这是因为 $U \ne U'$ 的时候我们可以取一个 $u' \in U' \setminus U$ 加到 $U$ 的最大线性无关组里，就得到一个 $U'$ 的线性无关组了。

显然，$U_K$ 的维数不会超过 $n_1 + n_2$，因为这些向量就 $n_1+n_2$ 个坐标嘛。因此，$U_K$ 的维数先会随着 $K$ 严格单调递增，然后到某个 $K = K^{\ast}$ 时 $U_{K^{\ast}} = U_{K^{\ast} + 1}$，且这里 $K^{\ast} \le n_1 + n_2$。根据递推式我们可以看出相同的 $U_{K-1}$ 一定推出的是相同的 $U_K$。所以一旦 $U_{K^{\ast}} = U_{K^{\ast} + 1}$，则 $U_{K^{\ast}} = U_{K^{\ast} + 1} = U_{K^{\ast} + 2} = \cdots$ 大家都相等了。这就说明如果存在 $U_K$ 内有元素 $u^{\top}$ 满足 $u^{\top} u_O \ne 0$，则最小的 $K \le n_1 + n_2$，就证好啦。

细节不太清楚的可以去找本自己看得懂的线性代数教材瞧瞧向量空间的具体定义。不知道是否有不依赖于线性代数的证明，如果有的话欢迎分享下咯。

回到算法上来。现在我们知道了，如果对于所有长度不超过 $n_1+n_2+1$ 的序列均合法则可以对于所有串均合法。

因此可以通过哈希确定坏串最短长度后即可按位确定答案。

时间复杂度$O(n^2m)$或$O(nm)$。

期望得分:$70 \sim 100$。

我和算法3一样为什么我挂掉了

你的哈希函数 $H$ 需要满足：$H(\texttt{"ab"}) \neq H(\texttt{"ba"})$ 且 $H(\texttt{"bc"})+H(\texttt{"de"}) \neq H(\texttt{"be"})+H(\texttt{"cd"})$，否则你的算法就会是错的。

Aprilgrimoire 在验题的时候加了一个extest把这种情况干掉了

一些正确的哈希姿势

例如从后往前数，位于不同位置的相同字符有着不同的哈希值。字符串的哈希值就是字符哈希值的乘积，多串的哈希值是每个串哈希值的和。

另一种方法是把字符串的哈希值设为 $\mathrm{b}^{\sum_{i} s_i a^i}$，然后多串的哈希值还是每个串哈希值的和。

还有一种方法是把哈希值设成矩阵的形式，例如每个字符都对应一个 $3 \times 3$ 的随机小矩阵。

OIer 当然可以使用反正法说明哈希的正确率：“反正哈希正确率很高！” 但我们这里还是分析一下第一种方法。

第一种方法即事先随机出 $x_{i,c}$ 共 $(n_1+n_2) \times 26$ 个随机数，然后每个字符串的哈希值即 $H(s_1 \cdots s_L) = \prod_{i=1}^{L} x_{L-i+1,s_i}$。我们递推求出的是对于每个 $L \le n_1+n_2$，两个图各自对应的哈希值：$f_1(L) = \sum_{s_1 \cdots s_L} g_1(s) H(s)$ 和 $f_2(L) = \sum_{s_1 \cdots s_L} g_2(s) H(s)$。这里我们用 $g_1(s), g_2(s)$ 表示 $s$ 在 $G_1, G_2$ 中的出现次数。

现在我们将 $x_{i,c}$ 看成变量而非随机数，则 $f_1(L, x), f_2(L, x)$ 都可以看作是 $x_{i,c}$ 的 $L$ 次多项式。不存在长度为 $L$ 的坏串，等价于 $f_1(L, x), f_2(L, x)$ 作为两个关于 $x$ 的多项式时是相等的（也即多项式系数相等，也即这两个函数在带入任意一组 $x$ 的时候都相等）。

因此就是要看看两个多项式不相等，但随机一组 $x$ 带入进去之后导致 $f_1(L,x) = f_2(L, x)$ 的概率是多少。我们可以用 Schwartz-Zippel 引理来说明：对于某个域 $F$ 上的不超过 $d$ 次的多项式 $f(x_1, \dots, x_m)$，如果每个 $x_1, \cdots, x_m$ 都是从 $F$ 中的一个大小为 $S$ 的子集中独立地均匀随机选取的，那么 $f(x) = 0$ 的概率不超过 $\frac{d}{S}$。

对于本题，大家当然会在模一个素数 $p$ 的情况下计算。令 $F = F_p, f(x) = f_1(L, x) - f_2(L, x), d = n_1 + n_2, S = p$，就可以知道失败概率不超过 $(n_1+n_2)/p$。

但这个失败概率仅仅是做一次“用哈希值相等来判断两个字符串集合相等”的失败概率。算法中我们要枚举长度，还要按位贪心，所以大概要做 $O((n_1 + n_2)\Sigma)$ 次，其中 $\Sigma$ 是字符集大小。使用 union bound 可知总的失败概率是 $O((n_1+n_2)^2 \Sigma / p)$。取个大点的 $p$ 就可以高枕无忧啦。

对这个问题有兴趣的同学可以搜一下 Polynomial Identity Testing (PIT) 学习一波。

Bonus

如果要求严格字典序最小，能否证明在存在严格字典序最小的情况下，答案串长度是否有限？若有限，答案串长度是否存在上界？

己酸集合

from zhouyuyang，数据、标程、题解 by zhouyuyang。

把题目名字的拼音拿出来，JiSuanJiHe，这提示了这是一道计(Ji)算(Suan)几(Ji)何(He)题。

算法0

我会暴力！

每次询问暴力计算答案!

期望得分$15$。

如果利用算法$2$中的方程判断，可能可以通过Subtask $3$。

算法1

我会KD-Tree!

随机数据KD-Tree的复杂度看上去很真实。

极端情况下会被卡到$O(nQ)$，但是跑跑subtask $2$应该没啥问题。

事实证明KDT是一个死掉的算法。

期望得分:$45$。

算法2

我会写方程!

写出圆方程$x_i^2+(y_i-z_i)^2 \le R_i^2$。

移项得到$x_i^2+y_i^2 \le R_i^2-z_i^2 +2y_iz_i $。

如果我们把$(x_i,y_i)$映射到$(y_i,x_i^2+y_i^2)$,则问题转化为询问直线$l:kx+b$以下的点个数。其中$k=2z_i,b=R_i^2-z_i^2$。

维护斜率固定时的点的相对顺序，每次询问二分即可。

时间复杂度$O((n^2+Q)\log n)$。

期望得分:$30$，结合算法$1$期望$60$。

算法3

欸$n=12000$好像不太能继续用算法$2$了。

欸能不能把$n$给分成若干块，每块单独计算贡献。

如果按照分块的思路去维护，设把点序列分成$S$块，每一块按照算法$2$的思路来处理，则时间复杂度为$O((\frac{n^2}{S}+QS)\log n)$。

取$S=\frac{n}{\sqrt{Q}}$时最优，为$O(n\sqrt{Q}\log n)$。

期望得分:$100$。

我和算法3一样为什么我又挂掉了

坐标范围是$10^9$因此用 double 精度有可能会爆炸。

出题人没有说过点集互不相同，公告里也更新过了，所以对于相同点要又高超的处理技巧。

可能将点坐标转换后会出现三点共线，同时sort是不稳定排序，因此需要一些小技巧处理这种情况。

挑战哈密顿

from peehs_moorhsum，数据、标程、题解 by peehs_moorhsum。

算法0

我会暴力！

暴力搜索哈密顿路径，或者状压DP，可以通过前两个点。

期望得分$20$。

算法1

第三个点是$DAG$，第四个点缩强连通分量之后每个分量很小。

可以对于每个分量搜任两点之间有没有哈密顿路。

期望得分$40$。

算法2

第五个点到第十个点是在一条链上随机加边生成的。

有各种乱搞姿势，看起来能在这些点获得10~57分不等

结合算法1，可以获得50~97分

算法3

接下来是标算。

维护边的一个尽量大的子集，满足只考虑这些边时每个点出入度都不超过1，且不构成圈。

如果子集大小达到$n-1$，则找到了一条哈密顿路。

考虑调整维护子集。按随机顺序考虑边，如果加入后不构成圈，且加入之后所有点度数均仍合法，则加入这条边。

否则如果不构成圈，但有一个点度数不合法，则以一半概率加入并把该点相连的与新加入边矛盾的边断掉。

用最暴力的方法实现，也能总用时在10秒左右跑出前9个点，10分钟左右跑出最后一个点。

期望得分:$100$。

如果利用LCT维护是否构成圈，能够快很多。但出题人因为太懒，并没有写

一些彩蛋

关于有向图哈密顿链，似乎是有不少论文的。

验题人实现了其中一些，发现都是反向优化没有很好的表现。

所以欢迎吊打论文的大家在题解区交流做法ww

另：这道题主角真的是03

这次的题目背景大部分是vfleaking写的。

出题人 01,02,03 只是主人公的名字，和真实出题人没有任何的关系。

序列妙妙值

from zhouyuyang，数据、标程、题解 by zhouyuyang。

由于是 D1T1 ,为了让参赛的选手分数都好看一点，数据相对来说造的没有那么强。

算法1

我会暴力!

设$f_{i,j}$表示前$i$个数字，划分成了$j$段的最优解。

转移直接枚举新的右端点即可。

使用前缀异或和优化后时间复杂度为$O(kn^2)$。

期望得分:$40$。

算法2

我会优化暴力!

当$a_i$较小时，则我们可以记录前缀异或和为$a_i$的最优解。

转移时枚举上一个端点对应的前缀异或和即可。

设$v=\max{a_i}$，则时间复杂度为$O(knv)$

期望得分:$20 \sim 40$。

结合算法1期望得分$60 \sim 80$。

算法3

不难发现对于算法2，我们可以实现$O(1)$修改最优解，$O(v)$查询。现在我们尝试平衡一下两部分的复杂度。

在修改时，我们枚举二进制下较高的$8$位，并且更新最优解。

在询问时，我们枚举二进制下较低的$8$位，并且利用最优解更新$DP$值。

不难发现，这样转移和算法2中的等价。

时间复杂度$O(nk\sqrt{v})$。

期望得分:$100$。

其他算法

考虑序列分块，块内暴力转移，块之间采用fmt的思路转移，时间复杂度$O(kn\sqrt{n \log n})$，当场看上去是能过的。

可以尝试只枚举xor和前$256$小的状态加速转移，得分不明。

可以尝试在$trie$树上乱搞更新答案，得分也不明。

网络恢复

from Aprilgrimoire，数据、标程、题解 by Aprilgrimoire。

做法一

令所有的$a_i=1$，依次对每条边进行询问。

询问次数：$O(m)$

期望得分：$10$

做法二

每次取出$w=64$个点，令它们的权值$a$分别为$1,2,\cdots,2^{w-1}$。然后打开每条边，进行询问。通过每个点的$b$的每个bit可以判断出它和这$w$个点中的哪些点有边。

询问次数：$O(\frac{n}{w})$

期望得分：$30$

做法三

测试点$5$中，保证给出的图是树。我们可以给每个点分配随机的$a$，打开每条边，进行询问。对于图中的叶子，它的$b$恰好等于和它相连的点的$a$。对于其它点，它的$b$等于某个点的$a$的概率是很低的，可以忽略。依次考虑所有的点，如果我们发现它是叶子，那么我们就找到了一条边。我们可以报告这条边，并且把这条边从图上删掉（将它的两个端点的$b$异或上对方的$a$），并重新考虑这条边的端点是否成为了叶子。

询问次数：$1$

期望得分：$10$

做法四

测试点$6$中，保证给出的图是基环树。每次随机将边分成两个集合。由于环上至少有$3$条边，每次至少有$\frac{3}{4}$的概率使环上的边没有被划分到同一个集合中，从而得到的两个集合都是森林。尝试对这两个集合使用做法三，有较高的概率可以得到解。

询问次数：$O(1)$

期望得分：$20$

做法五

每轮随机取出一些边，只考虑被取出的边。每条边在不同的轮中可以被重复取出。使用做法三的方法持续找出度为$1$的点，直到剩下每个点的度都至少为$2$。每条边有玄学的概率在至少一轮中被发现了。

虽然不知道为什么但是效果还不错。

询问次数：$50$

期望的分：$80$

做法六

将所有的边随机分成$50$组，只考虑某一组中的边。使用做法三的方法持续找出度为$1$的点，直到剩下每个点的度都至少为$2$。假设当前剩下的每个点的度都至少为$k$，我们可以找出这些点中任意$\lfloor(k+1)/2\rfloor$个的$a$的异或和，设为集合$A$。再考虑一个点的$b$异或上$\lfloor k/2 \rfloor$个点的$a$，设为集合$B$。比较集合$A$与集合$B$，对于每个公共元素，我们就找到了将一个点的$b$表示为$k$个$a$的异或的方法。发现一些度恰好为$k$的点并删除和它们相邻的边后，可能有一些点的度现在小于$k$了。由于剩下的点数比较少，我们可以重新把$k$置为$1$，然后依次增大$k$。

虽然不知道为什么但是对于随机数据效果挺好的。

询问次数：$50$

期望得分：$100$

校园闲逛

from zhouyuyang，数据、标程、题解 by zhouyuyang。

本题idea来自于【CTSC2016】NOIP十合一的测试点$4$。

出题人没打算把FFT的常数卡到死，被喷卡常题，然后就被分治干过去了...

算法-1

暴力DP计算方案数即可。

时间复杂度$O(nmv)$。

期望得分$10$。

算法0

使用分治fft优化暴力计算的过程。

时间复杂度$O(n^3v\log^2v)$。

转移时利用点值的性质可以做到$O((n^3+n^2\log v)v\log v)$

期望得分$20 \sim 100$。

同样是算法0，为什么有人20，有人100...

选手卡常水平高超，实在打不过...告辞...

算法1

确定起点时可以列出关于答案的生成函数的方程组：

假设$a_{p,i}$表示长度为$i$的到达$p$的路径条数，$e_{p,q,i}$表示起点是$p$,终点是$q$,长度是$i$的边的数量。据此设$A_p=\sum a_{p,i}x^i$,$E_{p,q}=\sum e_{p,q,i}x^i$

设节点数为3,起点为1。则可以列出如下方程组。

$$ \left\{ \begin{array}{l} A_1=E_{1,1}A_{1}+E_{2,1}A_{2}+E_{3,1}A_{3}+1\\ A_2=E_{1,2}A_{1}+E_{2,2}A_{2}+E_{3,2}A_{3}\\ A_3=E_{1,3}A_{1}+E_{2,3}A_{2}+E_{3,3}A_{3}\\ \end{array} \right. $$

类似于高斯消元的思路，我们可以每次找到唯一一个常数项非$0$的系数进行高斯消元。由于边权不为0，因此仅有形如$E_{i,i}$的系数的常数项非$0$。

解到最后会得到若干个$A_if_i=P_i$的公式，由于$f_i$常数项非0，直接$A_i=P_if_i^{-1}$即可,其中$f_i^{-1}$表示$f_i$的逆元。

对于每个起点运行消元即可。

时间复杂度$O(n^4v\log v)$。

期望得分$50 \sim 80$。

算法2

观察不同起点时的矩阵，不难发现方程组本质只有最后一列的常数项上存在区别，其余各项均没有区别。

因此类比于解逆矩阵，我们可以同时解这$n$个方程，在消元时同时消最后的$n$个不同的方程即可。

时间复杂度$O(n^3v\log v)$。

期望得分$60 \sim 100$。

算法3

在维护高斯消元的系数的时候，仍然可以使用点值加速高斯消元系数的维护。

我们只需要在询问当前元素的值的时候进行一次IDFT，其余时间全部使用点值维护修改量即可。

时间复杂度$O(v(n^3+n^2\log v))$。

期望得分$70 \sim 100$。

由于算法$3$有着高达$7$的大常数，但是算法$2$常数只有$1$，因此算法$3$跑的挺慢的。

其他算法

如果利用FFT的点值，不要每次都暴力分治也可以过。复杂度可以和算法3一样。

如果在转移的时候利用转移系数加速分治过程也可以过。复杂度可以和算法3一样。

如果你分治常数足够小，应该可以卡着时间限制过去。

转眼间又是一年NOI了，为了帮大家备战NOI，延续UOJ的传统保留项目，在两年之后，UOJ NOI Round #4 将在8月11号到8月13号重新举行！

为了方便阅读，同时也因为管理员比较鸽，这次的UNR没有特别的主题。

比赛时间

笔试模拟将于 8 月 11 日晚 19 点开始，将进行半个小时。

Day 1 的比赛将于 8 月 12 日上午 8 点半开始，将进行五个小时，共三道题。

Day 2 的比赛将于 8 月 13 日上午 8 点半开始，将进行五个小时，共三道题。

比赛难度

比赛的难度将比 NOI2019 略微简单一些，相信对绝大部分选手来说题目是具有一定的挑战性的。

题目中还有着一道提交答案题和一道交互题，大家可以放心食用。

出题人

这次拯救UNR的出题人管理员有：

peehs_moorhsum,AprilGrimoire, zhouyuyang,Picks。

看到4个出题人出了6道题，大家可以猜猜有哪些出题人出了多于一道题。

比赛奖项

这次比赛将会根据三次比赛的总分进行排序（如果存在同分将以两天的罚时总和作为第二关键字），其中比赛的前五名将成为这次训练的金牌得主，第六名到第十五名将获得银牌，第十六名到第三十名将获得铜牌。（得奖人数将根据参赛人数进行调整）

总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。

带噶好！偶系算法竞赛小编提米>~<

在 提交记录中，最大的点平均只用了不到$960000$次询问。大家可能会很惊讶，这是怎么做到的呢？下面就跟着小编一起来看看吧！

UOJ#153有一种不需要人类智慧的、更本质一点（？）的做法。我们构造一张二分图，把第一轮$1$~$n$构成的所有连通块看作左边的点，第二轮$1$~$n$构成的所有连通块看作右边的点。两点之间连边当且仅当对应的连通块有公共点。（容易发现，两个块最多有一个公共点，否则公共点之间无法区分。）

因此二分图恰有$n$条边，且边与原题的点$1$到$n$一一对应。

通过询问$n+1$到$2n$的连通块，我们同样可以构建出一张二分图。假如我们能将该图和原先二分图的顶点一一对应，则也能将它的边$n+1$到$2n$和原先的边$1$到$n$一一对应。

将点一一对应，我们只需要图不自同构。我们可以随机生成图，计算哈希，假如哈希冲突再次随机即可。最后的图中，两部分的点数均略大于100。

此时如果随机询问点对应的连通块，期望次数会略大于$10^6$（但已经比大部分提交优了>~<)。为此，我们将已有的连通块按大小排序，和最后对应排名的连通块大小的差值认为是这个连通块的剩余点数。按照剩余点数从大到小询问，就可以做到$960000$左右啦。（每次排序时间开销较大，可以隔几轮重排一次。）

以上就是在1e6次询问内解决UOJ#153的全部内容了。大家有什么想法呢？欢迎在评论区和小编讨论哦！