A 牛牛的mex运算

一.题目大意

$\quad$ 给出 $n$ 个数 $a[1..n]$ ， $q$ 次询问，每次给出 $l, r$ 并询问 $mex(a[l..r])$ .

$\quad$ $n,q \leq 10^5, 0 \leq a \leq n - 1$ 且 $a[i]$ 互异.

二.分析

$\quad$ 赛时用的莫队，看题解才发现自己写麻烦了.

$\quad$ 根据题目条件不难得 $a[]$ 是 $0..n-1$ 的一个排列.

$\quad$ 因此 $mex(a[l..r])=min(a[1..l-1], a[r+1..n])$ .

三.代码实现

1. 莫队

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

typedef unsigned long long ull;
typedef long long ll;

const int M = (int)1e5;
const int N = (int)5e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
const double eps = 1e-3;

int n, a[M + 5];
int q, block;

struct node
{
    int l, r, id, bl;

    bool operator< (const node& b)const
    {
        if(bl != b.bl) return bl < b.bl;
        return r < b.r;
    }
}s[M + 5];

int cur, ans[M + 5];
int cnt[M + 5];

void add(int x)
{
    ++cnt[a[x]];
    while(cnt[cur]) ++cur;
}

void sub(int x)
{
    --cnt[a[x]];
    if(!cnt[a[x]]) cur = min(cur, a[x]);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d", &n, &q); block = (int)sqrt(n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= q; ++i) scanf("%d %d", &s[i].l, &s[i].r), s[i].id = i, s[i].bl = s[i].l / block;
    sort(s + 1, s + q + 1);
    int l = 1, r = 0;
    for(int i = 1; i <= q; ++i)
    {
        while(r < s[i].r) ++r, add(r);
        while(r > s[i].r) sub(r), --r;
        while(l < s[i].l) sub(l), ++l;
        while(l > s[i].l) --l, add(l);
        ans[s[i].id] = cur;
    }
    for(int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
    return 0;
}

2. 简单操作

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

typedef unsigned long long ull;
typedef long long ll;

const int M = (int)1e5;
const int N = (int)5e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
const double eps = 1e-3;

int n, q, a[M + 5];
int pre[M + 5], suf[M + 5];

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d", &n, &q);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    pre[0] = n; for(int i = 1; i <= n; ++i) pre[i] = min(pre[i - 1], a[i]);
    suf[n + 1] = n; for(int i = n; i >= 1; --i) suf[i] = min(suf[i + 1], a[i]);
    int l, r;
    while(q--)
    {
        scanf("%d %d", &l, &r);
        printf("%d\n", min(pre[l - 1], suf[r + 1]));
    }
    return 0;
}

B 牛牛的算术

一.题目大意

$\quad$ T组询问，每组询问给出 $n$ ，求 $\begin{aligned} \prod_{i=1}^{n} \sum_{j=1}^i \sum_{k=1}^j ijk (mod \; 199999)\end{aligned}$

$\quad$ $\begin{aligned} \sum n \leq 10^{10^5} \end{aligned}$

二.分析

$\quad$ 化简可得 $\begin{aligned} \prod_{i=1}^{n} \sum_{j=1}^i \sum_{k=1}^j ijk = \prod_{i=1}^n [\frac{1}{8}i^5 + \frac{5}{12}i^4 + \frac{3}{8}i^3 + \frac{1}{12}i^2]\end{aligned}$ .

$\quad$ 很容易想到当 $n$ 大于某个值时，答案恒为 0. (打表可得当 $n \geq 66666$ 时，答案为 0.)

$\quad$ 那么直接搞就完事惹.

三.代码实现

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

typedef unsigned long long ull;
typedef long long ll;

const int M = (int)1e5;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)199999;
const double eps = 1e-3;

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

ll cal(int n)
{
    ll s = 0;
    s += inv(8) % mod * n % mod * n % mod * n % mod * n % mod * n % mod; s %= mod;
    s += 5 % mod * inv(12) % mod * n % mod * n % mod * n % mod * n % mod; s %= mod;
    s += 3 % mod * inv(8) % mod * n % mod * n % mod * n % mod; s %= mod;
    s += inv(12) % mod * n % mod * n % mod; s %= mod;
    return s;
}

char s[M + 5];

ll f[M + 5];

void init()
{
    f[0] = 1;
    for(int i = 1; i <= 100000; ++i)
    {
        f[i] = f[i - 1] * cal(i) % mod;
    }
    f[0] = 0;
}

void work()
{
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    if(len >= 6)
    {
        printf("0\n");
        return;
    }
    int n = 0;
    for(int i = 1; i <= len; ++i) n = n * 10 + s[i] - '0';
    printf("%lld\n", f[n]);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    init();
    int T; scanf("%d", &T);
    while(T--) work();
    return 0;
}

C 牛牛的无向图

一.题目大意

$\quad$ 给出 $n$ 个点 $m$ 条边的无向图，每条边有权值 $w[i]$ .

$\quad$ 定义一条路径的权值为这条路径上边权最大的边的权值.

$\quad$ 定义 $d(u, v)$ 为 $u$ 到 $v$ 的所有路径中权值最小的路径的权值.

$\quad$ $q$ 次询问，每次询问给出 $L$ ，求 $\begin{aligned} \sum_{1\leq u < v \leq n}[d(u, v) \leq L] \end{aligned}$

$\quad$ 对 $q$ 次答案异或一遍并输出.

$\quad$ $1 \leq n \leq 10^5, 1 \leq m,q \leq 5\times 10^5, 1 \leq w, L \leq 10^9$ .

二.分析

$\quad$ 很容易想到对 $w[i]$ 和 $L[i]$ 排序，这样可以保证答案不降.

$\quad$ 因此，对于处在 $[L[i-1] + 1 , L[i]]$ 的边 $e$ ，我们只需要统计有多个新点对产生.

$\quad$ 不难(用)证明，按照 $Kruskal$ 算法步骤， $e$ 一定是连通块 $u$ 所有点 $u'$ 与连通块 $v$ 所有点 $v'$ 的 $d(u', v')$ .

$\quad$ 详见代码.

三.代码实现

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

typedef unsigned long long ull;
typedef long long ll;

const int M = (int)1e6;
const int N = (int)5e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
const double eps = 1e-3;

struct node
{
    int cat;
    int u, v, w;

    bool operator< (const node& b)const
    {
        if(w != b.w) return w < b.w;
        return cat < b.cat;
    }
}s[M + 5];

unsigned int SA, SB, SC; int n, m, q, LIM;
unsigned int rng61(){
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}

void gen(){
    scanf("%d%d%d%u%u%u%d", &n, &m, &q, &SA, &SB, &SC, &LIM);
    for(int i = 1; i <= m; i++){
        s[i].u = rng61() % n + 1;
        s[i].v = rng61() % n + 1;
        s[i].w = rng61() % LIM;
        s[i].cat = 1;
    }
    for(int i = 1; i <= q; i++){
        s[i + m].w = rng61() % LIM;
        s[i + m].cat = 2;
    }
}

int fa[M + 5], sz[M + 5];

int tofind(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = tofind(fa[x]);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    gen();
    sort(s + 1, s + m + q + 1);
    for(int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
    ll ans = 0, cur = 0;
    for(int i = 1, u, v; i <= m + q; ++i)
    {
        if(s[i].cat == 1)
        {
            u = s[i].u, v = s[i].v;
            u = tofind(u), v = tofind(v);
            if(u == v) continue;
            cur += sz[u] * sz[v];
            fa[u] = v, sz[v] += sz[u];
        }
        else ans ^= cur;
    }
    printf("%lld\n", ans);
    return 0;
}

D 牛牛的粉丝

一.题目大意

$\quad$ 有一个环，长度为 $n$ ，环上每个位置上有 $x[i]$ 个人.

$\quad$ 先进行 $k$ 次活动，每次活动每个人有 $p_1$ 的概率按顺时针方向走一个单位， $p_2$ 的概率按逆时针方向走一个单位， $p_3$ 的概率待在原地.

$\quad$ 问 $k$ 次活动后，每个位置上人数的期望.

$\quad$ $3 \leq n \leq 500, 0 \leq k \leq 10^{18}，x[i] \leq 10^6$ .

二.分析

$\quad$ 记 $f[i, j]$ 为第 $i$ 次活动结束后， $j$ 号位置人数的期望.

$\quad$ 易得 $f[i, j] = p_1f[i - 1, j - 1] + p_2f[i - 1, j + 1] + p_3f[i - 1, j]$ .

$\quad$ 由于 $k$ 最大是 $10^{18}$ ，我们用矩阵快速幂优化递推式. 即：

$\quad$ $\left[ \begin{matrix} f[i, 0] & ... & f[i, n - 1] \end{matrix} \right] = \left[ \begin{matrix} f[i-1, 0] & ... & f[i-1, n - 1] \end{matrix} \right] \times \left[ \begin{matrix} p_3 & p_1 & 0 & ... & ... & ... & 0 & p_2 \\ p_2 & p_3 & p_1 & 0 & ... & ... & ... & 0 \\ 0 & p_2 & p_3 & p_1 & 0 & ... & ... & 0 \\ 0 & 0 & p_2 & p_3 & p_1 & 0 & ... & 0 \\ . & . & . & . & . & . & . & . \\ p_1 & 0 & ... & ... & ...& 0 & p_2 & p_3 \end{matrix} \right]$

$\quad$ 可这样时间复杂度是 $O(n^3logk)$ ，妥妥的 TLE...

$\quad$ 观察到系数矩阵是循环矩阵，而循环矩阵有两个特点：

$\quad$ $\quad$ 1.循环矩阵对加法和乘法封闭.

$\quad$ $\quad$ 2.循环矩阵某一行或某一***定，则循环矩阵确定.

$\quad$ 根据上述两条性质，我们则可把时间复杂度优化到 $O(n^2logk)$ .

三.代码实现

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

typedef unsigned long long ull;
typedef long long ll;

const int M = (int)5e2;
const int N = (int)5e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
const double eps = 1e-3;

int n, a, b, c, s; ll k, p1, p2, p3;

struct Matrix
{
    ll D[M + 5][M + 5];
}A, B, S, C;

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

void work()
{
    S = B; --k;
    while(k)
    {
        if(k & 1)
        {
            for(int i = 0; i < n; ++i) C.D[i][0] = 0;
            for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) C.D[i][0] = (C.D[i][0] + S.D[i][j] * B.D[j][0] % mod) % mod;
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < n; ++j)
                {
                    C.D[j][(j - i + n) % n] = C.D[i][0];
                }
            }
            memcpy(S.D, C.D, sizeof(C.D));
        }
        {
            for(int i = 0; i < n; ++i) C.D[i][0] = 0;
            for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) C.D[i][0] = (C.D[i][0] + B.D[i][j] * B.D[j][0] % mod) % mod;
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < n; ++j)
                {
                    C.D[j][(j - i + n) % n] = C.D[i][0];
                }
            }
            memcpy(B.D, C.D, sizeof(C.D));
        }
        k >>= 1;
    }
    for(int i = 0; i < n; ++i) C.D[0][i] = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            C.D[0][i] = (C.D[0][i] + A.D[0][j] * S.D[j][i]) % mod;
        }
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %lld", &n, &k);
    scanf("%d %d %d", &a, &b, &c);
    s = a + b + c;
    p1 = a * inv(s) % mod, p2 = b * inv(s) % mod, p3 = c * inv(s) % mod;
    memset(A.D, 0, sizeof(A.D));
    memset(B.D, 0, sizeof(B.D));
    for(int i = 0; i < n; ++i) scanf("%lld", &A.D[0][i]);
    if(k == 0)
    {
        for(int i = 0; i < n; ++i) printf("%lld%c", A.D[0][i], i == n - 1 ? '\n' : ' ');
        return 0;
    }
    for(int i = 0; i < n; ++i)
    {
        B.D[(i - 1 + n) % n][i] = p1;
        B.D[(i + 1) % n][i] = p2;
        B.D[i][i] = p3;
    }
    work();
    for(int i = 0; i < n; ++i) printf("%lld%c", C.D[0][i], i == n - 1 ? '\n' : ' ');
    return 0;
}

牛客练习赛68 A B C D

A 牛牛的mex运算

一.题目大意

二.分析

三.代码实现

1. 莫队

2. 简单操作

B 牛牛的算术

一.题目大意

二.分析

三.代码实现

C 牛牛的无向图

一.题目大意

二.分析

三.代码实现

D 牛牛的粉丝

一.题目大意

二.分析

三.代码实现