Difference between revisions of "BreakFast:2021HDU暑期多校训练营1"

Jump to navigation Jump to search

BreakFast:2021HDU暑期多校训练营1 (view source)

Revision as of 21:58, 29 July 2021

27,240 bytes added ,  21:58, 29 July 2021
update AEFGHIJK
(add week 6 contest)
 
(update AEFGHIJK)
Line 1: Line 1:
__TOC__
== Replay ==
== Replay ==


== Problem A ==
https://img-blog.csdnimg.cn/img_convert/ecc6f404c8f1f5c2f0a56f55844d8857.gif
 
== [https://acm.hdu.edu.cn/showproblem.php?pid=6950 Problem A. Mod, Or and Everything] ==
 
=== 题目大意 ===
 
<math display="inline">T</math> 组输入，每组一个整数 <math display="inline">n</math>，求 <math display="inline">(n \; mod \; 1) \; OR \; (n \; mod \; 2) \; OR \; \cdots \; OR \; (n \; mod \; n)</math>.
 
<math display="inline">1 \leq T \leq 5000, 1 \leq n \leq 10^{12}</math>.
 
=== 分析 ===
 
<s>分析个啥，直接打表找规律.</s>
 
=== 代码实现 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)1e5;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
 
void work()
{
//    for(int i = 1; i <= 100; ++i)
//    {
//        int s = 0;
//        for(int j = 1; j <= i; ++j) s |= i % j;
//        printf("%d: %d\n", i, s);
//    }
    ll n; scanf("%lld", &n);
    if(n == 1)
    {
        printf("0\n");
        return;
    }
    for(ll i = 0; ; ++i)
    {
        if(((1ll<<i) < n) && n <= ((1ll<<i+1)))
        {
            printf("%lld\n", (1ll<<i) - 1);
            break;
        }
    }
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
    return 0;
}</syntaxhighlight>
[https://acm.hdu.edu.cn/showproblem.php?pid=6951 Problem B. Rocket land]
 
[https://acm.hdu.edu.cn/showproblem.php?pid=6952 Problem C. Puzzle loop]
 
[https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop]
 
== [https://acm.hdu.edu.cn/showproblem.php?pid=6954 Problem E. Minimum spanning tree] ==
 
=== 题目大意 ===
 
<math display="inline">T</math> 组输入，每组给出一个 <math display="inline">n</math>.
 
点的编号为 <math display="inline">1, 2, \cdots, n</math>，点 <math display="inline">a</math> 与 点 <math display="inline">b</math> 的权值定义为 <math display="inline">lcm(a, b)</math>.
 
求这个图的最小生成树.
 
<math display="inline">1 \leq T \leq 10^2, 2 \leq n \leq 10^7</math>.
 
=== 分析 ===
 
显然合数与它的因子连边，质数与 <math display="inline">2</math> 连边最优.
 
=== 代码实现 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)1e7;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
 
int cnt, prime[M + 5];
bool is_prime[M + 5];
ll f[M + 5];
 
void init()
{
    memset(is_prime, 1, sizeof(is_prime));
    cnt = is_prime[0] = is_prime[1] = 0;
    for(int i = 2; i <= M; ++i)
    {
        if(is_prime[i]) prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
        {
            is_prime[i * prime[j]] = 0;
            if(i % prime[j] == 0) break;
        }
    }
    f[2] = 0;
    for(int i = 3; i <= M; ++i)
    {
        if(is_prime[i]) f[i] = f[i - 1] + 2 * i;
        else            f[i] = f[i - 1] + i;
    }
}
 
void work()
{
    int n; scanf("%d", &n);
    printf("%lld\n", f[n]);
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    init();
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
    return 0;
}</syntaxhighlight>
== [https://acm.hdu.edu.cn/showproblem.php?pid=6955 Problem F. Xor sum] ==
 
=== 题目大意 ===
 
<math display="inline">T</math> 组输入，每组输入有两个整数 <math display="inline">n</math> 和 <math display="inline">k</math>，接下来 <math display="inline">n</math> 个整数表示 <math display="inline">a[1], a[2], \cdots, a[n]</math>.
 
要求找一段区间，使得这段区间的异或和不小于 <math display="inline">k</math>，若不存在则输出 <math display="inline">-1</math>，存在则找到满足上述条件最短的区间，若仍不唯一，则输出最靠左的区间.
 
<math display="inline">1 \leq T \leq 10^2, 1 \leq n \leq10^5, 0 \leq k, a[i] < 2^{30}</math>.
 
=== 分析 ===
 
记 <math display="inline">s[i] = a[1] \; XOR \; a[2] \; XOR \; \cdots \; XOR \;a[i]</math>.
 
则区间 <math display="inline">[l, r]</math> 异或和不小于 <math display="inline">k</math> 等价于 <math display="inline">s[r] \; XOR \; s[l-1]</math> 不小于 <math display="inline">k</math>.
 
因此字典树维护 <math display="inline">s[i]</math>，节点记录当前最新的时间戳，对于两边都能走的情况就选择最新的时间戳走.
 
详见代码.
 
=== 代码实现 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)1e5;
const int N = (int)29;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
 
struct tnode
{
    int nx[2], stamp;
} tree[M * 31 + 5];
int cnt;
 
int n, k;
 
void insert(int p, int d, int x, int stamp)
{
    if(d == -1) return;
    int v = (x>>d&1);
    if(!tree[p].nx[v])
    {
        tree[p].nx[v] = ++cnt;
        tree[tree[p].nx[v]].nx[0] = 0;
        tree[tree[p].nx[v]].nx[1] = 0;
        tree[tree[p].nx[v]].stamp = 0;
    }
    tree[p].stamp = stamp;
    insert(tree[p].nx[v], d - 1, x, stamp);
    if(d == 0)
    {
        tree[tree[p].nx[v]].stamp = stamp;
    }
}
 
inline int setZero(int x, int k)
{
    return x&(~(1<<k));
}
 
inline int setOne(int x, int k)
{
    return x|(1<<k);
}
 
int queryMx(int x, int p, int d)
{
    for(int i = d, v; i >= 0; --i)
    {
        v = (x>>i&1);
        if(tree[p].nx[!v]) p = tree[p].nx[!v], x = setOne(x, i);
        else              p = tree[p].nx[v], x = setZero(x, i);
    }
    return x;
}
 
int mi, l, r;
 
void query(int x, int stamp, bool f = 0)
{
    int p = 0;
    for(int i = N, vk, vx; i >= 0; --i)
    {
        vk = (k>>i&1);
        vx = (x>>i&1);
        bool canZero = 0, canOne = 0;
        if(tree[p].nx[vx])  canZero = queryMx(setZero(x, i), tree[p].nx[vx], i - 1) >= k;
        if(tree[p].nx[!vx]) canOne = queryMx(setOne(x, i), tree[p].nx[!vx], i - 1) >= k;
        if(canZero && canOne)
        {
            if(tree[tree[p].nx[vx]].stamp > tree[tree[p].nx[!vx]].stamp) p = tree[p].nx[vx], x = setZero(x, i);
            else                                                        p = tree[p].nx[!vx], x = setOne(x, i);
        }
        else if(canZero)    p = tree[p].nx[vx], x = setZero(x, i);
        else if(canOne)    p = tree[p].nx[!vx], x = setOne(x, i);
        else                return;
    }
    if(mi > stamp - tree[p].stamp)
    {
        mi = stamp - tree[p].stamp;
        l = tree[p].stamp + 1, r = stamp;
    }
}
 
void work()
{
    mi = inf, l = -1, r = -1;
    cnt = tree[0].nx[0] = tree[0].nx[1] = tree[0].stamp = 0;
    scanf("%d %d", &n, &k);
    insert(0, N, 0, 0);
    int s = 0;
    for(int i = 1, a; i <= n; ++i)
    {
        scanf("%d", &a);
        s ^= a;
        query(s, i);
        insert(0, N, s, i);
    }
    if(mi == inf) printf("-1\n");
    else          printf("%d %d\n", l, r);
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
    return 0;
}</syntaxhighlight>
== [https://acm.hdu.edu.cn/showproblem.php?pid=6956 Problem G. Pass!] ==
 
=== 题目大意 ===
 
<math display="inline">T</math> 组输入，每组有两个整数 <math display="inline">n</math> 和 <math display="inline">x</math>.
 
一共有 <math display="inline">n</math> 个人和 <math display="inline">1</math> 个球，初始球在第 <math display="inline">1</math> 人脚下，每秒拥有球的那个人会把球传给另一个人.
 
经过 <math display="inline">t</math> 秒后，球又回到了第 <math display="inline">1</math> 个人脚下，方案数为 <math display="inline">x</math>.
 
现在给出 <math display="inline">x</math> 要求反解最小非负整数 <math display="inline">t</math>.
 
=== 分析 ===
 
设 <math display="inline">f[i][0]</math> 表示第 <math display="inline">i</math> 秒末球不在第 <math display="inline">1</math> 个人脚下的方案数，<br />
<math display="inline">\quad f[i][1]</math> 表示第 <math display="inline">i</math> 秒末球在第 <math display="inline">1</math> 个人脚下的方案数.
 
则有如下转移方程：
 
<math display="block">\left\{
\begin{aligned}
f[0][1] &= 1 \\
f[i][0] &= (n - 2)f[i - 1][0] + (n - 1)f[i - 1][1] \\
f[i][1] &= f[i - 1][0]
\end{aligned}
\right.
\rightarrow
\left\{
\begin{aligned}
f[1][0] &= n - 1 \\
f[2][0] &= (n - 1)(n - 2) \\
f[i][0] &= (n - 2)f[i - 1][0] + (n - 1)f[i - 2][0] \quad i \geq 3\\
\end{aligned}
\right.</math>
学了一下[https://zhuanlan.zhihu.com/p/104596563 二阶线性递推式的通项求法]，<s>夙愿清单减减.</s>
 
于是可以得到 <math display="inline">f[i][0]</math> 的解析式为 <math display="inline">f[i][0] = \frac{(n -1)^2}{n}(n-1)^{i - 1} + \frac{n - 1}{n}(-1)^{i - 1}</math>.
 
又由 <math display="inline">f[i][1] = f[i - 1][0]</math> 得
 
<math display="block">\begin{aligned}
f[i][1] &= f[i - 1][0] \\
&= \frac{(n -1)^2}{n}(n-1)^{i - 2} + \frac{n - 1}{n}(-1)^{i - 2} \quad i \geq 0 \\
&=
\left\{
\begin{aligned}
\frac{(n -1)^i}{n} &- \frac{n - 1}{n} \quad i \; is \; odd \\
\frac{(n -1)^i}{n} &+ \frac{n - 1}{n} \quad i \; is \; even \\
\end{aligned}
\right. \\
&=
\left\{
\begin{aligned}
\frac{(n -1)^{2k+1}}{n} &- \frac{n - 1}{n} \quad i = 2k+1, k \geq  0\\
\frac{(n -1)^{2k}}{n} &+ \frac{n - 1}{n} \quad i = 2k, k \geq  0\\
\end{aligned}
\right. \\
&\stackrel{Only \; need \; to \; solve}{\longrightarrow}
\left\{
\begin{aligned}
(n-1)^{2k} &\equiv \frac{nx + n - 1}{n - 1} \; (mod\; p) \\
(n-1)^{2k} &\equiv nx - n + 1\; (mod \; p) \\
\end{aligned}
\right. \\
\end{aligned}</math>
至此套上 BSGS 即可.
 
=== 代码实现 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)1e5;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
 
struct hashTable
{
    const static int M = (int)1e5;
    const static int N = (int)31601;
    int head[N + 5], cnt;
 
    struct node
    {
        int v, w, nx;
    } a[M + 5];
 
    void init()
    {
        cnt = 0;
        memset(head, -1, sizeof(head));
    }
 
    void add(int v, int w)
    {
        for(int i = head[w % N]; ~i; i = a[i].nx)
        {
            if(a[i].w == w)
            {
                a[i].v = v;
                return;
            }
        }
        a[cnt].v = v;
        a[cnt].w = w;
        a[cnt].nx = head[w % N];
        head[w % N] = cnt++;
    }
 
    int tofind(int w)
    {
        for(int i = head[w % N]; ~i; i = a[i].nx)
        {
            if(a[i].w == w) return a[i].v;
        }
        return -1;
    }
} H;
 
struct LOG
{
    ll quick(ll a, ll b, ll p = mod)
    {
        ll s = 1;
        while(b)
        {
            if(b & 1) s = s * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return s;
    }
 
    ll inv(ll n, ll p = mod)
    {
        return quick(n, p - 2, p);
    }
 
    int k = 31596, t;
 
    void init(int a, int p)
    {
        H.init();
        for(int i = 0, j = 1; i < k; ++i)
        {
            H.add(i, j);
            j = 1ll * j * a % p;
        }
        t = quick(a, k, p);
    }
 
    int BSGS(int a, int b, int p)
    {
        a = (1ll * a % p + p) % p, b = (1ll * b % p + p) % p;
        if(b == 1)  return 0;
        for(int i = 1, j = t * inv(b, p) % p, h; i <= k; ++i)
        {
            h = H.tofind(j);
            if(~h && 1ll * k * i > h && !((1ll * k * i - h)&1)) return 1ll * k * i - h;
            j = 1ll * j * t % p;
        }
        return -1;
    }
} B;
 
int n, x;
 
int calOdd()
{
    int a = (1ll * n * x % mod + n - 1 + mod) % mod * B.inv(n - 1) % mod;
    int x = B.BSGS(n - 1, a, mod);
    if(x == -1) return inf;
    return x + 1;
}
 
int calEven()
{
    int a = (1ll * n * x % mod - n + 1 + mod) % mod;
    int x = B.BSGS(n - 1, a, mod);
    if(x == -1) return inf;
    return x;
}
 
void work()
{
    scanf("%d %d", &n, &x);
    B.init(n - 1, mod);
    int odd = calOdd(), even = calEven();
    int mi = min(odd ,even);
    if(mi == inf)  printf("-1\n");
    else            printf("%d\n", mi);
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}</syntaxhighlight>
== [https://acm.hdu.edu.cn/showproblem.php?pid=6957 Problem H. Maximal submatrix] ==
 
=== 题目大意 ===
 
<math display="inline">T</math> 组输入，每组输入一个 <math display="inline">n \times m</math> 的矩阵.
 
求一个最大子矩阵，这个子矩阵每一列中的元素递增，输出最大子矩阵的大小.
 
<math display="inline">1 \leq T \leq 10, 1 \leq n, m \leq 2000</math>.
 
=== 分析 ===
 
单调栈经典题了.
 
=== 代码实现 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)2e3;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
 
int n, m;
int a[M + 5][M + 5];
int b[M + 5][M + 5];
 
int s[M + 5], w[M + 5], p;
 
int cal(int a[])
{
    a[m + 1] = p = 0;
    int ans = 0;
    for(int i = 1; i <= m + 1; ++i)
    {
        if(a[i] > s[p])
        {
            s[++p] = a[i], w[p] = 1;
        }
        else
        {
            int width = 0;
            while(s[p] > a[i])
            {
                width += w[p];
                ans = max(ans, width * s[p]);
                p--;
            }
            s[++p] = a[i], w[p] = width + 1;
        }
    }
    return ans;
}
 
void work()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
    for(int j = 1; j <= m; ++j)
    {
        b[1][j] = 1;
        for(int i = 2; i <= n; ++i)
        {
            if(a[i][j] >= a[i - 1][j]) b[i][j] = b[i - 1][j] + 1;
            else                      b[i][j] = 1;
        }
    }
    int mx = 0;
    for(int i = 1; i <= n; ++i)
    {
        mx = max(mx, cal(b[i]));
    }
    printf("%d\n", mx);
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
    return 0;
}</syntaxhighlight>
== [https://acm.hdu.edu.cn/showproblem.php?pid=6958 Problem I. KD-Graph] ==
 
=== 题目大意 ===
 
<math display="inline">T</math> 组输入，每组输入 <math display="inline">n, m, k</math> 表示 <math display="inline">n</math> 个点 <math display="inline">m</math> 条边的有权联通无向图.
 
接下来 <math display="inline">m</math> 行，每行三个整数 <math display="inline">u, v, w</math> 表示无向边的两个端点和边权.
 
一个图被称为 KD 图当且仅当 <math display="inline">n</math> 个点可以不重不漏地分成 <math display="inline">K</math> 组且组内两两点之间存在一条路径，满足这条路径的最大边权小于等于 <math display="inline">D</math>，不同组的每两点则不存在这样的路径.
 
要求计算最小的非负整数 <math display="inline">D</math>，若不存在输出 <math display="inline">-1</math>.
 
=== 分析 ===
 
赛时一开始二分 + BFS，结果 TLE...
 
换成二分 + 并查集，常数小了点，得到 AC.
 
=== 代码实现 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
 
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)1e5;
const int N = (int)5e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
 
int n, m, k;
 
struct enode
{
    int u, v, w;
} Edge[N + 5];
 
int fa[M + 5];
int rk[M + 5];
 
int tofind(int x)
{
    if(x == fa[x])  return x;
    return fa[x] = tofind(fa[x]);
}
 
int cal(int lim)
{
    for(int i = 1; i <= n; ++i) fa[i] = i;
    for(int i = 1, u, v; i <= m; ++i)
    {
        u = Edge[i].u, v = Edge[i].v;
        if(Edge[i].w <= lim)
        {
            u = tofind(u), v = tofind(v);
            if(u != v)
            {
                if(rk[u] > rk[v]) swap(u, v);
                fa[u] = v, rk[v] = max(rk[v], rk[u] + 1);
            }
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; ++i) if(fa[i] == i)  ++cnt;
    return cnt;
}
 
void work()
{
    n = read(), m = read(), k = read();
    int l = 0, r = 0, mid;
    for(int i = 1; i <= m; ++i)
    {
        Edge[i].u = read(), Edge[i].v = read(), Edge[i].w = read();
        r = max(r, Edge[i].w);
    }
    while(l < r)
    {
        mid = (l + r) >> 1;
        if(cal(mid) <= k)  r = mid;
        else                l = mid + 1;
    }
    if(cal(r) == k) printf("%d\n", r);
    else            printf("-1\n");
}
 
int main()
{
//    cout << 5 * log2(inf) * (M + 2 * N) << "\n";
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T = read();
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}</syntaxhighlight>
== [https://acm.hdu.edu.cn/showproblem.php?pid=6959 Problem J. zoto] ==
 
=== 题目大意 ===
 
<math display="inline">T</math> 组输入，每组输入 <math display="inline">n, m</math> 表示二维平面上有 <math display="inline">n</math> 个整数点和 <math display="inline">m</math> 次询问.
 
接下来 <math display="inline">n</math> 行，每行一个非负整数 <math display="inline">fx[i]</math>，表示有一个整数点 <math display="inline">(i, fx[i])</math>.
 
接下来 <math display="inline">m</math> 行，每行四个整数 <math display="inline">x0, y0, x1, y1</math> 表示查询 <math display="inline">(x0, y0)</math> 与 <math display="inline">(x1, y1)</math> 围成的矩阵里有多少个不同的 <math display="inline">y</math> 值.
 
<math display="inline">1 \leq T \leq 5, 1 \leq n, m, x0, x1 \leq 10^5, 0 \leq  fx[i], y0, y1 \leq 10^5</math>.
 
=== 分析 ===
 
一开始用莫队 + 线段树喜提 TLE.
 
正解是莫队 + 分块.
 
分块支持 <math display="inline">O(1)</math> 修改 + <math display="inline">O(\sqrt{10^5})</math> 查询.
 
'''小收获：莫队的修改次数很多，查询次数较少，应选择修改较快的数据结构进行维护.'''
 
=== 代码实现 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
using namespace std;
 
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
 
void print(int n)
{
    if(n < 0)
    {
        putchar('-');
        print(-n);
    }
    else
    {
        if(n > 9) print(n / 10);
        putchar(n % 10 + '0');
    }
}
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)1e5;
const int N = (int)320;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
 
int n, m, xblock, yblock, yblockCnt;
int a[M + 5];
int ans[M + 5];
 
struct qnode
{
    int l, r, a, b, id;
    bool operator<(const qnode& b)const
    {
        return l / xblock == b.l / xblock ? (r == b.r ? 0 : ((l / xblock) & 1) ^ (r < b.r)) : l < b.l;
    }
} q[M + 5];
 
int id[M + 5];
int num[M + 5];
int nums[N + 5];
int mx;
 
void init()
{
    yblock = (int)sqrt(mx), yblockCnt = (mx + yblock) / yblock;
    for(int i = 0; i <= mx; ++i)
    {
        id[i] = i / yblock;
        num[i] = 0;
    }
    for(int i = 0; i < yblockCnt; ++i) nums[i] = 0;
}
 
void add(int x)
{
    if(++num[a[x]] == 1) ++nums[id[a[x]]];
}
 
void del(int x)
{
    if(--num[a[x]] == 0) --nums[id[a[x]]];
}
 
int query(int l, int r)
{
    int ans = 0;
    if(id[r] - id[l] + 1 <= 2)
    {
        for(int i = l; i <= r; ++i) if(num[i]) ++ans;
    }
    else
    {
        for(int i = l; i <= n && id[i] == id[l]; ++i) if(num[i]) ++ans;
        for(int i = r; i >= 1 && id[i] == id[r]; --i) if(num[i]) ++ans;
        for(int i = id[l] + 1; i < id[r]; ++i) ans += nums[i];
    }
    return ans;
}
 
void work()
{
    n = read(), m = read(); xblock = (int)sqrt(n);
    for(int i = 1; i <= n; ++i) a[i] = read();
    mx = 1;
    for(int i = 1; i <= m; ++i)
    {
        q[i].l = read(), q[i].a = read(), q[i].r = read(), q[i].b = read();
        mx = max(mx, q[i].b);
        q[i].id = i;
    }
    init();
    sort(q + 1, q + m + 1);
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++i)
    {
        while(r < q[i].r) add(++r);
        while(r > q[i].r) del(r--);
        while(l < q[i].l) del(l++);
        while(l > q[i].l) add(--l);
        ans[q[i].id] = query(q[i].a, q[i].b);
    }
    for(int i = 1; i <= m; ++i) print(ans[i]), putchar('\n');
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}</syntaxhighlight>
== [https://acm.hdu.edu.cn/showproblem.php?pid=6960 Problem K. Necklace of Beads] ==
 
=== 题目大意 ===
 
<math display="inline">T</math> 组输入，每组给出 <math display="inline">n</math> 和 <math display="inline">k</math>.
 
有红蓝绿三种颜色的珠子，红蓝珠子有无穷多个，绿色珠子只有 <math display="inline">k</math> 个，要求串成 <math display="inline">n</math> 个珠子的项链.
 
两个项链如果可以通过旋转得到则认为是一种方案.
 
求方案数.
 
<math display="inline">1 \leq T \leq 10, 1 \leq n, k \leq 10^6</math>.
 
=== 分析 ===
 
显然Burnside 引理，于是
 
<math display="block">\begin{aligned}
ANS &= \frac{1}{n}\sum_{i=0}^{n - 1}{\sum_{j=0}^{\lfloor \frac{k}{n/gcd(n, i)} \rfloor}{f(gcd(n, i), j)}} \\
&= \frac{1}{n}\sum_{d=1}^{n}{\varphi(\frac{n}{d})\sum_{j=0}^{\lfloor \frac{k}{n/d} \rfloor}{f(d, j)}}
\end{aligned}</math>
<math display="inline">f(n, m)</math> 表示长度为 <math display="inline">n</math> 的环，绿色珠子有 <math display="inline">m</math> 个的合法方案数.
 
<math display="inline">g(n, m)</math> 表示长度为 <math display="inline">n</math> 的序列，选 <math display="inline">m</math> 个互不相邻位置的方案数.
 
对绿色珠子的位置分类讨论：
 
# 假设绿色珠子放在 <math display="inline">1</math> 号位置，则 <math display="inline">2, n</math> 这两个位置不能放绿色珠子，并且绿色珠子把环分割为 <math display="inline">m</math> 段，每段的方案数为 <math display="inline">2</math>，因此总方案数为 <math display="inline">g(n - 3, m - 1) \times 2^{m}</math>.
# 假设绿色珠子放在 <math display="inline">n</math> 号位置，根据对称性，方案数同 <math display="inline">1.</math>
# 除上述两种情况之外，方案数为 <math display="inline">g(n - 2, m) \times 2^{m}</math>.
 
因此 <math display="inline">f(n, m) = g(n - 3, m - 1) \times 2^{m+1} + g(n - 2, m) \times 2^{m}</math>.
 
由插空法可得 <math display="inline">g(n, m) = \binom{n - m + 1}{m}</math>.
 
<math display="inline">O(10^6)</math> 预处理出欧拉函数和阶乘，逆元，阶乘逆元.
 
时间复杂度 <math display="inline">O(10^6 + T\sqrt{n})</math>.
 
=== 代码实现 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)1e6;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
 
bool is_prime[M + 5];
int cnt, prime[M + 5];
int phi[M + 5];
int fac[M + 5], inv[M + 5], invfac[M + 5];
 
void init()
{
    phi[1] = 1;
    memset(is_prime, 1, sizeof(is_prime));
    cnt = is_prime[0] = is_prime[1] = 0;
    fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;
    for(int i = 2; i <= M; ++i)
    {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod;
        if(is_prime[i])
        {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
        {
            is_prime[i * prime[j]] = 0;
            if(i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
 
int c(int n, int m)
{
    if(n < 0 || m < 0 || n < m) return 0;
    return 1ll * fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
 
void work()
{
    int n, k; scanf("%d %d", &n, &k);
    int ans = 0;
    for(int d = 1, two, r, f, dd; 1ll * d * d <= n; ++d)
    {
        if(n % d)  continue;
        two = 1, r = 1ll * k * d / n, f = (!(d&1)) * 2;
        for(int j = 1; j <= r; ++j)
        {
            two = 2ll * two% mod;
            f = (f + 2ll * two * c(d - j - 1, j - 1) + 1ll * two * c(d - j - 1, j)) % mod;
        }
        ans = (ans + 1ll * f * phi[n / d]) % mod;
        if(d * d == n)  continue;
        dd = n / d;
        two = 1, r = 1ll * k * dd / n, f = (!(dd&1)) * 2;
        for(int j = 1; j <= r; ++j)
        {
            two = 2ll * two% mod;
            f = (f + 2ll * two * c(dd - j - 1, j - 1) + 1ll * two * c(dd - j - 1, j)) % mod;
        }
        ans = (ans + 1ll * f * phi[n / dd]) % mod;
    }
    ans = 1ll * ans * inv[n] % mod;
    printf("%d\n", ans);
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    init();
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}</syntaxhighlight>
Retrieved from "https://wiki.soullan.com/index.php/Special:MobileDiff/214"

Navigation menu