环检测算法学习笔记

# Floyd's Tortoise and Hare 环检测算法

https://www.jianshu.com/p/4f7dc8b9aa3c

算法总结：

# 步骤1

两个指针 $ptr1,ptr2$ 分别从原点出发，每次分别走 $1、2$ 步。直到 $val(ptr1)=val(ptr2)$ 。

# 步骤2

$ptr2$ 不变， $ptr1$ 返回原点，继续迭代，但此时两者的步长均为 $1$ ，直至 $val(ptr1)=val(ptr2)$ 。

此时 $ptr1$ 所在位置即为环的入口点（该点属于环的一部分）

# 步骤3

$ptr1$ 不边， $ptr2$ 继续以 $1$ 步长前进，直至 $val(ptr1)=val(ptr2)$ ，前进的步数即为循环节长度

详细实现见下方例题的求循环代码

# 例题 Codeforces Gym102501H

猜测 $f(x)$ 有一个较小的循环节：

求循环代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll mod = 1ll<<40;
const ll startNum = 0x600DCAFE;

inline ll getNext(ll x) {return (x + (x >> 20) + 12345) % mod;}
void solve(){
    ll cur1 = getNext(startNum), ptr1 = 1;
    ll cur2 = getNext(getNext(startNum)), ptr2 = 2;
    while(cur1 != cur2){
        cur1 = getNext(cur1), ptr1++;
        cur2 = getNext(getNext(cur2)), ptr2+=2;
    }
    cur1 = startNum, ptr1 = 0;
    while(cur1 != cur2){
        cur1 = getNext(cur1), ptr1++;
        cur2 = getNext(cur2), ptr2++;
    }
    cout << "entrence: " << ptr1 << endl;
    ptr2 = ptr1 + 1, cur2 = getNext(cur1);
    ll ans = !(cur2 & 1);
    while(cur1 != cur2) {
        cur2 = getNext(cur2), ptr2++;
        ans += !(cur2 & 1);
    }
    cout << "circuit length: " << ptr2 - ptr1 << endl;
    cout << "even number per loop: " << ans << endl;
}

signed main(){
    clock_t start = clock();
    solve();
    cerr << "timeConsume: " << ((double)(clock() - start) / CLOCKS_PER_SEC) << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

输出结果:

entrence: 350125310
circuit length: 182129209
even number per loop: 91029304
timeConsume: 11.904

1
2
3
4

也就是说，循环节长度为182129209，入口点在350125310，每个循环有91029304个偶数

那么，只要我们预处理出0到350125310 + 182129209 - 1个数中分别对应多少个偶数即可

分块大小为 $5e6$ ，可以在0.3s内处理完

分块打表代码:

#include <bits/stdc++.h>
#define ll long long

using namespace std;

void redirect_output() { freopen("./output.txt", "w", stdout); }

const ll mod = 1ll<<40;
const ll startNum = 0x600DCAFE;
const ll block_size = 5e6;

inline ll getNext(ll x) {return (x + (x >> 20) + 12345) % mod;}
void solve(){
    ll cur = startNum, ans = !(cur & 1);
    for(ll i=0; i<=532254519ll; i++){
        if(i % block_size == 0){
            cout << "{" << cur << "ll, " << ans << "ll},";
            if(i / block_size % 4 == 3) cout << '\n';
        }
        cur = getNext(cur);
        ans += !(cur & 1);
    }
}

signed main(){
    redirect_output();
    clock_t start = clock();
    solve();
    cerr << "timeConsume: " << ((double)(clock() - start) / CLOCKS_PER_SEC) << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

AC代码

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)

using namespace std;

const ll table[][2] = {
{1611516670ll, 1ll},{6995323118ll, 2500401ll},{14370630249ll, 5004364ll},{24473902285ll, 7500029ll},
{38312556854ll, 10006017ll},{57274551969ll, 12506329ll},{83248007737ll, 15011683ll},{118826730177ll, 17517443ll},
{167560289742ll, 20012408ll},{234323188514ll, 22530434ll},{325792323073ll, 25031296ll},{451094609069ll, 27539195ll},
{622741727028ll, 30040232ll},{857898708083ll, 32538480ll},{937685173ll, 35042602ll},{6072677726ll, 37541450ll},
{13107744445ll, 40042828ll},{22744003927ll, 42546233ll},{35943646365ll, 45056959ll},{54027907086ll, 47548216ll},
{78802032994ll, 50056831ll},{112739509636ll, 52565704ll},{159235062884ll, 55056278ll},{222913708970ll, 57559660ll},
{310147760736ll, 60057168ll},{429642460847ll, 62554179ll},{593348380684ll, 65062411ll},{817588294774ll, 67574933ll},
{295498034ll, 70077204ll},{5192879414ll, 72572034ll},{11901289737ll, 75074286ll},{21092425584ll, 77586589ll},
{33681877906ll, 80089334ll},{50930014590ll, 82577797ll},{74557367833ll, 85076566ll},{106926639410ll, 87569837ll},
{151258698876ll, 90060817ll},{211997026857ll, 92557144ll},{295206930517ll, 95067617ll},{409189858068ll, 97582000ll},
{565345893787ll, 100089173ll},{779223572048ll, 102578453ll},{1072246754882ll, 105080524ll},{4354683110ll, 107578420ll},
{10752858133ll, 110081437ll},{19518274761ll, 112579315ll},{31526697331ll, 115071718ll},{47977804257ll, 117584728ll},
{70512631458ll, 120091493ll},{101383583168ll, 122603663ll},{143677078963ll, 125100277ll},{201601781662ll, 127598938ll},
{280954761586ll, 130104566ll},{389678281232ll, 132606644ll},{538598461112ll, 135114812ll},{742592321221ll, 137604957ll},
{1022070324749ll, 140110603ll},{3554026557ll, 142613775ll},{9655697881ll, 145118771ll},{18014204912ll, 147616701ll},
{29466792348ll, 150119937ll},{45154383935ll, 152614526ll},{66642984633ll, 155117508ll},{96085200428ll, 157608613ll},
{136417233148ll, 160106698ll},{191671943332ll, 162605678ll},{267368060404ll, 165108248ll},{371063286307ll, 167605345ll},
{513107125545ll, 170101751ll},{707668644954ll, 172599641ll},{974225187667ll, 175085228ll},{2790547793ll, 177572982ll},
{8611289031ll, 180074324ll},{16584933110ll, 182564868ll},{27507640334ll, 185067560ll},{42470755600ll, 187569610ll},
{62966213954ll, 190070901ll},{91040988045ll, 192573754ll},{129505250351ll, 195073010ll},{182194153727ll, 197571938ll},
{254367017868ll, 200067363ll},{353236621546ll, 202571441ll},{488691710416ll, 205056578ll},{674235835123ll, 207563824ll},
{928397275086ll, 210056612ll},{2061291639ll, 212555608ll},{7611195984ll, 215046440ll},{15215211602ll, 217558986ll},
{25631359205ll, 220055532ll},{39898870311ll, 222551803ll},{59446145748ll, 225059431ll},{86223613511ll, 227563092ll},
{122903535528ll, 230050444ll},{173156136173ll, 232565955ll},{241996682198ll, 235069888ll},{336303276921ll, 237573994ll},
{465478252203ll, 240074925ll},{642434794044ll, 242579118ll},{884883721897ll, 245073898ll},{1367467361ll, 247575267ll},
{6660774750ll, 250065868ll},{13913445317ll, 252566347ll},{23846914106ll, 255061631ll},{37457188797ll, 257561860ll},
{56101519545ll, 260064780ll},{81642081850ll, 262557086ll},{116629560400ll, 265048248ll}
};

const ll mod = 1ll<<40;
const ll startNum = 0x600DCAFE, block_size = 5e6, loop_len = 182129209, entrance = 350125310, mul = 91029304;

inline ll getNext(ll x) {return (x + (x >> 20) + 12345) % mod;}
void solve(){
    ll n, ans = 0;
    cin >> n;
    if(n == 0){
        cout << "0\n";
        return;
    }
    n--;
    if(n > entrance){
        ll tmp = (n - entrance) / loop_len;
        ans = tmp * mul;
        n -= tmp * loop_len;
    }
    ll cur = table[n / block_size][0], ptr = block_size * (n / block_size);
    ans += table[n / block_size][1];
    for(;ptr < n; ptr++){
        cur = getNext(cur);
        ans += !(cur & 1);
    }
    cout << ans << endl;
}

signed main(){
    Android;
    solve();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

# 参考

https://dinnerhunt.cn/post/GYM-102501/

https://www.cnblogs.com/JHSeng/p/12332531.html

上次更新: 2021/02/24, 03:37:30

← 带权并查集处理线段约瑟夫环学习笔记→