2019西安邀请赛题解(部分)

B.(积性函数前缀和)

题意

给定 $n, m, p$ , 其中 $p$ 是质数

求 $<mstyle displaystyle="true" scriptlevel="0"> <munderover> \prod i = 1 n </munderover> <munderover> \prod j = 1 n </munderover> <munderover> \prod k = 1 n </munderover> m^{(i, j) [k ∣ (i, j)]} m o d p </mstyle>$

推导

使用费马降幂,可得 $m^{<mstyle displaystyle="true" scriptlevel="0"> <munderover> \sum i = 1 n </munderover> <munderover> \sum j = 1 n </munderover> (i, j) σ ((i, j)) m o d (p - 1) </mstyle>} m o d p$

$<mstyle displaystyle="true" scriptlevel="0"> <munderover> \sum i = 1 n </munderover> <munderover> \sum j = 1 n </munderover> <munderover> \sum k = 1 n </munderover> (i, j) [k ∣ (i, j)] = <munderover> \sum d = 1 n </munderover> d σ (d) <munderover> \sum i = 1 n </munderover> <munderover> \sum j = 1 n </munderover> [(i, j) = = d] = <munderover> \sum d = 1 n </munderover> d σ (d) <munderover> \sum i = 1 \frac{n}{d} </munderover> <munderover> \sum j = 1 \frac{n}{d} </munderover> [(i, j) = = 1] </mstyle>$

使用欧拉函数可得, $\sum_{d = 1}^{n} d σ (d) (2 Φ (\frac{n}{d}) - 1)$

$d σ (d), ϕ (d)$ 前缀和可线性筛预处理 $O (n^{\frac{2}{3}})$ , 剩下的直接杜教筛(或者直接分块)，这样总复杂度为 $O (n^{\frac{2}{3}})$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x7fffffff;

const int N = 8e6 + 7;

int mod;
int dsig[N+1000], phi[N+10000], p[N>>3], num[N], pn;

void init() {
    phi[1] = dsig[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!phi[i]) {
            phi[i] = i - 1;
            p[pn++] = i;
            num[i] = 1;
            dsig[i] = 2;
        }
        for(int j = 0, d; j<pn && (d=i*p[j])<N; j++) {
            if(i % p[j] == 0) {
                num[d] = num[i] + 1;
                phi[d] = phi[i] * p[j];
                dsig[d] = dsig[i]/num[d]*(num[d]+1);
                break;
            } else {
                num[d] = 1;
                phi[d] = phi[i] * (p[j] - 1);
                dsig[d] = dsig[i]*2;
            }
        }
    }
    for(int i = 1; i < N; i++) {
        phi[i] = (2ll * phi[i] + phi[i - 1]) % mod;
        dsig[i] = ((ll)i * dsig[i] + dsig[i - 1]) % mod;
    }
    for(int i = 0; i < 1000; i++) phi[i+N]=dsig[i+N]=inf;
}

int n, m, pp;
inline int id(int x) { return x < N? x : n / x + N;}
inline int s1(int x) { return x*(x+1ll)/2%mod;}
int Dsig(int x) {
    int t = id(x);
    if(t < N || dsig[t] != inf) return dsig[t];
    int &ret = dsig[t] = 0;
    for(int l = 1, r; l <= x; l = r + 1) {
        r = x / (x / l);
        ret = (ret + ((ll)s1(r) - s1(l-1))*s1(x/l))%mod;
    }
    return ret = ((ll)ret + mod) % mod;
}
int Phi(int x) {
    int t = id(x);
    if(t < N || phi[t] != inf) return (phi[t] - 1ll + mod) % mod;
    int &ret = phi[t] = 2ll*s1(x)%mod;
    for(int l = 2, r; l <= x; l = r + 1) {
        r = x / (x / l);
        ret = (ret - (r - l + 1ll) * (Phi(x/l) + 1)) % mod;
    }
    ret = ((ll)ret + mod) % mod;
    return ((ll)ret + mod - 1) % mod;
}
int solve() {
    mod = pp - 1;
    init();
    int ord = 0;
    for(int l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ord = (ord + Phi(n / l) * ((ll)Dsig(r) - Dsig(l - 1))) % mod;
    }
    ord = ((ll)ord + mod) % mod;
    int ret = 1;
    for(m %= pp; ord; ord>>=1, m = (ll)m*m%pp)
        if(ord&1) ret = (ll)ret*m%pp;
    return ret;
}

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
    clock_t s = clock();
#endif
    scanf("%d%d%d", &n, &m, &pp);
    printf("%d\n", solve());
#ifdef local
    cerr << clock() - s << " ms\n";
#endif
    return 0;
}

E.(树链剖分)

由于每次操作都是 $s$ 到根，所以有一个 $l o g$ 的做法？（这不是 $b z o j$ 原题吗.jpg）

菜鸡只会树链剖分然后维护 $o r$ 和 $a n d$ 标记，两个 $l o g$ 的做法

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1 << 18 | 7;

vector<int> E[N];
int fa[N], dep[N], sz[N], son[N], top[N], id[N], rid[N], cnt;
void dfs1(int u, int d) {
    dep[u] = d; sz[u] = 1;
    int& maxs = son[u] = -1;
    for(int &e : E[u]) {
        if(e == fa[u]) continue;
        fa[e] = u, dfs1(e, d + 1);
        sz[u] += sz[e];
        if(maxs == -1 || sz[e] > sz[maxs]) maxs = e;
    }
}
void dfs2(int u, int tp) {
    top[u] = tp; id[u] = ++cnt; rid[cnt] = u;
    if(son[u] != -1) dfs2(son[u], tp);
    for(int &e : E[u]) {
        if(e == fa[u] || e == son[u]) continue;
        dfs2(e, e);
    }
}

int w[N], tag[2][N], a[N];
int n, q;
#define ls o<<1
#define rs o<<1|1
void push_up(int o){ w[o]=w[ls]^w[rs];}
void push_down(int o, int l, int r) {
    int &t1 = tag[0][o], &t2=tag[1][o];
    if(~t1) {
        w[ls] &= t1, w[rs] &= t1;
        tag[0][ls] &= t1; tag[0][rs] &= t1;
        tag[1][ls] ^= (~t1&tag[1][ls]);
        tag[1][rs] ^= (~t1&tag[1][rs]);
        t1 = ~0u;
    }
    if(t2) {
        int mid = (l+r)>>1;
        if((mid-l+1)&1) w[ls] |= t2;
        else w[ls] ^= t2&w[ls];
        if((r-mid)&1) w[rs] |= t2;
        else w[rs] ^= t2&w[rs];
        tag[1][ls] |= t2; tag[1][rs] |= t2;
        tag[0][ls] ^= (~tag[0][ls]&t2);
        tag[0][rs] ^= (~tag[0][rs]&t2);
        t2 = 0;
    }
}
void build(int o, int l, int r) {
    tag[0][o] = ~0u, tag[1][o] = 0;
    if(l == r) { w[o] = a[rid[l]]; return;}
    int mid = (l + r)>>1;
    build(ls,l,mid), build(rs, mid+1, r);
    push_up(o);
}
void update(int o, int l, int r, int L, int R, int x, int k) {
    // k = 0 for AND, k = 1 for OR
    if(L <= l && r <= R) {
        if(k) {
            if((r-l+1)&1) w[o] |= x;
            else w[o] ^= w[o]&x;
            tag[0][o] ^= ~tag[0][o]&x, tag[1][o] |= x;
        } else {
            w[o] &= x;
            tag[0][o] &= x, tag[1][o] ^= (~x&tag[1][o]);
        }
        return;
    }
    int mid = (l + r) >> 1;
    push_down(o, l, r);
    if(mid >= L) update(ls, l, mid, L, R, x, k);
    if(mid < R) update(rs, mid+1, r, L, R, x, k);
    push_up(o);
}
int query(int o, int l, int r, int L, int R) {
    if(L <= l && r <= R) return w[o];
    int mid = (l + r)>>1, ret = 0;
    push_down(o, l, r);
    if(mid >= L) ret ^= query(ls, l, mid, L, R);
    if(mid < R) ret ^= query(rs, mid+1, r, L, R);
    return ret;
}

/* void brock(int l, int r, int x, int o) { if(o == 0) for(int i = l; i <= r; i++) a[i] &= x; if(o == 1) for(int i = l; i <= r; i++) a[i] |= x; } int query(int l, int r) { int ret = 0; for(int i = l; i <= r; i++) ret ^= a[i]; return ret; }*/

void updates(int u, int v, int x, int op) {
    int uu = top[u], vv = top[v];
    while(uu != vv) {
        if(dep[uu] < dep[vv]) swap(uu, vv), swap(u, v);
        update(1, 1, n, id[uu], id[u], x, op);
        u = fa[uu], uu = top[u];
    }
    if(dep[u] < dep[v]) swap(u, v);
    update(1, 1, n, id[v], id[u], x, op);
}

int query(int u, int v) {
    int uu = top[u], vv = top[v], ret = 0;
    while(uu != vv) {
        if(dep[uu] < dep[vv]) swap(uu, vv), swap(u, v);
        ret ^= query(1, 1, n, id[uu], id[u]);
        u = fa[uu], uu = top[u];
    }
    if(dep[u] < dep[v]) swap(u, v);
    ret ^= query(1, 1, n, id[v], id[u]);
    return ret;
}

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs1(1, 1); dfs2(1, 1);
    build(1, 1, n);
    for(int i = 0, op, u, x; i < q; i++) {
        scanf("%d%d%d", &op, &u, &x);
        if(op == 3) {
            x ^= query(1, u);
            puts(x?"YES":"NO");
        } else updates(1, u, x, op==1);
    }
    return 0;
}

I.(细节题，bsgs)

题意

给定由 $a, p$ 生成的一个序列 $b_{1}, b_{2}, . . ., b_{n}$ ,其中{ $b_{n}$ }为 $c_{k} \equiv a^{k} m o d p$ 的一段连续的子串.

现在要求 $a, p$ .答案不唯一输出"unsure", 不存在输出"error".

做法

假设 $b_{1} = a^{k}$ , 则 $b_{i} = a^{k + i - 1}$
对于任意的 $2 \leq i \leq n - 1$ , 都有 $b_{i}^{2} \equiv b_{i - 1} b_{i + 1} m o d p$

也就是说 $p ∣ (b_{i}^{2} - b_{i - 1} b_{i + 1})$ ，求出所有的 $b_{i}^{2} - b_{i - 1} b_{i + 1}$ 求gcd, 然后对最后结果的每个素因子check即可.

如何check？就是说判断一个素数 $p$ 是否合法.

注意到 $a = i n v (b_{0}) \times b_{1} m o d p$

先判 $b_{0}$ 能否通过 $a^{k} m o d p$ 表示（bsgs算法），然后挨个检查是否合法。

边界情况: 所有数都相等, 如果全为1, 输出"unsure", 否则输出"error".

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7;
#ifdef local
    typedef long long i16;
#else
    typedef __int128 i16;
#endif

const i16 one = 1;
ll power_mod(ll a, ll b, ll mod) {
    ll ret = 1;
    for(a %= mod; b; b>>=1, a=one*a*a%mod)
        if(b & 1) ret = one*ret*a%mod;
    return ret;
}

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
cc_hash_table<ll, ll> hs;
bool bsgs(ll a, ll b, ll n) {
    hs.clear();
    ll B = sqrt(n), t = 1, tt = b;
    for(ll i = 0; i < B; i++)
        hs[t] = i, t = one*a*t%n;
    t = power_mod(t, n - 2, n);
    for(ll i = 0; i < n; i += B, tt=one*tt*t%n)
        if(hs.find(tt) != hs.end())
            return true;
    return false;
}

ll a[N];
bool chk(int n, ll x) {
    ll inv = power_mod(a[0], x - 2, x);
    ll aa = one * a[1] * inv % x, t = a[0];
    if(a[0] >= x || !bsgs(aa, a[0], x)) return 0;
    for(int i = 1; i < n; i++)
        if((t = one * t * aa % x) != a[i])
            return 0;
    return 1;
}


int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%lld", a+i);
    ll d = 0;
    if(n >= 2) {
        bool f = 1;
        for(int i = 1; i < n; i++)
            f &= a[i] == a[i - 1];
        if(f) return 0 * puts(a[0]==1?"unsure":"error");
    }
    for(int i = 1; i < n-1; i++)
        d = __gcd(d, abs(a[i]*a[i]-a[i-1]*a[i+1]));
    if(d == 1) return 0 * puts("error");
    if(d == 0) return 0 * puts("unsure");
    vector<ll> aa;
    for(ll i = 2; i * i <= d; i++) {
        if(d % i == 0) {
            if(chk(n, i)) aa.push_back(i), assert(i==2);
            while(d % i == 0) d /= i;
        }
    }
    if(d != 1) if(chk(n, d)) aa.push_back(d);
    if(aa.size() == 0) return 0 * puts("error");
    else if(aa.size() > 1) return 0 * puts("unsure");
    else {
        ll inv = power_mod(a[0], aa[0] - 2, aa[0]);
        ll tt = one * a[1] * inv % aa[0];
        printf("%lld %lld\n", tt, aa[0]);
    }
    return 0;
}

J.(dfs+map启发式合并)

处理出树上前缀异或和, 然后只有异或值相等的点对才有贡献.

对于没有祖先关系的点对 $(u, v)$ , 贡献为 $s z_{u} \times s z_{v}$ ，其中 $s z_{x}$ 表示以 $x$ 为根的子树大小.

对于有祖先关系的点对 $(u, v)$ ,贡献为 $(n - s z_{v^{'}}) \times s z_{v}$ , 假设祖先为 $u$ , $v^{'}$ 表示以 $u$ 的儿子为根子树中包含 $v$ 的子树根编号.

对于第一种情况，可以 $d f s$ 前序统计，后序加点的方式来计算.

对于第二种可以直接用 $m a p$ 启发式合并, 复杂度为 $O (n l o g^{2} n)$

（赛后发现可以不用启发式合并，对于 $u$ 这个点只在以 $u$ 为根的子树中作为祖先，那么回溯的时候直接减掉就可以了，这样复杂度为 $O (n l o g n)$ ）

代码（启发式合并）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
vector<int> E[N];
ll w[N];
int sz[N];
void dfs(int u, int fa) {
    sz[u] = 1;
    for(auto &e : E[u]) {
        if(e == fa) continue;
        w[e] ^= w[u];
        dfs(e, u);
        sz[u] += sz[e];
    }
}
map<ll, int> mp[N];
void Union(int x, int y) {
    if(mp[x].size() < mp[y].size())
        swap(mp[x], mp[y]);
    for(auto &e : mp[y])
        (mp[x][e.fi] += e.se) %= mod;
}
ll ans = 0;
int n;
void work(int u, int fa) {
    ans += 1ll * mp[0][w[u]] * sz[u];
    ans %= mod;
    mp[u][w[u]] = sz[u];
    for(auto &e : E[u]) {
        if(e == fa) continue;
        work(e, u);
        if(mp[e].count(w[u])) {
            ans += 1ll * mp[e][w[u]] * (n - sz[e]);
            ans %= mod;
        }
        Union(u, e);
    }
    (mp[0][w[u]] += sz[u]) %= mod;
}
int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &n);
    for(int i = 2, fa; i <= n; i++) {
        scanf("%d%lld", &fa, &w[i]);
        E[fa].push_back(i);
        E[i].push_back(fa);
    }
    dfs(1, 0); work(1, 0);
    printf("%lld\n", ans);
    return 0;
}

回溯

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
vector<int> E[N];
ll w[N]; int sz[N];
void prepare(int u = 1) {
    sz[u] = 1;
    for(int &e : E[u])
        w[e]^=w[u],prepare(e),sz[u]+=sz[e];
}
map<ll, int> nfa, fa;
ll ans; int n;
void work(int u) {
    int &x = nfa[w[u]], &y = fa[w[u]];
    ans = (ans + 1ll*x*sz[u]) % mod;
    ans = (ans + 1ll*y*sz[u]) % mod;
    for(int &e : E[u]) {
        y = (y + n - sz[e]) % mod;
        work(e);
        y = (y + mod - n + sz[e]) % mod;
    }
    x = (x + sz[u])%mod;
}


int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &n);
    for(int i = 2, fa; i <= n; i++)
        scanf("%d%lld", &fa, &w[i]), E[fa].pb(i);
    prepare(), work(1);
    printf("%lld\n", ans);
    return 0;
}

L.(置换群)

题意

给一个长度为 $n$ , 且每个数字都不相同的序列 $a_{i}$ .
有两种操作，
第一种交换序列的前一半和后一半, 如果 $n$ 为奇数，中间的数不变
比如1 2 3 4 5 交换后变成 4 5 3 1 2.
第二种操作为将偶数位与其前一位交换，如果 $n$ 为奇数，最后一个数不用交换
比如1 2 3 4 5 交换后变成 2 1 4 3 5.
两种操作可以无限次，现问可以生成多少种不同的序列序列

做法

比赛时候先瞎推瞎猜wa了两发，然后直接打表发现规律直接过了，在飞机上仔细想了下可以用置换群来解决
注意到同一个操作连续使用偶数次就变回原序列，因此可以直接做两次不同的操作，然后求置换群的循环节即可.
废话不多说直接上代码

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 7;
int a[N], vis[N];

int solve(int n) {
    if(n == 1) return 1;
    iota(a, a + 1 + n, 0);
    fill(vis, vis + 1 + n, 0);
    for(int i = 2; i <= n; i+=2)
        swap(a[i], a[i - 1]);
    int t = (n+1)/2+1;
    for(int i = t; i <= n; i++)
        swap(a[i], a[i-t+1]);
    int _lc = 1;
    for(int i = 1; i <= n; i++) {
        if(vis[i]) continue;
        int cnt = 0; int t = i;
        while(!vis[t]) {
            cnt++, vis[t] = 1;
            t = a[t];
        }
        _lc = _lc/__gcd(_lc, cnt)*cnt;
    }
    return _lc * 2;
}

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    int n; scanf("%d", &n);
    for(int i = 0, x; i < n; i++) scanf("%d", &n);
    printf("%d\n", solve(n));
    return 0;
}