UOJ Logo peehs_moorhsum的博客

博客

一种好写且卡不掉的树哈希

2022-08-25 22:31:40 By peehs_moorhsum

考虑这样一种哈希方式。对于一棵以 $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 的构造性证明

2022-08-15 10:51:48 By peehs_moorhsum

今天学了一下 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)$,显然得证。

简单多项式技巧的直观理解

2022-05-17 23:05:02 By peehs_moorhsum

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

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

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

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

暂别

2020-10-24 23:33:56 By peehs_moorhsum

又到了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

祝泥萌一切顺利!

有向图哈密顿链模板

2020-08-14 15:59:48 By peehs_moorhsum

昨天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$ 连一条边

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

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

peehs_moorhsum Avatar