2022-9-9总结

Boring Queries

考虑 lcm 的求法，一个求法是将所有质因子的质数取 max 再乘起来。

因为没有修改操作，可以考虑分解质因数然后用 ST 表求区间 max。

但是数据范围中 $a_i \le 2 \times 10^5$，很明显不能把每个质因子都用 ST 表处理，时间空间都不允许。

考虑每个数 $x$ 最多有一个大于 $\sqrt{x}$ 的质因子，所以我们可以用 ST 表处理 $\sqrt{2 \times 10^5}$ 以内的质数，共 $86$ 个，不会超出空间限制。

然后就是大于根号的质因子的去重问题，其实就是变相询问区间内不同数字个数，只不过带个权而已，可以仿照 HH 的项链这道题。

具体就是求一个 $\prod\limits_{i=l}^{r} i \, [last_i < l]$，这个可以主席树解决。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 100005;
const int P = 1e9+7;

int lim;
struct ST_list {  
    int f[N][20];
    
    void insert(int pos, int val)
    {
        f[pos][0] = val;
    }
    void prework()
    {
        for(int k = 1; k < 20; k++)
            for(int i = 1; i+(1<<k)-1 <= lim; i++)
                f[i][k] = max(f[i][k-1], f[i+(1<<(k-1))][k-1]);
    }
    int query(int l, int r)
    {
        int k = log2(r-l+1);
        return max(f[l][k], f[r-(1<<k)+1][k]);
    }
};
namespace Prime {
    const int SIZE = 450;
    bool vis[SIZE+1];
    int prime[SIZE+1], pcnt;
    void prework();
}
namespace HJT_tree {
    int root[N], node_cnt;
    struct node { int ls, rs; ll val = 1; } t[N*30];
    void insert(int &p, int s, int pos, ll val, int l = 0, int r = lim);
    ll query(int i, int ql, int qr, int l = 0, int r = lim);
}
using namespace Prime;
using namespace HJT_tree;

int n, q;
int a[N];
int last[N*2];
ST_list st[100];

ll qpow(ll a, ll b);

int main()
{
    // freopen("2.in", "r", stdin);
    // freopen("2.out", "w", stdout);
    cin >> n >> q; lim = n;
    Prime::prework();
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        for(int j = 1; j <= pcnt; j++)
        {
            int cnt = 0;
            while(a[i]%prime[j] == 0)
                cnt++, a[i] /= prime[j];
            st[j].insert(i, cnt);
        }
    }
    for(int i = 1; i <= pcnt; i++)
        st[i].prework();
    for(int i = 1; i <= n; i++)
    {
        HJT_tree::insert(root[i], root[i-1], last[a[i]], a[i]);
        last[a[i]] = i;
    }
    
    int l, r; ll lastans = 0;
    for(int i = 1; i <= q; i++)
    {
        cin >> l >> r;
        l = (l+lastans)%n+1;
        r = (r+lastans)%n+1;
        if(l > r) swap(l, r);
        ll ans = 1;
        for(int i = 1; i <= pcnt; i++)
            (ans *= qpow(prime[i], st[i].query(l, r))) %= P;
        (ans *= HJT_tree::query(root[r], 0, l-1)) %= P;
        (ans *= qpow(HJT_tree::query(root[l-1], 0, l-1), P-2)) %= P;
        
        cout << (lastans=ans) << "\n";
    }
    
}

namespace HJT_tree{
    #define ls(i) (t[i].ls)
    #define rs(i) (t[i].rs)
    #define lmid ((l+r)>>1)
    #define rmid ((l+r+2)>>1)
    void insert(int &p, int s, int pos, ll val, int l, int r)
    {
        if(p == 0) p = ++node_cnt;
        t[p].val = t[s].val*val%P;
        if(l == r) return void();
        if(pos <= lmid) rs(p) = rs(s), insert(ls(p), ls(s), pos, val, l, lmid);
        if(pos >= rmid) ls(p) = ls(s), insert(rs(p), rs(s), pos, val, rmid, r);
    }
    ll query(int i, int ql, int qr, int l, int r)
    {
        if(ql <= l and r <= qr) return t[i].val; ll ans = 1;
        if(ql <= lmid) (ans *= query(ls(i), ql, qr, l, lmid)) %= P;
        if(qr >= rmid) (ans *= query(rs(i), ql, qr, rmid, r)) %= P;
        return ans;
    }
}
namespace Prime {
    void prework()
    {
        for(int i = 2; i <= SIZE; i++)
        {
            if(!vis[i]) prime[++pcnt] = i;
            for(int j = 1; j <= pcnt and i*prime[j] <= SIZE; j++)
            {
                vis[i*prime[j]] = true;
                if(i%prime[j] == 0) break;
            }
        }
    }
}


ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}

序列

考虑枚举第一格的数，那么我们需要知道 $f_{i,j}$ 表示长度限制为 $i$，结束时第一格为 $j$ 的概率，$g_{i,j}$ 表示此时答案的期望。

求 $f$ 和 $g$ 时需要知道 $x_{i,j}$ 表示长度限制为 $i$，第一格弄出 $j$ 的概率，以及 $u_{i,j}$ 表示长度限制为 $i$，初始时第一格为 $j$ 的期望答案。

具体转移方程可以参考代码。

写出转移方程后不难发现将 $g_{i,j}$ 改为长度限制为 $i$，初始时第一格为 $j$，结束时第一格还是 $j$ 的概率*期望，就可以不用记 $f_{i,j}$，同时转移方程会简化很多。

时间复杂度 $O(nm)$。

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int P = 1e9+7;
const int N = 2005;

int n, m, t;
ll g[N];
ll f[N][N];
ll p[N][N];
ll q[N][N];

ll qpow(ll a, ll b);


int main()
{
    cin >> n >> m >> t;
    int maxn = min(t, n+m-1);
    ll invm = qpow(m, P-2);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= maxn; j++)
        {
            p[i][j] = p[i][j-1]*p[i-1][j-1]%P;
            if(j <= m) (p[i][j] += invm) %= P;
            q[i][j] = 1;
            if(j != maxn) q[i][j] = (q[i][j]-p[i-1][j]+P)%P;
        }
        for(int j = maxn; j >= 1; j--)
        {
            ll tmp = (q[i][j]*j%P + g[i-1])%P;
            if(j != maxn) tmp = (tmp - p[i-1][j]*f[i-1][j]%P + P)%P;
            f[i][j] = tmp;
            if(j != maxn) (f[i][j] += (1-q[i][j]+P)*f[i][j+1]%P) %= P;
            (g[i] += p[i][j]*tmp%P) %= P;
        }
    }
    
    cout << g[n];
}

ll qpow(ll a, ll b)
{
    ll ans = 1; a %= P;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}

Dokhtar-kosh paths

如果一坨字符可以排列成一个回文串，要么每个字符都出现了奇数次，要么只有一个字符出现了偶数次。

因为只需要知道每个字符是出现了奇数次还是偶数次，所以可以将字符状态状压一下。

我们可以处理出每个点到根的路径上的字符状态，这样找两个点异或一下就可以知道这条路径上的状态了。

求子树中最长的 Dk 路径，可以先求跨过当前节点的最长路径，最后再 dfs 一遍子树取个 max 即可。

如果是暴力的话只需要开一个桶进行 dfs 就行了，时间复杂度 $O(n^2)$。

因为我们只需要这么一个桶，所以可以用树上启发式合并优化一下，这样时间复杂度就变成 $O(n\log n)$ 了。

#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int N = 500005;

int n, ans[N];

namespace graph {
    struct edge {
        int to, ch, next;
    } e[N];
    int head[N], ecnt = 1;
    inline void insert(int u, int v, int ch)
    {
        e[++ecnt] = {v, ch, head[u]}; head[u] = ecnt;
    }
}
namespace dsu_on_tree {
    int t[1<<22];
    int big[N], siz[N], dep[N], val[N];
    int dfn[N], rk[N], dft;
    void dfs(int x, bool save);
    void prework(int x);
    void getans(int x);
}
using namespace graph;
using namespace dsu_on_tree;

signed main()
{
    
    read(n);
    for(int i = 2; i <= n; i++)
    {
        int f; char ch;
        read(f, ch);
        insert(f, i, ch-'a');
    }
    
    dep[1] = 1;
    dsu_on_tree::prework(1);
    dsu_on_tree::dfs(1, true);
    dsu_on_tree::getans(1);
    
    for(int i = 1; i <= n; i++)
        print(ans[i], ' ');
    
}

namespace dsu_on_tree{
    void add(int x)
    {
        t[val[x]] = max(t[val[x]], dep[x]);
    }
    int query(int x, int lca)
    {
        int ans = 0;
        int tmp = val[x];
        if(t[tmp] != 0)
            ans = max(ans, t[tmp]+dep[x]-2*dep[lca]);
        for(int k = 0; k < 22; k++)
        {
            tmp = val[x]^(1<<k); 
            if(t[tmp] != 0)
                ans = max(ans, t[tmp]+dep[x]-2*dep[lca]);
        }
        return ans;
    }
    void dfs(int x, bool save)
    {
        for(int i = head[x], y; i; i = e[i].next)
        {
            y = e[i].to;
            if(y == big[x]) continue;
            dfs(y, false);
        }
        if(big[x]) dfs(big[x], true);
        add(x);
        for(int i = head[x], y; i; i = e[i].next)
        {
            y = e[i].to;
            if(y == big[x]) continue;
            for(int j = dfn[y]; j <= dfn[y]+siz[y]-1; j++)
                ans[x] = max(ans[x], query(rk[j], x));
            for(int j = dfn[y]; j <= dfn[y]+siz[y]-1; j++)
                add(rk[j]);
        }
        ans[x] = max(ans[x], query(x, x));
        
        if(!save)
        {
            for(int j = dfn[x]; j <= dfn[x]+siz[x]-1; j++)
                t[val[rk[j]]] = 0;
        }
    }
    void getans(int x)
    {
        for(int i = head[x], y; i; i = e[i].next)
        {
            y = e[i].to; getans(y);
            ans[x] = max(ans[x], ans[y]);
        }
    }
    void prework(int x)
    {
        siz[x] = 1;
        dfn[x] = ++dft; rk[dft] = x;
        for(int i = head[x], y; i; i = e[i].next)
        {
            y = e[i].to;
            dep[y] = dep[x]+1;
            val[y] = val[x]^(1<<e[i].ch);
            prework(y); siz[x] += siz[y];
            if(siz[y] > siz[big[x]]) big[x] = y;
        }
    }
    
}