# 某岛

… : "…アッカリ～ン . .. . " .. .
August 28, 2021

# 传送门

https://codeforces.com/contest/1558

# Problem B. Up the Strip

$f(x) = \sum \limits_{y=1}^{x-1} f(x-y) + \sum \limits_{z=2}^{x} f(\lfloor \frac{x}{z} \rfloor)$
f(1) = 1，求 f(n)。

const int N = int(4e6) + 9;

Int f[N], s[N];
int n;

int main()
{

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

RD(n, MOD); f[n] = s[n] = 1;
DWN(i, n, 1) {
f[i] = s[i+1];
//FOR_1(j, 2, i) f[i/j] += f[i];
for (int j=2;i*j<=n;++j) {
int l = i*j, r = min(n+1, l+j);
f[i] += s[l]-s[r];
}
s[i] = s[i+1] + f[i];
}

cout << f[1] << endl;
}


# Problem D. Top-Notch Insertions

（证明，后面的每个数都多一个等号成立的影子状态，相当于给后面每个位置都累加 1，以保证每个数不相等，构造出从 2n+1 个数里选 n 个数的一一映射。）

Splay + 动态离散化（608ms）

    Rush {
r = r0; RD(n); int m = 0; Rush {
int x, y; RD(x, y);
if (r[y] == 0) {
++m;
r.insert(y+1, 1);
} else {
r.insert(y, 0);
}
//REP(i, 10) cout << r[i]; cout <<endl;
}
cout << Binom(n+n-1-m, n) << endl;
}


Rope（1965ms）

# Problem E. Down Below

n <= 1000, m <= 2000

BFS 找环