BreakFast:2021HDU暑期多校训练营1

Replay

Problem A. Mod, Or and Everything

题目大意

${\textstyle T}$ 组输入，每组一个整数 ${\textstyle n}$，求 ${\textstyle (n\;mod\;1)\;OR\;(n\;mod\;2)\;OR\;\cdots \;OR\;(n\;mod\;n)}$.

${\textstyle 1\leq T\leq 5000,1\leq n\leq 10^{12}}$.

分析

分析个啥，直接打表找规律.

代码实现

#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;
}

Problem B. Rocket land

Problem C. Puzzle loop

题目大意

${\textstyle T}$ 组输入，每组输入一个大小为 ${\textstyle (n-1)\times (m-1)}$ 的地图，地图字符集为 ${\textstyle \{'0','1','.'\}}$.

${\textstyle '0'}$ 表示该格子周围四条边有偶数条红边.

${\textstyle '1'}$ 表示该格子周围四条边有奇数条红边.

${\textstyle '.'}$ 表示该格子周围四条边无限制.

要求红边形成若干个边不相交的环，求方案数.

${\textstyle 1\leq T\leq 100,1\leq n,m\leq 17}$.

分析

红边实质上就是若个干不相交的欧拉路嘛，因此要求每个交点的度为偶数，这样便满足了形成若干个边不相交的环这一条件.

此外对每个格子的四条边建异或方程.

于是得到异或方程组，高斯消元即可.

代码实现

#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)17;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;

int n, m;
char s[N + 5][N + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int row, col;
bool a[2 * (N + 1) * (N + 1) + 5][2 * N * (N + 1) + 5];

inline int id(int x1, int y1, int x2, int y2)
{
    if(x1 > x2) swap(x1, x2);
    if(y1 > y2) swap(y1, y2);
    if(x1 == x2) return (x1 - 1) * m + y1;
    else         return (n + 1) * m + (x1 - 1) * (m + 1) + y1;
}

void build()
{
    row = 0, col = (n + 1) * m + n * (m + 1);
    for(int i = 1; i <= n + 1; ++i)
    {
        for(int j = 1; j <= m + 1; ++j)
        {
            ++row;
            for(int k = 1; k <= col + 1; ++k) a[row][k] = 0;
            for(int k = 0, x, y; k < 4; ++k)
            {
                x = i + dx[k], y = j + dy[k];
                if(x < 1 || x > n + 1 || y < 1 || y > m + 1)    continue;
                a[row][id(x, y, i, j)] = 1;
            }
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(s[i][j] == '.') continue;
            ++row;
            for(int k = 1; k <= col + 1; ++k) a[row][k] = 0;
            a[row][id(i, j, i, j + 1)] = 1;
            a[row][id(i, j, i + 1, j)] = 1;
            a[row][id(i, j + 1, i + 1, j + 1)] = 1;
            a[row][id(i + 1, j, i + 1, j + 1)] = 1;
            a[row][col + 1] = s[i][j] - '0';
        }
    }
//    for(int i = 1; i <= row; ++i)
//    {
//        bool f = 0;
//        for(int j = 1; j <= col; ++j)
//        {
//            if(!a[i][j])    continue;
//            if(f) printf(" ^ ");
//            printf("x(%d)", j);
//            f = 1;
//        }
//        printf(" = 0\n");
//    }
}

int gauss(int n, int m)
{
    int c, r;
    for(c = 1, r = 1; c <= m; ++c)
    {
        int t = r;
        for(int i = r; i <= n; ++i)
        {
            if(a[i][c])   t = i;
        }
        if(!a[t][c]) continue;
        for(int i = c; i <= m + 1; ++i) swap(a[t][i], a[r][i]);
        for(int i = 1; i <= n; ++i)
        {
            if(i == r)  continue;
            if(a[i][c])
            {
                for(int j = m + 1; j >= c; --j)
                {
                    a[i][j] ^= a[r][j];
                }
            }
        }
        ++r;
    }
    for(int i = r; i <= n; ++i)
    {
        if(a[i][m + 1])   return -1;//无解
    }
    return m - r + 1;//自由元个数
}

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;
}

void work()
{
    scanf("%d %d", &n, &m);
    --n, --m;
    for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    build();
    int r = gauss(row, col);
    if(r == -1) printf("0\n");
    else        printf("%lld\n", quick(2, 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();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

bitset 优化

#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)17;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;

int n, m;
char s[N + 5][N + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int row, col;
bitset<614> a[2 * (N + 1) * (N + 1) + 5];

inline int id(int x1, int y1, int x2, int y2)
{
    if(x1 > x2) swap(x1, x2);
    if(y1 > y2) swap(y1, y2);
    if(x1 == x2) return (x1 - 1) * m + y1;
    else         return (n + 1) * m + (x1 - 1) * (m + 1) + y1;
}

void build()
{
    row = 0, col = (n + 1) * m + n * (m + 1);
    for(int i = 1; i <= n + 1; ++i)
    {
        for(int j = 1; j <= m + 1; ++j)
        {
            ++row;
            a[row].reset();
            for(int k = 0, x, y; k < 4; ++k)
            {
                x = i + dx[k], y = j + dy[k];
                if(x < 1 || x > n + 1 || y < 1 || y > m + 1)    continue;
                a[row].set(id(x, y, i, j));
            }
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(s[i][j] == '.') continue;
            ++row;
            a[row].reset();
            a[row].set(id(i, j, i, j + 1));
            a[row].set(id(i, j, i + 1, j));
            a[row].set(id(i, j + 1, i + 1, j + 1));
            a[row].set(id(i + 1, j, i + 1, j + 1));
            a[row].set(col + 1, s[i][j] - '0');
        }
    }
//    for(int i = 1; i <= row; ++i)
//    {
//        bool f = 0;
//        for(int j = 1; j <= col; ++j)
//        {
//            if(!a[i][j])    continue;
//            if(f) printf(" ^ ");
//            printf("x(%d)", j);
//            f = 1;
//        }
//        printf(" = 0\n");
//    }
}

int gauss(int n, int m)
{
    int c, r;
    for(c = 1, r = 1; c <= m; ++c)
    {
        int t = r;
        for(int i = r; i <= n; ++i)
        {
            if(a[i][c])   t = i;
        }
        if(!a[t][c]) continue;
        swap(a[t], a[r]);
        for(int i = 1; i <= n; ++i)
        {
            if(i == r)  continue;
            if(a[i][c]) a[i] ^= a[r];
        }
        ++r;
    }
    for(int i = r; i <= n; ++i)
    {
        if(a[i][m + 1])   return -1;//无解
    }
    return m - r + 1;//自由元个数
}

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;
}

void work()
{
    scanf("%d %d", &n, &m);
    --n, --m;
    for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    build();
    int r = gauss(row, col);
    if(r == -1) printf("0\n");
    else        printf("%lld\n", quick(2, 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();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

Problem D. Another thief in a Shop

题目大意

${\textstyle T}$ 组输入，每组给 ${\textstyle n}$ 和 ${\textstyle k}$.

有 ${\textstyle n}$ 个物品，价值分别为 ${\textstyle a[1],a[2],\cdots ,a[n]}$，每件物品有无穷多件.

求拼凑出总价值为 ${\textstyle k}$ 的方案数.

${\textstyle 1\leq T\leq 100,1\leq n\leq 100,1\leq k\leq 10^{18},1\leq a[i]\leq 10}$.

分析

设 ${\textstyle f[i][j]}$ 表示考虑了前 ${\textstyle i}$ 个物品，总价值为 ${\textstyle j}$ 的方案数.

则有状态转移方程 ${\textstyle {\begin{aligned}f[i][j]=\sum _{l=0}^{\lfloor {\frac {j}{a[i]}}\rfloor }{f[i-1][j-l\times a[i]]}\end{aligned}}}$.

接下来这一步被题解惊艳到了，拉格朗日插值！！！

但体会一下也就明白了，还是很妙的感觉.

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int M = (int)1e2;
const int N = (int)5e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

int n; ll k;
int a[M + 5];
int f[N + 5];
int y[M + 5];
int pre[M + 5];
int suf[M + 5];
int fac[M + 5];
int inv[M + 5];
int invfac[M + 5];

void init()
{
    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;
    }
}

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int Lagrange(int n, ll k)
{
    if(k <= n + 1) return y[k];
    pre[0] = 1;     for(int i = 1; i <= n + 1; ++i) pre[i] = (k - i) % mod * pre[i - 1] % mod;
    suf[n + 2] = 1; for(int i = n + 1; i >= 1; --i) suf[i] = (k - i) % mod * suf[i + 1] % mod;
    int ans = 0, cur;
    for(int i = 1; i <= n + 1; ++i)
    {
        cur = 1ll * pre[i - 1] * suf[i + 1] % mod * invfac[i - 1] % mod * invfac[n + 1 - i] % mod;
        if(n + 1 - i & 1) cur *= -1;
        cur = 1ll * cur * y[i] % mod;
        ans = (ans + cur) % mod;
    }
    ans = (ans % mod + mod) % mod;
    return ans;
}

void work()
{
    scanf("%d %lld", &n, &k);
    int lcm = 1;
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), lcm = lcm / gcd(lcm, a[i]) * a[i];
    memset(f, 0, sizeof(f)); f[0] = 1;
    int r = lcm * n;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = a[i]; j <= r; ++j) f[j] = (f[j] + f[j - a[i]]) % mod;
    }
    for(int i = k % lcm; i < r; i += lcm) y[i / lcm + 1] = f[i];
    printf("%d\n", Lagrange(n - 1, k / lcm + 1));
}

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;
}

Problem E. Minimum spanning tree

题目大意

${\textstyle T}$ 组输入，每组给出一个 ${\textstyle n}$.

点的编号为 ${\textstyle 1,2,\cdots ,n}$，点 ${\textstyle a}$ 与 点 ${\textstyle b}$ 的权值定义为 ${\textstyle lcm(a,b)}$.

求这个图的最小生成树.

${\textstyle 1\leq T\leq 10^{2},2\leq n\leq 10^{7}}$.

分析

显然合数与它的因子连边，质数与 ${\textstyle 2}$ 连边最优.

代码实现

#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;
}

Problem F. Xor sum

题目大意

${\textstyle T}$ 组输入，每组输入有两个整数 ${\textstyle n}$ 和 ${\textstyle k}$，接下来 ${\textstyle n}$ 个整数表示 ${\textstyle a[1],a[2],\cdots ,a[n]}$.

要求找一段区间，使得这段区间的异或和不小于 ${\textstyle k}$，若不存在则输出 ${\textstyle -1}$，存在则找到满足上述条件最短的区间，若仍不唯一，则输出最靠左的区间.

${\textstyle 1\leq T\leq 10^{2},1\leq n\leq 10^{5},0\leq k,a[i]<2^{30}}$.

分析

记 ${\textstyle s[i]=a[1]\;XOR\;a[2]\;XOR\;\cdots \;XOR\;a[i]}$.

则区间 ${\textstyle [l,r]}$ 异或和不小于 ${\textstyle k}$ 等价于 ${\textstyle s[r]\;XOR\;s[l-1]}$ 不小于 ${\textstyle k}$.

因此字典树维护 ${\textstyle s[i]}$，节点记录当前最新的时间戳，对于两边都能走的情况就选择最新的时间戳走.

详见代码.

代码实现

#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;
}

Problem G. Pass!

题目大意

${\textstyle T}$ 组输入，每组有两个整数 ${\textstyle n}$ 和 ${\textstyle x}$.

一共有 ${\textstyle n}$ 个人和 ${\textstyle 1}$ 个球，初始球在第 ${\textstyle 1}$ 人脚下，每秒拥有球的那个人会把球传给另一个人.

经过 ${\textstyle t}$ 秒后，球又回到了第 ${\textstyle 1}$ 个人脚下，方案数为 ${\textstyle x}$.

现在给出 ${\textstyle x}$ 要求反解最小非负整数 ${\textstyle t}$.

分析

设 ${\textstyle f[i][0]}$ 表示第 ${\textstyle i}$ 秒末球不在第 ${\textstyle 1}$ 个人脚下的方案数，
${\textstyle \quad f[i][1]}$ 表示第 ${\textstyle i}$ 秒末球在第 ${\textstyle 1}$ 个人脚下的方案数.

则有如下转移方程：

$$\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.$$

学了一下二阶线性递推式的通项求法，夙愿清单减减.

于是可以得到 ${\textstyle f[i][0]}$ 的解析式为 ${\textstyle f[i][0]={\frac {(n-1)^{2}}{n}}(n-1)^{i-1}+{\frac {n-1}{n}}(-1)^{i-1}}$.

又由 ${\textstyle f[i][1]=f[i-1][0]}$ 得

$${\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}}$$

至此套上 BSGS 即可.

代码实现

#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;
}

Problem H. Maximal submatrix

题目大意

${\textstyle T}$ 组输入，每组输入一个 ${\textstyle n\times m}$ 的矩阵.

求一个最大子矩阵，这个子矩阵每一列中的元素递增，输出最大子矩阵的大小.

${\textstyle 1\leq T\leq 10,1\leq n,m\leq 2000}$.

分析

单调栈经典题了.

代码实现

#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;
}

Problem I. KD-Graph

题目大意

${\textstyle T}$ 组输入，每组输入 ${\textstyle n,m,k}$ 表示 ${\textstyle n}$ 个点 ${\textstyle m}$ 条边的有权联通无向图.

接下来 ${\textstyle m}$ 行，每行三个整数 ${\textstyle u,v,w}$ 表示无向边的两个端点和边权.

一个图被称为 KD 图当且仅当 ${\textstyle n}$ 个点可以不重不漏地分成 ${\textstyle K}$ 组且组内两两点之间存在一条路径，满足这条路径的最大边权小于等于 ${\textstyle D}$，不同组的每两点则不存在这样的路径.

要求计算最小的非负整数 ${\textstyle D}$，若不存在输出 ${\textstyle -1}$.

分析

赛时一开始二分 + BFS，结果 TLE...

换成二分 + 并查集，常数小了点，得到 AC.

代码实现

#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;
}

Problem J. zoto

题目大意

${\textstyle T}$ 组输入，每组输入 ${\textstyle n,m}$ 表示二维平面上有 ${\textstyle n}$ 个整数点和 ${\textstyle m}$ 次询问.

接下来 ${\textstyle n}$ 行，每行一个非负整数 ${\textstyle fx[i]}$，表示有一个整数点 ${\textstyle (i,fx[i])}$.

接下来 ${\textstyle m}$ 行，每行四个整数 ${\textstyle x0,y0,x1,y1}$ 表示查询 ${\textstyle (x0,y0)}$ 与 ${\textstyle (x1,y1)}$ 围成的矩阵里有多少个不同的 ${\textstyle y}$ 值.

${\textstyle 1\leq T\leq 5,1\leq n,m,x0,x1\leq 10^{5},0\leq fx[i],y0,y1\leq 10^{5}}$.

分析

一开始用莫队 + 线段树喜提 TLE.

正解是莫队 + 分块.

分块支持 ${\textstyle O(1)}$ 修改 + ${\textstyle O({\sqrt {10^{5}}})}$ 查询.

小收获：莫队的修改次数很多，查询次数较少，应选择修改较快的数据结构进行维护.

代码实现

#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;
}

Problem K. Necklace of Beads

题目大意

${\textstyle T}$ 组输入，每组给出 ${\textstyle n}$ 和 ${\textstyle k}$.

有红蓝绿三种颜色的珠子，红蓝珠子有无穷多个，绿色珠子只有 ${\textstyle k}$ 个，要求串成 ${\textstyle n}$ 个珠子的项链.

两个项链如果可以通过旋转得到则认为是一种方案.

求方案数.

${\textstyle 1\leq T\leq 10,1\leq n,k\leq 10^{6}}$.

分析

显然Burnside 引理，于是

$${\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}}$$

${\textstyle f(n,m)}$ 表示长度为 ${\textstyle n}$ 的环，绿色珠子有 ${\textstyle m}$ 个的合法方案数.

${\textstyle g(n,m)}$ 表示长度为 ${\textstyle n}$ 的序列，选 ${\textstyle m}$ 个互不相邻位置的方案数.

对绿色珠子的位置分类讨论：

1. 假设绿色珠子放在 ${\textstyle 1}$ 号位置，则 ${\textstyle 2,n}$ 这两个位置不能放绿色珠子，并且绿色珠子把环分割为 ${\textstyle m}$ 段，每段的方案数为 ${\textstyle 2}$，因此总方案数为 ${\textstyle g(n-3,m-1)\times 2^{m}}$.
2. 假设绿色珠子放在 ${\textstyle n}$ 号位置，根据对称性，方案数同 ${\textstyle 1.}$
3. 除上述两种情况之外，方案数为 ${\textstyle g(n-2,m)\times 2^{m}}$.

因此 ${\textstyle f(n,m)=g(n-3,m-1)\times 2^{m+1}+g(n-2,m)\times 2^{m}}$.

由插空法可得 ${\textstyle g(n,m)={\binom {n-m+1}{m}}}$.

${\textstyle O(10^{6})}$ 预处理出欧拉函数和阶乘，逆元，阶乘逆元.

时间复杂度 ${\textstyle O(10^{6}+T{\sqrt {n}})}$.

代码实现

#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;
}