CF986 总结

~~卡常场~~

A. Fair

对 k 种货物分别跑多源 BFS 即可。统计答案可以用 std::nth_element() 做到 O(nk)。

B. Petr and Permutations

容易发现两种排列的奇偶性一定不同。数一下逆序对，或者找环即可做到 O(n\log n) 或 O(n)。

C. AND Graph

刚开始题目读错，以为 x\&y\neq 0 有边，以为很好做。。写完了才发现问题，考虑了以下建图转化：

把 2^n 个点每个拆成两个点，称为 1 类点和 2 类点。
对于一个 1 类点，向它对应的 2 类点连有向边，向每个它二进制上扣掉一个 1 的 1 类点分别连一条有向边；
对于一个 2 类点，如果它在给出的集合中，则向它的 n 位反码的 1 类点连一条有向边。

然后 Tarjan 找一下强连通分量，集合中的每个数对应的 2 类点所在的不同 SCC 个数就是答案。

然而空间只有 256MB，不能把图直接建出来，还得写手工栈。。下面是代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=4200000;
const int MAXM=8400000;
struct Node
{
    int u, x, y;
    Node() {}
    Node(int a, int b, int c):
        u(a), x(b), y(c) {}
} p[MAXM];
int n, m, ans;
bool b[MAXN];
int dfn[MAXM], low[MAXM], cnt;
int sta[MAXM], top, scc;
bool ins[MAXM];
void tarjan(int u)
{
    int k=0;
    p[++k]=Node(u, -1, -1);
    while (k)
    {
        int u=p[k].u, &x=p[k].x, &y=p[k].y;
        if (x==-1)
        {
            low[u]=dfn[u]=++cnt;
            sta[top++]=u, ins[u]=1;
        }
        if (~y) low[u]=min(low[u], low[y]);
        if (u<1<<n&&~x||u>=1<<n&&x==n)
        {
            if (low[u]==dfn[u])
            {
                scc++; int t;
                bool flag=0;
                do
                {
                    t=sta[--top], ins[t]=0;
                    if (t<1<<n&&b[t]) flag=1;
                }
                while (t!=u);
                if (flag) ans++;
            }
            k--; continue;
        }
        int v=-1;
        if (u<1<<n)
        {
            if (b[u]) v=(~u&(1<<n)-1)+(1<<n);
        }
        else
        {
            int t=u-(1<<n);
            if (x==-1) v=t;
            else if (t&1<<x) v=(t^1<<x)+(1<<n);
        }
        x++;
        if (~v)
        {
            if (!dfn[v]) y=v, p[++k]=Node(v, -1, -1);
            else if (ins[v]) low[u]=min(low[u], dfn[v]);
        }
    }
}
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i=1; i<=m; i++)
    {
        int x;
        scanf("%d", &x);
        b[x]=1;
    }
    for (int i=0; i<1<<n+1; i++)
        if (!dfn[i]) tarjan(i);
    printf("%d\n", ans);
    return 0;
}

然后看了题解才意识到并不要 Tarjan，直接 DFS 就好了。。这样就省了 dfn,low 等一堆数组，空间就能开下了。

D. Perfect Encoding

题意就是构造序列 \{b_m\} ，使 \prod\limits_{i = 1}^m {{b_i}} \ge n 且 k=\sum\limits_{i = 1}^m {{b_i}} 最小。

假设 k 确定且 b_i 的范围为正实数，那么找找规律就发现取 b=e,m=\frac{k}{e} 时 n 最大。然后 3 是最接近 e 的整数，于是我们可以这样构造 b：

若 k\equiv 0(\mod 3)，则所有 b_i 都为 3；
若 k\equiv 1(\mod 3)，则最后一个 b_i 为 4，其他都为 3；
若 k\equiv 2(\mod 3)，则最后一个 b_i 为 2，其他都为 3。

这样，在知道 k 的情况下，用 FFT 做高精快速幂就可以算 f(k) = \max \prod\limits_i {{b_i}} 了。

那么怎么知道最小的合法的 k 呢？二分是一个办法，但太慢。我们可以发现 f(k) 在指数意义上是略小于（等于）3^{\frac{k}{3}} 的。解个方程可以得到 k\geq 3\log_3 n。然后可能有一点偏差，从这个下界开始往上枚举常数次就可以得到答案。

最后一个问题是怎么算 \log_3 n（大致精确到整数）。我们知道这个值与 n 在十进制下的位数还有它的首几位关系最大。于是我们只考虑这些因素就可以得出一个近似的答案。

开始写的时候没考虑上面这么多，就跑得很慢。最后把常数卡到第一次交的 1/13 才过（

下面是一些（我用的）卡常技巧：

不要每次跑都用 FFT 快速幂算 3 的幂次，实际上只用在开始时算一次，后面会用的指数都差不多，只需要在此基础上乘个常数。
快速幂的乘方操作不要直接用两数相乘的板子，单独写可以省一次 DFT。
快速幂不要每次倍增都把乘法的长度取为 \lg n ，否则复杂度会多个 \log。
高精压位。
如果还是不行，请注意代码的底层优化。

这样做的复杂度就是 O(\lg n\log \lg n)。代码：

#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=2200000;
const int P=998244353;
const int G=3, GI=332748118;
int qpow(int n, int k)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%P;
        n=1ll*n*n%P; k>>=1;
    }
    return r;
}
int l, r[MAXN];
void getl(int n)
{
    l=1, r[0]=0; int d=0;
    while (l<=n) l<<=1, d++;
    for (int i=1; i<l; i++)
        r[i]=r[i>>1]>>1|(i&1)<<d-1;
}
void ntt(int* a, int ty)
{
    for (int i=0; i<l; i++)
        if (i<r[i]) swap(a[i], a[r[i]]);
    for (int k=1; k<l; k<<=1)
    {
        int wn=qpow(ty==1?G:GI, (P-1)/(k<<1));
        for (int i=0; i<l; i+=k<<1)
            for (int j=0, w=1; j<k; j++, w=1ll*w*wn%P)
            {
                int x=a[i+j], y=1ll*w*a[i+k+j]%P;
                a[i+j]=(x+y)%P, a[i+k+j]=(x-y+P)%P;
            }
    }
    if (ty==-1)
    {
        int li=qpow(l, P-2);
        for (int i=0; i<l; i++) a[i]=1ll*a[i]*li%P;
    }
}
int f[MAXN], g[MAXN];
struct BigInt
{
    static const int BASE=100;
    static const int WIDTH=2;
    vector<int> s;
    BigInt(int num=0)
    {
        s.clear();
        do s.push_back(num%BASE), num/=BASE;
        while (num>0);
    }
    BigInt(string str)
    {
        s.clear();
        int x, len=(str.length()-1)/WIDTH+1;
        for (int i=0; i<len; i++)
        {
            int cl=str.length()-i*WIDTH;
            int op=max(0, cl-WIDTH);
            sscanf(str.substr(op, cl-op).c_str(), "%d", &x);
            s.push_back(x);
        }
        clean();
    }
    void clean()
    {
        while(s.size()>1&&!s.back()) s.pop_back();
    }
    BigInt operator * (int b) const
    {
        BigInt c; c.s.clear();
        int l=s.size()+3;
        for (int i=0; i<l; i++) f[i]=0;
        for (int i=0; i<s.size(); i++) f[i]=s[i]*b;
        for (int i=0; i<l; i++)
        {
            if (f[i]>=BASE) f[i+1]+=f[i]/BASE, f[i]%=BASE;
            c.s.push_back(f[i]);
        }
        c.clean();
        return c;
    }
    void operator *= (const BigInt& b)
    {
        getl(s.size()+b.s.size());
        for (int i=0; i<l; i++) f[i]=g[i]=0;
        for (int i=0; i<s.size(); i++) f[i]=s[i];
        for (int i=0; i<b.s.size(); i++) g[i]=b.s[i];
        ntt(f, 1); ntt(g, 1);
        for (int i=0; i<l; i++) f[i]=1ll*f[i]*g[i]%P;
        ntt(f, -1);
        s.clear();
        for (int i=0; i<l; i++)
        {
            if (f[i]>=BASE) f[i+1]+=f[i]/BASE, f[i]%=BASE;
            s.push_back(f[i]);
        }
        clean();
    }
    void sqr()
    {
        getl(2*s.size());
        for (int i=0; i<l; i++) f[i]=0;
        for (int i=0; i<s.size(); i++) f[i]=s[i];
        ntt(f, 1);
        for (int i=0; i<l; i++) f[i]=1ll*f[i]*f[i]%P;
        ntt(f, -1);
        s.clear();
        for (int i=0; i<l; i++)
        {
            if (f[i]>=BASE) f[i+1]+=f[i]/BASE, f[i]%=BASE;
            s.push_back(f[i]);
        }
        clean();
    }
    bool operator <= (const BigInt& b) const
    {
        if (s.size()!=b.s.size()) return s.size()<b.s.size();
        for (int i=s.size()-1; i>=0; i--)
            if (s[i]!=b.s[i]) return s[i]<b.s[i];
        return 1;
    }
};
const double LOG3=log(3);
const double LOG3_10=log(10)/LOG3;
int p; BigInt pow3p;
int pw[]={1, 3, 9, 27, 81, 243};
BigInt pow3(int k)
{
    BigInt s=1, t=3;
    while (k)
    {
        if (k&1) s*=t;
        t.sqr(); k>>=1;
    }
    return s;
}
BigInt calc(int k)
{
    if (k<=2) return k;
    if (k%3==0) return pow3p*pw[k/3-p];
    if (k%3==1) return pow3p*(pw[k/3-1-p]*4);
    return pow3p*(pw[k/3-p]*2);
}
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    string s; cin>>s;
    BigInt n=s;
    int l=3*((s.size()-1)*LOG3_10+log(s.front()-'0')/LOG3);
    p=max(0, l/3-1); pow3p=pow3(p);
    for (int i=l; ; i++)
        if (n<=calc(i))
        {
            printf("%d\n", i);
            break;
        }
    return 0;
}

E. Prince's Problem

求一条路径上的点权与 x 的 gcd 之积，那么显然每个质因子间是独立的，且答案只与 x 的最多 8 个质因子有关。考虑到每个质因子的幂次最多是 \log 10^7 ，我们可以统计从根到一个节点的路径上每个质因子的每种幂次出现的次数，再进行差分。先将询问离线，分别在节点 u,v 处打上标记 1 ，在节点 lca(u,v),fa_{lca(u,v)} 处打上标记 -1。然后从根开始 DFS 计算对于每个询问的 x，在该询问对应的路径上每个 x 的质因子 i 的每种幂次 j 出现的次数 f(i,j) 。记 x 中质因子 i 的幂次为 g(i) ，则 f(i,j) 对答案的贡献为： \left\{ {\begin{array}{*{20}{c}}{{i^{f(i,j)}}}&{j < g(i)}\\{{i^{g(i)}}}&{j \ge g(i)}\end{array}} \right.

暴力统计即可。质因数分解时可以先筛出素数，会快一些。最后的复杂度为 O\left((n+q)\left(\frac{\sqrt x}{\log x}+8\log x\right)\right),x=10^7。代码：

#include <cstdio>
#include <vector>
using namespace std;
const int MAXN=110000;
const int MAXB=20;
const int MAXM=700000;
const int MAXX=11000000;
const int MAXK=10, MAXC=24;
const int MOD=1E9+7;
int qpow(int n, int k)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%MOD;
        n=1ll*n*n%MOD; k>>=1;
    }
    return r;
}
int m, pri[MAXM], id[MAXX];
bool mark[MAXX];
void sieve(int lim)
{
    m=0;
    for (int i=2; i<=lim; i++)
    {
        if (!mark[i]) pri[++m]=i, id[i]=m;
        for (int j=1; j<=m&&i*pri[j]<=lim; j++)
        {
            mark[i*pri[j]]=1;
            if (i%pri[j]==0) break;
        }
    }
}
struct Factor
{
    int k, p[MAXK], c[MAXK];
} b[MAXN];
void get_factor(int n, Factor& tar)
{
    int &k=tar.k=0;
    for (int i=1; pri[i]*pri[i]<=n; i++)
        if (n%pri[i]==0)
        {
            tar.p[++k]=i, tar.c[k]=0;
            while (n%pri[i]==0) tar.c[k]++, n/=pri[i];
        }
    if (n>1) tar.p[++k]=id[n], tar.c[k]=1;
}
struct Query
{
    int id, k;
    Query(int i, int v): id(i), k(v) {}
};
int n, q, a[MAXN];
int fa[MAXN][MAXB], dep[MAXN];
int cnt[MAXM][MAXC];
vector<int> g[MAXN];
vector<Query> h[MAXN];
int f[MAXN][MAXK][MAXC];
void dfs1(int u, int f, int d)
{
    fa[u][0]=f, dep[u]=d;
    for (int b=1; b<MAXB; b++)
        fa[u][b]=fa[fa[u][b-1]][b-1];
    for (int v:g[u])
        if (v!=f) dfs1(v, u, d+1);
}
int lca(int u, int v)
{
    if (dep[u]<dep[v]) swap(u, v);
    for (int b=MAXB-1; b>=0; b--)
        if (dep[fa[u][b]]>=dep[v]) u=fa[u][b];
    if (u==v) return u;
    for (int b=MAXB-1; b>=0; b--)
        if (fa[u][b]!=fa[v][b]) u=fa[u][b], v=fa[v][b];
    return fa[u][0];
}
void dfs2(int u)
{
    Factor t;
    get_factor(a[u], t);
    for (int i=1; i<=t.k; i++) cnt[t.p[i]][t.c[i]]++;
    for (Query r:h[u])
        for (int i=1; i<=b[r.id].k; i++)
        {
            for (int j=1; j<b[r.id].c[i]; j++)
                f[r.id][i][j]+=r.k*cnt[b[r.id].p[i]][j];
            for (int j=b[r.id].c[i]; j<MAXC; j++)
                f[r.id][i][0]+=r.k*cnt[b[r.id].p[i]][j];
        }
    for (int v:g[u])
        if (v!=fa[u][0]) dfs2(v);
    for (int i=1; i<=t.k; i++) cnt[t.p[i]][t.c[i]]--;
}
int main()
{
//  freopen("E.in", "r", stdin);
//  freopen("E.out", "w", stdout);
    sieve(1E7);
    scanf("%d", &n);
    for (int i=1; i<n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    dfs1(1, 0, 1);
    scanf("%d", &q);
    for (int i=1; i<=q; i++)
    {
        int u, v, x;
        scanf("%d%d%d", &u, &v, &x);
        get_factor(x, b[i]);
        int w=lca(u, v);
        h[u].push_back(Query(i, 1));
        h[v].push_back(Query(i, 1));
        h[w].push_back(Query(i, -1));
        h[fa[w][0]].push_back(Query(i, -1));
    }
    dfs2(1);
    for (int i=1; i<=q; i++)
    {
        int ans=1;
        for (int j=1; j<=b[i].k; j++)
        {
            int p=pri[b[i].p[j]];
            for (int k=1; k<b[i].c[j]; k++, p*=pri[b[i].p[j]])
                ans=1ll*ans*qpow(p, f[i][j][k])%MOD;
            ans=1ll*ans*qpow(p, f[i][j][0])%MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}

冷滟泽的个人博客

A. Fair

B. Petr and Permutations

C. AND Graph

D. Perfect Encoding

E. Prince's Problem

相关推荐

评论抢沙发

A. Fair

B. Petr and Permutations

C. AND Graph

D. Perfect Encoding

E. Prince's Problem

相关推荐

评论 抢沙发

评论抢沙发