思维/数学题单题解

五边形数(hard version)

根据等差数列求和，可以推知通项：

$$\sum_{i=1}^n(3i-2)=3\dfrac{n(n+1)}{2}-2n=\dfrac{n(3n-1)}2$$

注意到 $n(3n-1) >2^{64}$，而 $\dfrac{n(3n-1)}2 < 2^{64}$，即直接计算会炸 ull，但是总答案不会， 而 $n,3n-1$ 必然一个奇数一个偶数。我们可以先选取其中的偶数将其计算 $\div 2$ 再乘以奇数，则不会爆 ull。当然用 i128 的话什么事情都没有。

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
ull n, ans;
signed main()
{
    cin >> n;
    if (n % 2 == 0)
    {
        ans = n / 2 * (3 * n - 1);
    }
    else
    {
        ans = (3 * n - 1) / 2 * n;
    }
    cout << ans;
    return 0;
}

白茶与线程博弈(hard version)

设干扰线程删除了 $t$ 次时， 还剩下线程数 $m’$ 为：

$$m'=m-7at-30b(t-1)$$

设干扰线程最多删除 $t’$ 次，满足不等式：

$$m-7at'-30b(t'-1)\ge 0$$

记下取整表示为 $\lfloor x\rfloor$ ，如 $\lfloor 1.9\rfloor=1,\lfloor 2.0\rfloor=2$ 。解得：

$$t'=\lfloor\dfrac{m+30b}{7a+30b}\rfloor \le \dfrac{m+30b}{7a+30b}$$

那么前 $t’-1$ 次追踪线程都能追踪到 $30b$ 个踪迹； 第 $t’$ 次能追踪到 $m-7at-30b(t’-1)$ 个踪迹，故总追踪数 $f$ 为：

$$f=30b(t'-1)+m-7at'-30b(t'-1)=m-7at'$$ $$f=m-7a\lfloor\dfrac{m+30b}{7a+30b}\rfloor$$

特别注意 $t’$ 为 $0$ 时，上式不成立，需要特判。这是因为 $t’=0$ 时上述式子的意义会变成干扰线程还没删除前追踪线程就追踪了，不符合题意。如果算到 $t’=0$ ，即：

$$\dfrac{m+30b}{7a+30b} < 0\Rightarrow m+30b < 7a+30b \Rightarrow m < 7a$$

说明第一次干扰就删完了，自然追踪不到，所以应该是输出 what a pity。

下面简要讨论该式子的数据范围。显然 $7a+30b,m+30b$ 在 long long 内。虽然中间变量 $t’=\lfloor\dfrac{m+30b}{7a+30b}\rfloor$ 的范围理论上也是 long long 的，但 $7at’$ 不可能会爆 long long。如果要爆 long long，则 $a$ 较大且 $t’$ 较大。设 $t’\ge c$，近似解得 $\dfrac{m+30b}{7a+30b}\ge c$ 即 $b\le\dfrac{m-7ac}{30(c-1)}$。设 $7at’$ 炸 long long，则有 $7at’\ge 2^{63}$，解得 $t’\ge \dfrac{2^{63}}{7a}=c$，代入得 $b\le \dfrac{(m-2^{63})a}{30(2^{63}-7a)}$。由于 $m\le 10^{16},a>0$，故分子 $(m-2^{63})a < 0$，且分母显然大于零，即 $b\le 0$，这与题给条件 $1\le b\le10^{16}$ 矛盾。因此，通过反证法严格证明出计算过程不会炸 long long。如果担心的话可以直接开 i128。或者可以用更简单的方法，即直接从现实意义出发，可知必然有 $f\ge 0$，即 $m\le 7at’$，故显然不会炸 long long。

#include <bits/stdc++.h>
using namespace std;
long long m, a, b, t, f;
signed main()
{
    cin >> m >> a >> b;
    t = (m + 30 * b) / (7 * a + 30 * b);
    f = m - 7 * a * t;
    if (t && f >= m / 2)
    {
        cout << "I catch you, baicha";
    }
    else
    {
        cout << "what a pity";
    }
    return 0;
}

高阶前缀和

设 $a=(1,1,\cdots)$，观察可得，有 $s_{j,i}$ 矩阵(这里设下标行 $j$ 从 $0$ 开始，列 $i$ 从 $0$ 开始)：

$$s=\begin{pmatrix} 1&1&1&1&\cdots\\ 1&2&3&4&\cdots\\ 1&3&6&10&\cdots\\ 1&4&10&20&\cdots\\ 1&5&15&35&\cdots\\ \vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix}$$

抽象为 $s_{j,i}$ 表示从最左上角点 $(0,1)$ 出发，只能往左和往下走，共有多少种方案能走到 $(j,i)$。显然初始值是 $s_{0,1}=1$，且根据加法原理，有：$s_{j,i}=s_{j-1,i}+s_{j,i-1}$，可以发现该组合数学意义与前缀和数组算术等价。即问题暂时转化为问方案数。

显然，从 $(0,1)$ 走到 $(j,i)$ 共需要往下移动 $j$ 次，往左移动 $i-1$ 次，在这所有 $i+j-1$ 次移动里，分 $j$ 次往下，共有 $C_{i+j-1}^j$ 种方案。即：$a=(1,1,\cdots)$ 时，有：$s_{j,i}=C_{i+j-1}^j=C_{i+j-1}^{i-1}$。

现在推广到 $a=(a_1,a_2,\cdots, a_n)$，有：

$$s=\begin{pmatrix} a_1&a_2&a_3&a_4&\cdots\\ a_1&a_1+a_2&a_1+a_2+a_3&a_1+a_2+a_3+a_4&\cdots\\ a_1&2a_1+a_2&3a_1+2a_2+a_3&4a_1+3a_2+2a_3+a_4&\cdots\\ a_1&3a_1+a_2&6a_1+3a_2+a_3&10a_1+6a_2+3a_3+a_4&\cdots\\ \vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix}$$

换言之，现在抽象成了，可以从任一点 $(0,i)(i\le x)$ 出发，第一步只能往下走且方案数为 $a_i$，在这之后 只能往左和往下走，共有多少种方案能走到 $(j,i)(j\ge 1)$。显然，可以将其拆分为 $x$ 个子问题，即分别从 $(0,1),(0,2),\cdots,(0,x)$ 出发，走到 $(j-1,i)$ 的方案数，将这些方案数用加法原理加起来即可，有：

$$s_{j+1,i}=\sum_{x=1}^iC_{j+i-x}^{j}a_x(j\ge 1)$$

作偏移，有：

$$\begin{align} s_{j+1,i}=&\sum_{x=1}^{i}C_{i+j-x}^ja_x\\ =&C_{j+i-1}^ja_1+C_{j+i-2}^ja_2+\cdots+C_{j+i-x+1}^ja_{x-1}+C_{j+i-x}^ja_x&①\\ s_{j+1,i-1}=&\sum_{x=1}^{i-1}C_{i-1+j-x}^ja_x\\ =&C_{j+i-2}^ja_1+C_{j+i-3}^ja_2+\cdots+C_{j+i-x}^ja_{ix-1}&②\\ s_{j,i}=&\sum_{x=1}^{i}C_{i+j-1-x}^ja_x\\ =&C_{j+i-2}^{j-1}a_1+C_{j+i-3}^{j-1}a_2+\cdots+C_{j+i-2}^{j-x}a_{x-1}+C_{j+i-x-1}^{j-1}a_x&③ \end{align}$$

根据组合数学杨辉三角公式：$C_{n-1}^{r-1}+C_{n-1}^r=C_n^r$ 可知，$②+③=①$。由此，证明了该组合数学意义式子与题给前缀和式子等价。因此，可以用组合数学方法推导高阶前缀和。即所求为：

$$s_{y,x}=\sum_{k=1}^xC_{y+x-k-1}^{y-1}a_k$$

注意到 $y-1$ 很大，我们可以转化为求较小的 $C_{y+x-k-1}^{x-k}$，并且使用线性递推，即所求的从 $k=1$ 开始递增的组合数值分别是：

$$\dfrac{1}{0!},\dfrac{n}{1!},\dfrac{n(n+1)}{2!},\dfrac{n(n+1)(n+2)}{3!},\cdots$$

即每次让分子乘以多一个数，分母也改为下一个阶乘即可，可以降复杂度 $O(y)$ 为 $O(n)$。

设 $p=10^9+7$，可以 $O(n\log p)$ 或 $O(n)$(线性逆元)求出答案。前者参考代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mn = 1e5 + 10, mod = 1e9 + 7;
ll qpow(ll a, ll b = mod - 2)
{
    ll r = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
        {
            r = r * a % mod;
        }
        a = a * a % mod;
    }
    return r;
}
ll n, a[mn], x, y, t[mn], ans;
signed main()
{
    cin.tie(0)->ios::sync_with_stdio(false);
    cin >> n >> x >> y;
    t[0] = 1;
    for (ll i = 1, fm = 1, fz = 1, d = y; i <= n; ++i, ++d)
    {
        fz = fz * d % mod;
        fm = fm * i % mod;
        t[i] = fz * qpow(fm) % mod;
    }
    for (ll i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for (ll i = x, j = 0; i >= 1; --i, ++j)
    {
        ans = (ans + t[j] * a[i]) % mod;
    }
    cout << ans;
    return 0;
}

后者：(可以过自主思考)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mn = 1e5 + 10, mod = 1e9 + 7;
ll qpow(ll a, ll b = mod - 2)
{
    ll r = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
        {
            r = r * a % mod;
        }
        a = a * a % mod;
    }
    return r;
}
ll n, a[mn], x, y, t[mn], ans, fact[mn], inv[mn];
signed main()
{
    cin.tie(0)->ios::sync_with_stdio(false);
    cin >> n >> x >> y;
    fact[0] = inv[0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        fact[i] = fact[i - 1] * i % mod;
    }
    inv[n] = qpow(fact[n]);
    for (ll i = n - 1; i >= 1; --i) //线性逆元
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
    t[0] = 1;
    for (ll i = 1, fm = 1, fz = 1, d = y; i <= n; ++i, ++d)
    {
        fz = fz * d % mod;
        t[i] = fz * inv[i] % mod;
    }
    for (ll i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for (ll i = x, j = 0; i >= 1; --i, ++j)
    {
        ans = (ans + t[j] * a[i]) % mod;
    }
    cout << ans;
    return 0;
}

OEIS

设集合 $d_n=(b_1,\cdots, b_n),d_{n+1}=(b_1,\cdots, b_n,b_{n+1})$，考虑如何推导出 $b_{n+1}$ 的递推公式。

如果将最后一个元素 $b_{n+1}$ 单独划分到一类，则前 $n$ 个元素的划分数通过递归定义发现等于 $B_n$。

如果将最后一个元素与前面的任选一个元素划分到一类，有 $C_n^1$ 种选法，则剩下的 $n-1$ 个元素的划分数为 $B_{n-1}$，根据乘法原理，共有 $C_n^1B_{n-1}$ 种方案。

同理，将最后一个元素与前面的任选两个元素划分到一类有 $C_n^2$ 种选法，共有 $C_n^2B_{n-2}$ 种方案。

不断类推，设最后一个元素与前面 $k(0\le k\le n)$ 个元素划分到一类，有 $C_n^kB_{n-k}=C_n^{n-k}B_{n-k}$ 种方案。因此，递推公式为：

$$B_{n+1}=\sum_{k=0}^nC_n^{n-k}B_{n-k}=\sum_{k=0}^nC_n^kB_k$$

我们发现题目标题为 OEIS，而题目给出了前 $5$ 项，我们可以直接去搜索(可以打印 OEIS，赛时可以查询(数列按字典序排布，查起来不慢))，发现 $1,1,2,5,15$ 刚好是 A000110 即贝尔数。往下翻阅，能够查到递推公式：

这个公式表达的就是上文的公式，可以直接利用。

根据样例可知最大的 $B_{25}$ 不超过 long long。但计算组合数时，注意选择正确的方法，否则中间变量可能会爆 long long，用阶乘算式的话如果开 int128 则不会有事。推荐的方法是使用杨辉三角，能够保证不爆 long long。

杨辉三角求组合数：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n;
ll b[100], c[100][100]; // c(down,up)
signed main()
{
    cin >> n;
    for (ll i = 0; i <= n; ++i)
    {
        c[i][0] = 1;
    }
    for (ll i = 1; i <= n; ++i) //杨辉三角
    {
        for (ll j = 1; j <= i; ++j)
        {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
    b[0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 0; j < i; ++j)
        {
            b[i] += c[i - 1][j] * b[j];
        }
    }
    cout << b[n];
    return 0;
}

阶乘法：(这里化简了 $C_d^u=\dfrac{d!}{u!(d-u)!}=\dfrac{\prod_{i=d-u+1}^di}{u!}$)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
ll n;
i128 b[100];
i128 c(ll df, ll uf)
{
    i128 r = 1;
    for (ll i = df; i >= df - uf + 1; --i)
    {
        r *= i;
    }
    for (ll i = 2; i <= uf; ++i)
    {
        r /= i;
    }
    return r;
}
signed main()
{
    cin >> n;
    b[0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 0; j < i; ++j)
        {
            b[i] += c(i - 1, j) * b[j];
        }
    }
    cout << (ll)b[n];
    return 0;
}

自主思考：

• 若 $n\le 10^3$，无论用杨辉三角还是预处理阶乘+逆元都可以，加上取模公式即可。复杂度均为 $O(n^2)$ (后者可以线性逆元)。

• 若 $n\le 10^5$，根据贝尔数与第二类斯特林数性质，可知：$B_n=\sum_{k=0}^nS(n,k)$。

  同一行第二类斯特林数的计算，可以用通项公式卷积或指数生成函数，具体参见 洛谷P5395。将计算结果加起来就是 $B_n$。

换座位

这题即求长为 $n$ 的排列的错位数 $d_n$。

解法一：容斥原理推通项

设共 $n$ 人下有 $i$ 个位置的人没有换位，这 $i$ 个位置有 $C_n^i$ 种选择，则剩下 $n-i$ 个位置有 $C_{n-i}^{n-i}=1$ 种选择，而剩下的 $n-i$ 个位置都不一样，有 $(n-i)!$ 个组法，乘法原理合起来有 $C_n^i(n-i)!$。

设 $t$ 表示不满足题意的方案数，只要有人没换位都不满足，根据容斥原理有，$t=1$ 个位置的人没换位 $-2$ 个位置的人没换位 $+3$ 个位置的人没换位 $-\dots$，即：

$$t=\sum_{i=1}^n(-1)^{i+1}C_n^i(n-k)!=n!\sum_{i=1}^n\dfrac{(-1)^{i+1}}{i!}$$

则所求 $d_n$ 为总方案数 $n!$ 减去 $t$，即：

$$\begin{align} d_n&=n!-n!\sum_{i=1}^n\dfrac{(-1)^{i+1}}{i!}\\ &=n!\dfrac{(-1)^0}{0!}+n!\sum_{i=1}^n\dfrac{(-1)^{i+1}(-1)}{i!}\\ &=n!\sum_{i=0}^n\dfrac{(-1)^i}{i!} \end{align}$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, f[30], d;
signed main()
{
    cin >> n;
    f[0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        f[i] = f[i - 1] * i;
    }
    for (ll i = 0, s = 1; i <= n; ++i, s *= -1)
    {
        d += f[n] / f[i] * s;
    }
    cout << d;
    return 0;
}

解法二：递推公式

设已知 $d_i(i <n)$，要求 $d_n$。则：

1. 若前面 $n-1$ 个人都换好座位了，有 $d_{n-1}$ 种方案，第 $n$ 个人还在原地，从前面的人里任选一个人有 $n-1$ 种选法，将选出的人与第 $n$ 个人交换座位，可以得到合法方案，乘法原理得 $(n-1)d_{n-1}$。
2. 若前面 $n-1$ 个人里只有一个人还在原地，即剩下 $n-2$ 个人换好了，有 $d_{n-2}$ 种方案，选出这个在原地的人有 $n-1$ 种选法，将选出的人与第第 $n$ 个人交换座位，可以得到合法方案，乘法原理得 $(n-1)d_{n-2}$。
3. 若前面的人有更多人在原地，且第 $n$ 个人也在原地，则找不到一次交换操作使得能够变成合法方案。因此，递推项只有两种可能，即：

$$d_n=(n-1)(d_{n-1}+d_{n-2})$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, d[30] = {0, 0, 1, 2};
signed main()
{
    cin >> n;
    for (ll i = 4; i <= n; ++i)
    {
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
    }
    cout << d[n];
    return 0;
}

自然数拆分

所求即分拆数 $p_n$。定义 $k$ 部分拆数 $p_{n,k}$ 表示把 $n$ 拆成 $k$ 个整数的方案，显然有 $p_n=\sum_{i=0}^np_{n,i}$。

而 $p_{n,k}$ 是下面方程的解的个数：

$$n=r_1+r_2+\cdots+r_k\quad, r_1\ge r_2\ge\cdots\ge r_k\ge 1$$

将每个 $r$ 用 $y=r+1$ 换元，有 $r\ge 1$ 即 $y\ge 0$ 代替，有：

$$n=k+y_1+y_2+\cdots+y_k\quad,y_1\ge y_2\ge\cdots\ge y_k\ge 0$$

转化为：

$$n-k=y_1+y_2+\cdots+y_k\quad,y_1\ge y_2\ge\cdots\ge y_k\ge 0$$

如果这里边的 $y$ 有 $j$ 个满足 $y \ge 1$，则等效于求子问题 $p_{n-k,j}$，因此，枚举所有 $j$，有：

$$p(n,k)=\sum_{j=1}^kp(n-k,j)$$

更换变量，得：

$$\begin{cases} p(n,k)&=p(n-k,1)+\cdots+p(n-k,k-1)+p(n-k,k)\\ p(n-1,k-1)&=p(n-k,1)+\cdots+p(n-k,k-1) \end{cases}$$

作差，得：$p(n,k)-p(n-1,k-1)=p(n-k,k)$，因此，得到递推公式：

$$p(n,k)=p(n-1,k-1)+p(n-k,k)$$

有初始值 $p_{0,0}=1$，因此本题得解。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mn = 4e2 + 5;
ll n, p[mn][mn], ans;
signed main()
{
    cin >> n;
    p[0][0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 0; j <= n; ++j)
        {
            if (i - j >= 0)
            {
                p[i][j] = p[i - j][j] + p[i - 1][j - 1];
            }
        }
    }
    for (ll i = 0; i <= n; ++i)
    {
        ans += p[n][i];
    }
    cout << ans;
    return 0;
}

自主思考：可以使用五边形数定理求解。具体证明较复杂，感兴趣自行查。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mn = 1e5 + 10, mod = 1e9 + 7, i2 = (mod + 1) / 2;
ll a[mn], p[mn], n;
signed main()
{
    cin.tie(0)->ios::sync_with_stdio(false);
    cin >> n;
    p[0] = 1;
    for (ll i = 1; i <= n / 2 + 1; ++i)
    {
        a[2 * i - 1] = i * (3 * i - 1) % mod * i2 % mod;
        a[2 * i] = i * (3 * i + 1) % mod * i2 % mod;
    }
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 1; a[j] <= i; ++j)
        {
            if (((j + 1) / 2 + 1) % 2 == 0)
            {
                p[i] = (p[i] + p[i - a[j]]) % mod;
            }
            else
            {
                p[i] = (p[i] - p[i - a[j]] + mod) % mod;
            }
        }
    }
    cout << p[n];
    return 0;
}

二分次数

可以证明，对于长为 $n=2^0+2^1+2^2+\cdots +2^p+c$ 的数组 $ASL$ 为：

$$ASL=\dfrac1n(1\cdot 2^0+2\cdot 2^1+3\cdot 2^2\cdots+(p+1)2^p+(p+2)c)$$

即有 $2^0$ 个 $t(a_i)=1$，有 $2^1$ 个 $t(a_i)=2$，有 $2^2$ 个 $t(a_i)=3\cdots$，剩下不能凑够 $2^x$ 的有 $c$ 个。

注意到 $2^0+2^1+\cdots 2^p=2^{p+1}-1$，即对于给定的 $m,k$，有：

$$2^m+k=2^0+2^1+\cdots+2^{m-1}+(k+1)\Rightarrow p=m-1,c=k+1$$

利用错位相减法，对 $c_n=(an+b)q^{n-1}=(1\cdot n+0)2^{n-1}$，其前 $n$ 项和为：

$$S_n=(An+B)q^n-B,\quad其中 A=\dfrac{a}{q-1}=1,B=\dfrac{b-A}{q-1}=-1$$

故 $S_n=(n-1)2^n+1$。其中 $n$ 对应 $p+1$。故所求为：

$$nASL=p2^{p+1}+1+(p+2)c=(m-1)2^m+1+(m+1)(k+1)$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
ll qpow(ll a, ll b)
{
    ll r = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
        {
            r = r * a % mod;
        }
        a = a * a % mod;
    }
    return r;
}
ll m, k, ans;
signed main()
{
    cin.tie(0)->ios::sync_with_stdio(false);
    cin >> m >> k;
    ans = ((m - 1) * qpow(2, m) % mod + 1 + (m + 1) * (k + 1) % mod) % mod;
    cout << ans;
    return 0;
}

FFT

可以发现，所有情况加起来，刚好凑齐所有排列。即所有排列可以分类塞到 sum 表达式里。故答案为 $n!$。(本题为2022省赛签到题)

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &x)
typedef long long ll;
ll mod = 998244353, n, x = 1;
signed main()
{
    sc(n);
    for (ll i = 2; i <= n; ++i)
    {
        x = x * i % mod;
    }
    printf("%lld", x);
    return 0;
}

剪纸

题意即满足 $l+r$ 最小

可以发现，构造边长为斐波那契数列时，直观发现数量最多。所以找到最大不超 $n$ 的斐波那契 $f_i$ 并输出 $f_{i-1},f_i$ 即可。注意特判，$n=2$ 时不是 $1,2$ 因为两个正方形是相同的，是 $1,1$ (本题为2022省赛easy题)

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &x)
typedef long long ll;
ll n, a = 1, b = 1;
signed main()
{
    sc(n);
    if (n <= 2)
    {
        printf("1 1");
        return 0;
    }
    while (b <= n)
    {
        ll t = a;
        a = b, b = t + a;
    }
    printf("%lld %lld", b - a, a);
    return 0;
}

幂运算

先把底数为 $1$ (共 $n^2$ 种) 和底数不为 $1$ 且指数相等的情况(共 $n(n-1)$ 种)搞出来，其他情况都是不存在相等的。

有且仅有同底时能求出相等。同底的数可以互相分组，例如 $2,4,8,\cdots, 2^k$ 为一组，$3,9,\cdots,$ 为一组，$5,25,\cdots$ 为一组，$6,36,\cdots$ 为一组(组元素不能重复所以 $4$ 那里不能再开一组了)。

对于组内的元素，设最低底数为 $b$，任选两个组内元素 $b^u,b^v$，根据 $b^{ux}=b^{vy}$ 即 $ux=vy$ 有解。将方程化为最简形式即 $(u’,v’)=1$ 后，可以发现，在 $[1,n]$ 内有 $\lfloor\dfrac n{\max(u’,v’)}\rfloor$ 组解，即这些解是 $(v’,u’),(2v’,2u’),\cdots$。

问题即求：枚举每个组元素大于 $1$ 的组，任选两个指数 $u,v$ 组成 $A_n^2$ 个方程 $ux=vy$，求这些方程的小于 $n$ 的解数之和。显然，每组元素数目是 $\log n$ 级的，即枚举的复杂度为 $\log^2 n$，加上计算 $\gcd$ 的复杂度，共计 $O(\sqrt n\log^2 n\log\log n)\approx 1.4\times 10^8$(实际上远小于这个值)，可以过题。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
ll n, ans;
map<ll, bool> vis;
signed main()
{
    cin >> n;
    ans = n * (2 * n - 1) % mod;
    for (ll i = 2, p = 0; i * i <= n; ++i, p = 0)
    {
        if (vis[i])
        {
            continue;
        }
        for (ll j = i; j <= n; j *= i, ++p)
        {
            vis[j] = true;
        }
        ll s = 0;
        for (ll u = 1; u <= p; ++u)
        {
            for (ll v = u + 1; v <= p; ++v)
            {
                ll g = __gcd(u, v);
                ll u2 = u / g, v2 = v / g;
                s += n / max(u2, v2);
            }
        }
        ans = (ans + 2 * s) % mod;
    }
    cout << ans;
    return 0;
}

平面最近点对

分析代码特点，可知若我们在旋转后的坐标轴上绘制如下的点：

那么最下面的两个点间取得最小距离 $d=0.5$，但是根据排序结果，其中间被五个点挡住，所以对左下角点，只会求其与竖线上五个点的距离，求不到最小点。而之后求的每一个距离都必然大于 $0.5$。故该构造得解。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
vector<pair<db, db>> v;
signed main()
{
    db z = sin(-1), w = cos(-1);
    auto rot = [&](db x, db y)
    {
        db x_ = x * w - y * z;
        db y_ = x * z + y * w;
        return make_pair(x_ + 100, y_ + 100);
    };
    v.push_back(rot(0.75, 0));
    v.push_back(rot(1.25, 0));
    v.push_back(rot(1, 1));
    v.push_back(rot(1, 2));
    v.push_back(rot(1, 3));
    v.push_back(rot(1, 4));
    v.push_back(rot(1, 5));
    printf("%d\n", v.size());
    for (auto pr : v)
    {
        printf("%lf %lf\n", pr.first, pr.second);
    }
    return 0;
}

附：正确的平面最近点对解法(复杂度 $O(n\log n)$)如下

namespace solve_ac
{
    ll n;
    db ans = 1e18;
    const ll mn = 2e5 + 10;
    struct node
    {
        db x, y;
        bool operator<(const node &r) const { return x < r.x; }
    } p[mn];
    void solve(ll lc, ll rc)
    {
        if (lc == rc)
        {
            return;
        }
        ll cc = (lc + rc) >> 1;
        db cx = p[cc].x; //修改前的
        solve(lc, cc), solve(cc + 1, rc);
        inplace_merge(p + lc, p + cc + 1, p + rc + 1, [](const node &x, const node &y)
                      { return x.y < y.y; });
        vector<node> v;
        for (ll i = lc; i <= rc; ++i)
        {
            if (sqrt((cx - p[i].x) * (cx - p[i].x)) <= ans)
            {
                v.emplace_back(p[i]);
            }
        }
        for (auto lf = v.begin(), rf = lf; lf != v.end(); lf++)
        {
            db sans = ans;
            while (rf != v.end() && rf->y <= lf->y + sans)
            {
                ++rf;
            }
            for (auto i = lf + 1; i != rf; ++i)
            {
                ans = min(ans, sqrt((lf->x - i->x) * (lf->x - i->x) + (lf->y - i->y) * (lf->y - i->y)));
            }
        }
    }
    db getans(vector<pair<db, db>> &p0)
    {
        n = p0.size();
        for (ll i = 1; i <= n; ++i)
        {
            p[i].x = p0[i - 1].first, p[i].y = p0[i - 1].second;
        }
        sort(p + 1, p + 1 + n);
        solve(1, n);
        return ans;
    }
}

最后更新： 2023年11月02日 17:38

原始链接： https://lr580.github.io/2022/11/06/%E6%80%9D%E7%BB%B4-%E6%95%B0%E5%AD%A6%E9%A2%98%E5%8D%95%E9%A2%98%E8%A7%A3/

lr580