Glucoco
0%

发表于 更新于 分类于 阅读次数：

题目链接：ICPC 2019 南京网络赛 B 题

思路

题目要求 \[ a^{a^{a^{\cdots}}}  \pmod{m}\] 其中共有\(b\)个\(a\)。 考虑欧拉函数降幂。我们常用的欧拉函数降幂是这样的： \[ a^b \equiv \left\{ \begin{aligned} & a^{b \bmod \varphi(m)} & {\rm gcd}(a, m)=1 \\ & a^b &{\rm gcd}(a, m)\neq 1, b < \varphi(m) \\ & a^{b \bmod\varphi(m) +\varphi(m)} &{\rm gcd}(a, m)\neq 1, b \geq \varphi(m)  \end{aligned} \right . \pmod{m} \] 其中第一个式子是被包含在后两个式子当中的。那么对于我们要求的式子，记\(f(a,b,m)\)为\(b\)个\(a\)在这种形式下对\(m\)取模的值，记\(t(a,b)\)为\(b\)个\(a\)在这种形式下的值。我们可以得这样的递推关系，当\(t(a,b) < \varphi(m)\)时，我们可以直接递归求\(t(a,b)\)，否则\(f(a,b,m) = a^{f(a,b-1,\varphi(m)) + \varphi(m)} \pmod{m}\)。在判断\(t(a,b)\)和\(\varphi(m)\)的时候，由于\(t(a,b)\)增长的速度很快，对于\(a \geq 3\)，只要\(b \geq 2\)，一定满足\(t(a,b) \geq m\)，其他情况特判即可。由于不断的对\(m\)取\(\varphi(m)\)，所以第三个参数会很快收敛到\(1\)，所以跑得很快。

代码

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
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 1000000 + 5;
LL vis[MAX_N];
LL p[MAX_N], phi[MAX_N], tot;
void linearSieve() {
    vis[0] = vis[1] = 1;
    phi[1] = 1;
    for (LL i = 2; i < MAX_N; ++i) {
        if (!vis[i]) {
            p[++tot] = i;
            phi[i] = i - 1;
        }
        for (LL j = 1; j <= tot && i * p[j] < MAX_N; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            } else {
                phi[i * p[j]] = phi[i] * phi[p[j]];
            }
        }
    }
}
inline LL getPow(LL x, LL y, LL P) {
    LL ret = 1 % P;
    while (y) {
        if (y & 1) ret = ret * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return ret;
}
LL T;
LL a, b, m;
// u ^ v < P
bool check(LL u, LL v, LL P) {
    if (v == 0) return 1 < P;
    if (u >= P) return false;
    if (u == 1) return u < P;
    if (u == 2) {
        if (v >= 5) return false;
        else {
            if (v == 1) return 2 < P;
            if (v == 2) return 4 < P;
            if (v == 3) return 16 < P;
            if (v == 4) return 65536 < P;
        }
    }
    if (u >= 3) {
        if (v >= 2) return false;
        else return u < P;
    }
}
LL f(LL u, LL v) {
    if (v == 0) return 1;
    else return getPow(u, f(u, v - 1), LL(1E18));
}
LL solve(LL u, LL v, LL P) {
    // printf("Call solve(%lld, %lld, %lld)\n", u, v, P);
    if (P == 1) return 0;
    if (v == 1) return u % P;
    LL t = phi[P];
    if (check(u, v - 1, t)) return f(u, v) % P;
    else return getPow(u, solve(u, v - 1, t) + t, P);
}
int main() {
    linearSieve();
    scanf("%lld", &T);
    for (LL cs = 1; cs <= T; ++cs) {
        scanf("%lld%lld%lld", &a, &b, &m);
        printf("%lld\n", solve(a, b, m));
    }
    return 0;
}

发表于 更新于 分类于 阅读次数：

题目链接：HDU 6706

思路

\[ {\rm gcd}(i,j) = 1, i > j \rightarrow {\rm gcd}(i^a - j^a, i^b - j^b) = i^{ {\rm gcd} (a,b)} - j^{ {\rm gcd} (a,b)} \]

\[ \begin{aligned} f(n, a, b) = & \sum_{i = 1}^{n} \sum_{j = 1}^{i} {\rm gcd} (i^a - j^a, i^b - j^b)[ {\rm gcd} (i,j)=1] \\ = & \sum_{i = 1}^{n} \sum_{j=1}^{i} (i-j)[{\rm gcd}(i, j)=1] \\ = & \sum_{i = 1}^{n} \sum_{j = 1}^{i} i [{\rm gcd}(i, j) = 1] - \sum_{i = 1}^{n} \sum_{j = 1}^{i} j[{\rm gcd}(i, j) = 1]  \end{aligned} \]

被减数 \(\sum_{i = 1}^{n} \sum_{j=1}^{i} = \sum_{i = 1}^{n} i \sum_{j = 1}^{i} [{\rm gcd}(i,j) = 1] = \sum_{i = 1}^{n} i \varphi(i)\)。

减数考虑\({\rm gcd}(i,j) = {\rm gcd}(i, i - j)\)，故如果存在一个有贡献的\(j'\)，一定存在一个有贡献的\(i - j'\)，他们的贡献和是\(i\)。对于每一个这样的\((i)\)都有\(\varphi(i)\)组\((i,j)\)，去重之后可以表示为\(\sum_{i = 1}^{n} (\frac{i \varphi(i)}{2} + [i=1])\)。

所以我们可以推得：

\[f(n, a, b) = \frac{\sum_{i = 1}^{n} i \varphi(i) - 1}{2}\]

\(f(x) = x \varphi(x)\)是积性函数，考虑使用筛法。设\(g(x) = x\)，令\(f\)和\(g\)做Direclet卷积：

\[ f * g (x) = \sum_{d|x} \frac{x}{d} \varphi(\frac{x}{d}) d = \sum_{d|n} x \varphi(\frac{x}{d}) = x \sum_{d|n} \varphi(\frac{x}{d}) = x^2  \]

可求前缀和，记\(\sum_{x=1}^{n} f(x) = F(n)\)，也就是我们要求的值，那么

\[ \begin{aligned} \frac{n(n+1)(2n + 1)}{6} = \sum_{x = 1}^{n} f * g(x) =&  \sum_{x = 1}^{n} \sum_{d|x} x \varphi(\frac{x}{d}) \\ = & \sum_{d=1}^{n}\sum_{x=1}^{n} x \varphi(\frac{x}{d}) [d | x] \\ = & \sum_{d=1}^{n}  \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} xd\varphi(x) \\ = & \sum_{d=1}^{n} d \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} x \varphi(x) \\ = & F(n) + \sum_{d = 2}^{n} d F(\lfloor \frac{n}{d} \rfloor) \end{aligned} \]

所以我们可以得到

\[F(n) = \frac{n(n+1)(2n + 1)}{6} -\sum_{d = 2}^{n} d F(\lfloor \frac{n}{d} \rfloor)\]

杜教筛即可。

实测结果预处理前\(n \leq 3.5 \times 10^6\)的\(F(n)\)是最快的，在HDU的老爷机上跑了998 MS。

预处理线性筛，对于积性函数\(f(x) = x \varphi(x)\)：

  • \(f(p) = p(p - 1)\)
  • \(f(p^k) = p^k \varphi(p^k)\)，\(f(p^{k+1}) = p^{k+1} \varphi(p^{k+1}) = p^{k+1} \varphi(p^k) p = p^{k+2} \varphi(p^k)\)，所以\(f(p^{k+1}) = p^2 f(p^k)\)

代码

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
67
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_LEN = int(3E6) + int(5E5) + 5;
const int P = int(1E9) + 7;
LL getPow(LL x, LL y) {
    LL ret = 1;
    while (y) {
        if (y & 1) ret = ret * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return ret;
}
LL inv_6, inv_2;
LL n, T;
bool vis[MAX_LEN];
LL tot, p[MAX_LEN], low[MAX_LEN];
LL f[MAX_LEN];
void linearSieve() {
    vis[0] = vis[1] = 1; low[1] = f[1] = 1;
    for (LL i = 2; i < MAX_LEN; ++i) {
        if (!vis[i]) {
            low[i] = p[++tot] = i;
            f[i] = 1LL * i * (i - 1) % P;
        }
        for (LL j = 1; j <= tot && 1LL * i * p[j] < MAX_LEN; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) {
                low[i * p[j]] = low[i] * p[j];
                if (low[i] == i) f[i * p[j]] = ((1LL * p[j] * p[j]) % P * f[i]) % P;
                else f[i * p[j]] = (f[i / low[i]] * f[p[j] * low[i]]) % P;
                break;
            } else {
                f[i * p[j]] = (f[i] * f[p[j]]) % P;
                low[i * p[j]] = p[j];
            }
        }
    }
    for (LL i = 1; i < MAX_LEN; ++i) f[i] = (f[i] + f[i - 1]) % P;
}
unordered_map <LL, LL> hashS;
LL sum(LL x) {
    if (x < MAX_LEN) return f[x];
    if (hashS.find(x) != hashS.end()) return hashS[x];
    LL ret = (1LL * x * (x + 1) % P) * (1LL * (2 * x + 1) * inv_6 % P) % P;
    LL l, r;
    for (l = 2; l <= x; l = r + 1) {
        r = x / (x / l);
        ret -= (((l + r) * (r - l + 1) % P * inv_2) % P * sum(x / l));
        ret = ((ret % P) + P) % P;
    }
    return hashS[x] = ret;
}
int main() {
    scanf("%lld", &T);
    linearSieve();
    inv_6 = getPow(6, P - 2);
    inv_2 = getPow(2, P - 2);
    int ta, tb;
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%lld%lld%lld", &n, &ta, &tb);
        LL ans = ((sum(n) - 1) % P + P) % P * inv_2 % P;
        printf("%lld\n", ans);
    }
    return 0;
}

发表于 更新于 分类于 阅读次数：

题目链接：HDU 6709

考虑什么情况下花费的时间最少。我们要花的必要的时间是\(k + \sum t_i\)，如果所有的捕鱼工作全部能在煮鱼的时候完成。如下图所示：

这种情况花费的时间肯定是最小的，为\(k + \sum t_i\)，但是前提是\(1 + \sum \lfloor \frac{t_i}{k}  \rfloor\geq n\)。但是如果\(t_i\)很小，那么我们可能会牺牲\(k - (t_i \bmod k)\)的时间用来抓鱼，例如这种情况：

于是在 \(1 + \sum \lfloor \frac{t_i}{k}  \rfloor < n\) 的情况下我们可以牺牲前 \(n - (1 + \sum \lfloor \frac{t_i}{k}  \rfloor )\) 个最小的 \(k - (t_i \bmod k)\) 来捉鱼，这样保证牺牲的时间是最小的。

其实我们可以观察到每一次开始煮鱼的时候也是捕新鱼的开始，我们其实只要对每一个这样的单位区间，这样的区间有三种情况，一种是出现捕鱼的时候不能煮鱼（即不等），一种是煮鱼的时候不能捕鱼（即等），一种是 \(t_i \bmod k = 0\)。如果我们把煮鱼的时间看成是必要的，那么我们就要减少因为捕鱼浪费的煮鱼时间；如果我们把捕鱼的时间看作是必要的，那么我们就要减少因为煮鱼浪费的捕鱼的时间，这里也用到了定一个求另一个的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
int T, n, k, t[MAX_N], r[MAX_N];
int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &n, &k);
        LL sum = 0;
        for (int i = 1; i <= n; ++i) scanf("%d", t + i), sum += t[i];
        LL cnt = 1;
        for (int i = 1; i <= n; ++i) cnt += t[i] / k;
        if (cnt >= n) printf("%lld\n", k + sum);
        else {
            LL rem = n - cnt;
            for (int i = 1; i <= n; ++i) r[i] = (k - t[i] % k);
            sort(r + 1, r + n + 1);
            for (int i = 1; i <= rem; ++i) sum += r[i];
            printf("%lld\n", k + sum);
        }
    }
    return 0;
}

发表于 更新于 分类于 阅读次数：

题目链接：HDU 6705

题目要在无源有向带圈图中找第\(k\)短的路径。 比赛的时候我用堆动态维护前\(50000\)大的\(d\)（与Dijkstra中\(d\)意义相同），暴力拓边，以TLE告终。 实际上没有必要对所有的边进行拓展，如下图中\(A\)拓展到了\(B\)，这条边是全局最小的边，接着我们用\(B\)去拓展新边的时候，其实只要考虑与\(B\)邻接的最小的一条边，这个时候\(AB+BC\)被加入堆中，但是有可能\(AB+BC\)不是\(AB\)的下一个状态，因为只要比\(AB\)大一点点就可能是它的下一个状态，所以\(AF\)可能影响\(AB+BC\)的排名，所以也要加入堆中。

所以，综上所述，我们对每个点的出边进行排序，用堆动态维护当前最小的路径，每次BFS拓展的时候只要拓展当前点最小的出边和当前边的下一条边即可。 渐进时间复杂度\(O(T(n+q)\log n)\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 50000 + 5;
struct Edge {
    int from, to; LL cost;
    friend bool operator < (const Edge &u, const Edge &v) {
        return u.cost < v.cost;
    }
};
int T, n, m, q, qr[MAX_N];
LL ans[MAX_N];
vector <Edge> g[MAX_N];
struct Status {
    int from, to, id;
    LL cost;
    friend bool operator < (const Status &u, const Status &v) {
        return u.cost > v.cost;
    }
};
priority_queue <Status> que;
int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 1; i <= n; ++i) g[i].clear();
        int u, v, w;
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back({u, v, w});
        }
        while (!que.empty()) que.pop();
        for (int i = 1; i <= n; ++i) sort(g[i].begin(), g[i].end());
        for (int i = 1; i <= n; ++i) {
            if (g[i].size()) que.push({g[i][0].from, g[i][0].to, 0, g[i][0].cost});
        }
        int maxK = -1;
        for (int i = 1; i <= q; ++i) scanf("%d", qr + i), maxK = max(maxK, qr[i]);
        for (int i = 1; i <= maxK; ++i) {
            Status t = que.top(); que.pop();
            ans[i] = t.cost;
            if (g[t.to].size()) que.push({g[t.to][0].from, g[t.to][0].to, 0, t.cost + g[t.to][0].cost});
            if (t.id + 1 < g[t.from].size())
                que.push({
                    g[t.from][t.id + 1].from,
                    g[t.from][t.id + 1].to,
                    t.id + 1,
                    t.cost - g[t.from][t.id].cost + g[t.from][t.id + 1].cost
                });
        }
        for (int i = 1; i <= q; ++i) printf("%lld\n", ans[qr[i]]);
    }
    return 0;
}

发表于 更新于 分类于 阅读次数：

题目链接：Codeforces 1200E

维护一个字符串\(r\)表示答案，然后对于每一个字符串\(s_i\)，和相同长度的\(r\)的后缀\(r_{s}\)拼接起来（\(s_i\)在前，\(r_s\)在后），求\(\rm fail\)函数，得到最长公共前后缀的长度，取当前字符串的长度取一个最小值，这个值就是\(s_i\)添加到\(r\)中之前要删除的前缀的长度。

渐进时间复杂度\(O(n)\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = int(1E5) + 5;
const int MAX_L = int(1E6) + 5;
int n;
string str[MAX_N];
string ans;
int fail[MAX_L];
char s[MAX_L];
int cal(const string &u, const string &v) {
    int tot = 0;
    for (auto const &c: u) s[++tot] = c; s[++tot] = '#';
    for (auto const &c: v) s[++tot] = c; s[tot + 1] = '!';
    for (int i = 2, j = 0; i <= tot; ++i) {
        while (j && s[i] != s[j + 1]) j = fail[j];
        if (s[i] == s[j + 1]) ++j;
        fail[i] = j;
    }
    return min(fail[tot], int(u.size()));
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> str[i];
    ans = str[1];
    for (int i = 2; i <= n; ++i) {
        string suf = ans.substr(max(int(ans.size() - str[i].size()), 0), str[i].size());
        int cut = cal(str[i], suf);
        ans += str[i].substr(cut, str[i].size() - cut);
    }
    cout << ans << endl;
    return 0;
}

发表于 更新于 分类于 阅读次数：

题目链接：BZOJ 1009

设准考证号为目标串\(S\)，不吉利的数字串为模式串\(T\)。 考虑对\(S\)和\(T\)进行模式匹配，\(f(i,j)\)表示匹配到目标串的第\(i\)位和模式串的第\(j\)位，并且之前没有出现过完全匹配的子串，这种情况下目标串前\(i\)位的组成方案数量。那么显然答案为\(\sum_{i=0}^{m-1} f(n, i)\)。 这时候有两种情况：

  • \(s_i = t_j\)，\(f(i, j) = f(i - 1, j - 1)\)
  • \(s_i \neq t_j\), \(f(i, j) = \sum f(i - 1,k)[{\rm fail}(k) = j - 1]\)

所以\(f(i,j)\)要么从\(f(i-1,j-1)\)转移，要么从能跳转到\(f(i-1,j-1)\)的\(f(i-1,k)\)转移（基于\(j-1\)结尾的后缀和\(i-1\)为结尾的后缀已经匹配完了）。

考虑\(n \leq 10^9\)，这个式子要继续化简。我们设一个新的函数\(g(u, v)\)，表示在\(u\)位置的所有可能取值中，\(u\)能转移到\(v\)的方案数，显然\(g(u,v)\)由两部分构成：一个是\(v=u + 1\)并且\(v\)匹配成功，另一个是\({\rm fail}(v) = u - 1\)。那么我们可以得到：

\[f(i, j) = \sum_{k=0}^{m-1} f(i - 1, k) \times g(k, j)\]

\(k\)的范围\([0,m-1]\)表示合法串中不能由完整的模式串匹配，求和部分就是统计转移的贡献。

此时我们可以把上式转化为 \[ \begin{aligned} & \begin{bmatrix} f(i-1, 0) & f(i-1,1) & \cdots & f(i-1, m-1) \\ f(i-1, 0) & f(i-1,1) & \cdots & f(i-1, m-1) \\ \vdots & \vdots & \ddots & \vdots \\ f(i-1, 0) & f(i-1,1) & \cdots & f(i-1, m-1)    \end{bmatrix} \cdot g \\ = & \begin{bmatrix} f(i, 0) & f(i,1) & \cdots & f(i, m-1) \\ f(i, 0) & f(i,1) & \cdots & f(i, m-1) \\ \vdots & \vdots & \ddots & \vdots \\ f(i, 0) & f(i,1) & \cdots & f(i, m-1)    \end{bmatrix} \end{aligned}   \]

因此可以使用矩阵快速幂进行优化，渐进时间复杂度\(O(m^3 \log n)\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 20 + 5;
int n, m, k, fail[MAX_N];
char s[MAX_N];
struct Matrix {
    int _[MAX_N][MAX_N];
    Matrix() {
        memset(_, 0, sizeof _);
    }
    friend Matrix operator * (const Matrix &u, const Matrix &v) {
        Matrix ret;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < m; ++j) {
                for (int t = 0; t < m; ++t) {
                    ret._[i][j] += u._[i][t] * v._[t][j];
                    ret._[i][j] %= k;
                }
            }
        }
        return ret;
    }
} g, f;
Matrix getPow(Matrix x, int y) {
    Matrix ret;
    for (int i = 0; i <= m; ++i) ret._[i][i] = 1;
    while (y) {
        if (y & 1) ret = ret * x;
        x = x * x;
        y >>= 1;
    }
    return ret;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    scanf("%s", s + 1);
    for (int i = 2, j = 0; i <= m; ++i) {
        while (j && s[i] != s[j + 1]) j = fail[j];
        if (s[i] == s[j + 1]) ++j;
        fail[i] = j;
    }
    // for (int i = 1; i <= m; ++i) printf("fail[%d] = %d\n", i, fail[i]);
    for (int i = 0; i < m; ++i) {
        for (char c = '0'; c <= '9'; ++c) {
            int j = i;
            while (j && c != s[j + 1]) j = fail[j];
            if (s[j + 1] == c) ++j;
            g._[i][j] = (g._[i][j] + 1) % k;
        }
    }
    f._[0][0] = 1;
    f = f * getPow(g, n);
    int ans = 0;
    for (int i = 0; i < m; ++i) ans = (ans + f._[0][i]) % k;
    printf("%d\n", ans);
    return 0;
}

发表于 更新于 分类于 阅读次数：

题目链接：Gym - 101981G

这道题是去年南京区预赛的题，现场没有推出公式，到现在仍然不知道公式怎么推，但是最近从其他的推公式的题中得到了一些启发，总结了一些打表找规律的方法。

首先我们可以先建立一个平面直角坐标系，假设边长为\(n\)的三角形中有\(d\)个点，我们把\(d\)个点暴力枚举出来，然后\(O({\rm C}_{n}^{3})\)枚举多少个组合能构成等边三角形。

打表程序如下：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 1000 + 5;
int n, tot;
double x[MAX_N], y[MAX_N];
inline double dist(int u, int v) {
    double dx = x[u] - x[v], dy = y[u] - y[v];
    return sqrt(dx * dx + dy * dy);
}
inline bool equal(double u, double v) {
    return fabs(u - v) < 0.01;
}
int main() {
    scanf("%d", &n);
    double nx = 0, ny = 0;
    for (int i = 1; i <= n + 1; ++i) {
        for (int j = 0; j < n + 2 - i; ++j) {
            double ux = nx + j * 2 * sqrt(3);
            ++tot;
            x[tot] = ux;
            y[tot] = ny;
        }
        ny += 3; nx += sqrt(3);
    }
    for (int i = 1; i <= tot; ++i) {
        printf("x = %.2f, y = %.2f\n", x[i], y[i]);
    }
    int cnt = 0;
    for (int i = 1; i <= tot; ++i) {
        for (int j = i + 1; j <= tot; ++j) {
            for (int k = j + 1; k <= tot; ++k) {
                double a = dist(i, j);
                double b = dist(i, k);
                double c = dist(j, k);
                if (equal(a, b) && equal(b, c) && equal(c, a)) ++cnt;
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}

然后我们可以根据前几项的结果进行猜想，可以往三个方向考虑：

  • 多次差分之后为等差数列的，通项公式为多项式
  • 多次差分之后增长规律几乎不变并为指数级增长的，可能是齐次线性递推
  • 否则可能是非齐次线性递推

这里我们发现多次差分之后是一个等差数列，考虑待定系数求解多项式的系数，这里可以使用高斯消元的方法：

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
67
68
69
70
71
72
73
74
75
76
class AugMatrix:
    def __init__(self, row, col):
        self.row, self.col = row, col
        self.mtr = [[0] * (col + 1) for i in range(row)]
    def fillAt(self, row, col, val):
        self.mtr[row][col] = val
    def fillAugAt(self, row, val):
        self.mtr[row][self.col] = val
    def fill(self, mtr, augMtr):
        for i in range(self.row):
            for j in range(self.col):
                self.mtr[i][j] = mtr[i][j]
            self.mtr[i][self.col] = augMtr[i]
    def printMtr(self):
        for i in range(self.row):
            print(self.mtr[i])
    @staticmethod
    def gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    def rowMul(self, row, val):
        for i in range(self.col + 1):
            self.mtr[row][i] = self.mtr[row][i] * val
    def rowSub(self, rowA, rowB):
        for i in range(self.col + 1):
            self.mtr[rowA][i] = self.mtr[rowA][i] - self.mtr[rowB][i]
    def eliminate(self):
        for i in range(self.col - 1):
            for j in range(self.row - 1, i, -1):
                now, pre = self.mtr[j][i], self.mtr[j - 1][i]
                if now == 0:
                    continue
                elif pre == 0:
                    self.mtr[j], self.mtr[j - 1] = self.mtr[j - 1], self.mtr[j]
                    continue
                gcd = self.gcd(now, pre)
                lcm = now * pre // gcd
                self.rowMul(j, lcm // now)
                self.rowMul(j - 1, lcm // pre)
                self.rowSub(j, j - 1)
        for i in range(self.col - 1, 0, -1):
            for j in range(0, i):
                now, pre = self.mtr[j][i], self.mtr[j + 1][i]
                if now == 0 or pre == 0:
                    continue
                gcd = self.gcd(now, pre)
                lcm = now * pre // gcd
                self.rowMul(j, lcm // now)
                self.rowMul(j + 1, lcm // pre)
                self.rowSub(j, j + 1)
    def approximate(self):
        for i in range(self.row):
            g = self.gcd(self.mtr[i][self.col], self.mtr[i][i])
            self.mtr[i][self.col] = self.mtr[i][self.col] // g
            self.mtr[i][i] = self.mtr[i][i] // g
    def simplify(self):
        for i in range(self.row):
            self.mtr[i][self.col] = self.mtr[i][self.col] / self.mtr[i][i]
            self.mtr[i][i] = 1
    def generate(self):
        ret = list()
        for i in range(self.row):
            ret.append(self.mtr[i][self.col])
        return ret
n = 7
x = [1, 2, 3, 4, 5, 6, 7]
y = [1, 5, 15, 35, 70, 126, 210]
m = AugMatrix(n, n)
for i in range(7):
    for j in range(7):
        m.fillAt(i, j, x[i] ** j)
    m.fillAugAt(i, y[i])
m.eliminate()
m.approximate()
m.printMtr()

接着通过前七项解出了系数\((0, \frac{1}{4}, \frac{11}{24}, \frac{1}{4}, \frac{1}{24}, 0, 0, 0)\)，得到： \[f(x) = \frac{1}{4} x + \frac{11}{24} x^2 + \frac{1}{4} x^3 + \frac{1}{24} x^4 \] 最后通过多算几项验证正确性后，得到了最终的程序：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL P = LL(1E9) + 7;
LL inv_4, inv_24;
inline LL getPow(LL x, LL y) {
    LL ret = 1;
    while (y) {
        if (y & 1) ret = ret * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return ret;
}
inline LL f(LL x) {
    LL ret = 0, base = x;
    ret = (ret + inv_4 * base) % P; base = base * x % P;
    ret = (ret + 11 * inv_24 * base) % P; base = base * x % P;
    ret = (ret + inv_4 * base) % P; base = base * x % P;
    ret = (ret + inv_24 * base) % P;
    return ret;
}
int main() {
    inv_4 = getPow(4, P - 2);
    inv_24 = getPow(24, P - 2);
    int T, n;
    scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d", &n);
        printf("%lld\n", f(n));
    }
    return 0;
}

发表于 更新于 分类于 阅读次数：

手撸了一份，推公式用。

如果\(f(x)\)为多项式，即满足 \[f(x) = \sum_{i=0}^{n} a_i x^i\] 我们可以通过打表找出\(n+1\)个点值，然后用待定系数法求解。我们可以得到这样一个方程 \[\begin{bmatrix} x_0^0 & x_0^1 & \cdots & x_0^n  \\x_1^0 & x_1^1 & \cdots & x_1^n\\ \vdots & \vdots & \ddots & \vdots \\ x_n^0 & x_n^1 & \cdots & x_n^n \end{bmatrix} \cdot \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{bmatrix} =\begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix}\] 那么我们可以通过系数矩阵\(\boldsymbol X\)和\(\vec y\)向量来构造增广矩阵\([{\boldsymbol X} | \vec y ]\)，进而通过高斯消元法求解待定系数。

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
class AugMatrix:
    def __init__(self, row, col):
        self.row, self.col = row, col
        self.mtr = [[0] * (col + 1) for i in range(row)]
    def fillAt(self, row, col, val):
        self.mtr[row][col] = val
    def fillAugAt(self, row, val):
        self.mtr[row][self.col] = val
    def fill(self, mtr, augMtr):
        for i in range(self.row):
            for j in range(self.col):
                self.mtr[i][j] = mtr[i][j]
            self.mtr[i][self.col] = augMtr[i]
    def printMtr(self):
        for i in range(self.row):
            print(self.mtr[i])
    @staticmethod
    def gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    def rowMul(self, row, val):
        for i in range(self.col + 1):
            self.mtr[row][i] = self.mtr[row][i] * val
    def rowSub(self, rowA, rowB):
        for i in range(self.col + 1):
            self.mtr[rowA][i] = self.mtr[rowA][i] - self.mtr[rowB][i]
    def eliminate(self):
        for i in range(self.col - 1):
            for j in range(self.row - 1, i, -1):
                now, pre = self.mtr[j][i], self.mtr[j - 1][i]
                if now == 0:
                    continue
                elif pre == 0:
                    self.mtr[j], self.mtr[j - 1] = self.mtr[j - 1], self.mtr[j]
                    continue
                gcd = self.gcd(now, pre)
                lcm = now * pre // gcd
                self.rowMul(j, lcm // now)
                self.rowMul(j - 1, lcm // pre)
                self.rowSub(j, j - 1)
        for i in range(self.col - 1, 0, -1):
            for j in range(0, i):
                now, pre = self.mtr[j][i], self.mtr[j + 1][i]
                if now == 0 or pre == 0:
                    continue
                gcd = self.gcd(now, pre)
                lcm = now * pre // gcd
                self.rowMul(j, lcm // now)
                self.rowMul(j + 1, lcm // pre)
                self.rowSub(j, j + 1)
    def approximate(self):
        for i in range(self.row):
            g = self.gcd(self.mtr[i][self.col], self.mtr[i][i])
            self.mtr[i][self.col] = self.mtr[i][self.col] // g
            self.mtr[i][i] = self.mtr[i][i] // g
    def simplify(self):
        for i in range(self.row):
            self.mtr[i][self.col] = self.mtr[i][self.col] / self.mtr[i][i]
            self.mtr[i][i] = 1
    def generate(self):
        ret = list()
        for i in range(self.row):
            ret.append(self.mtr[i][self.col])
        return ret

发表于 更新于 分类于 阅读次数：

题目链接：HDU 6695

题目要求把元素分成两个集合\(A,B\)，一个集合只能用\(x\)属性，另一个只能用\(y\)属性，要求\(\min | \max A_i(x)- \max B_i(x) |\)

以\(x\)属性为关键字进行排序（从小到大），从前往后枚举，假设第\(i\)个放在第一个集合里且是最大的，后面的元素就只能放在第二个集合里面。

讨论\(B\)集合中最大的元素是什么，假设\(m\)为\(y[i+1 \cdots n]\)的后缀最大值，如果\(x_i \leq m\)，那么一定是选择\(m\)，否则可以在前面的\(y\)当中选最接近\(x_i\)的，具体方法是在平衡树中二分。

这种固定一个求另一个的方法是一种常见方法。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
struct Node {
    LL x, y;
    inline void input() {
        scanf("%lld%lld", &x, &y);
    }
    friend bool operator < (const Node &u, const Node &v) {
        return u.x < v.x;
    }
} a[MAX_N];
LL T, n, suf[MAX_N];
multiset <LL> s;
inline LL getAbs(LL u) {
    return u < 0 ? -u : u;
}
void cal() {
    LL minDelt = LL(1E18);
    for (int i = 1; i <= n; ++i) {
        LL sufMax = suf[i + 1];
        LL now = a[i].x;
        if (now <= sufMax) minDelt = min(minDelt, getAbs(now - sufMax));
        else {
            auto minIt = s.lower_bound(now);
            if (i != n) minDelt = min(minDelt, getAbs(now - sufMax));
            if (minIt == s.end()) {
                if (s.size()) {
                    --minIt;
                    if (*minIt > sufMax) minDelt = min(minDelt, getAbs(now - *minIt));
                }
            } else {
                if (*minIt > sufMax) minDelt = min(minDelt, getAbs(now - *minIt));
                if (minIt != s.begin()) {
                    --minIt;
                    if (*minIt > sufMax) minDelt = min(minDelt, getAbs(now - *minIt));
                }
            }
        }
        s.insert(a[i].y);
    }
    printf("%lld\n", minDelt);
}
int main() {
    scanf("%lld", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%lld", &n);
        for (int i = 1; i <= n; ++i) a[i].input();
        sort(a + 1, a + n + 1);
        suf[n + 1] = -1;
        for (int i = n; i >= 1; --i) suf[i] = max(a[i].y, suf[i + 1]);
        s.clear();
        cal();
    }
    return 0;
}

发表于 更新于 分类于 阅读次数：

题目链接：Codeforces 1132C

首先预处理所有的询问，统计每个段有多少个人涂，即对每个\([l_i, r_i]\)区间加一。

我们需要\(q-2\)个人，反向考虑我们删掉哪两个。枚举删掉的第一个，把他的区间贡献从预处理的数组中删去，然后用一个新的数组\(c\)来记录哪些点只有一个人涂，即\(c_i = [a_i = 1]\)。接着我们去枚举除了第一个人之外的所有人，如果把他们删掉，那么会有多少个点变成0，即对\(c_i\)求前缀和，这个值为\(pre[r_i] - pre[l_i - 1]\)。我们希望这个值尽可能的小，因此最小的那个就是我们要删除的第二个点。

这种固定一个（枚举），求另一个的方法是一种常用方法。

时间复杂度\(O(nq + q^2)\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 5000 + 5;
int n, q, ans, l[MAX_N], r[MAX_N], itv[MAX_N], c[MAX_N];
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= q; ++i) scanf("%d%d", l + i, r + i);
    for (int i = 1; i <= q; ++i) {
        for (int j = l[i]; j <= r[i]; ++j) {
            ++itv[j];
        }
    }
    for (int i = 1; i <= q; ++i) {
        for (int j = l[i]; j <= r[i]; ++j) --itv[j];
        int sum = 0;
        for (int j = 1; j <= n; ++j) {
            c[j] = (itv[j] == 1) + c[j - 1];
            sum += (itv[j] > 0);
        }
        int minWork = INT_MAX;
        for (int j = 1; j <= q; ++j) {
            if (i == j) continue;
            minWork = min(minWork, c[r[j]] - c[l[j] - 1]);
        }
        ans = max(sum - minWork, ans);
        for (int j = l[i]; j <= r[i]; ++j) ++itv[j];
    }
    printf("%d\n", ans);
    return 0;
}