Codeforces Round 856 (Div. 2)

题目质量很好的一场比赛。

D. Counting Factorizations

题意

一个整数的唯一分解形式为 $m=\prod\limits_{i=1}^kp_i^{e_i}$。我们记集合 $f(m)=\{p_1,e_1,p_2,e_2,\cdots,p_k,e_k\}$。给出一个长度为 $2n$ 的数组 $\{a_1,a_2,\cdots,a_{2n}\}$。问有多少个数 $m$ 满足 $f(m)=\{a_1,a_2,\cdots,a_{2n}\}$。

题解

记 $a$ 中的每个数出现次数为 $c_a$。

当底数确定以后，由于底数互不相同，此时的方案数就是一个多重集的排列数。

那么对于合数，它们只能当作指数，其贡献为 $\dfrac{1}{c_i!}$。对于质数，它可能当作底数，也可能作指数，但是，在底数中它至多出现一次。可以用生成函数进行表示：$\dfrac{1}{c_i!}+\dfrac{1}{(c_i-1)!}x$。那么，整体的方案数就可以写成：

$$n!\times\prod_{i\notin prime} \dfrac{1}{c_i!}\times\prod_{i\in prime}(\frac{1}{c_i!}+\frac{1}{(c_i-1)!}x)$$

答案就是 $x^n$ 项的系数。

时间复杂度 $O(n^2)$ 足以通过本题，不过可以通过分治乘法进一步优化。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int p=998244353;
int cnt,pri[maxn];
bool vis[maxn];
ll fac[maxn],ifac[maxn];
ll fpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
void init()
{
    vis[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt&&i*pri[j]<maxn;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
    fac[0]=1;
    for(int i=1;i<maxn;i++) fac[i]=i*fac[i-1]%p;
    ifac[maxn-1]=fpow(fac[maxn-1],p-2);
    for(int i=maxn-1;i;i--) ifac[i-1]=i*ifac[i]%p;

}
int a[maxn];
struct node
{
    ll a,k;
    node operator * (const node &x) const {return {a*x.a%p,k+x.k};}
    bool operator < (const node &x) const {return k<x.k;}
};
vector<node> v[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n;cin>>n;
    for(int i=1;i<=2*n;i++)
    {
        int x;cin>>x;
        a[x]++;
    }
    int m=0;
    ll ans=fac[n];
    for(int i=1;i<=1e6;i++)
    {
        if(!vis[i]&&a[i]>0) 
        {
            m++;
            for(int j=0;j<=1;j++) 
            {
                v[m].push_back({ifac[a[i]-j],j});
            }
        }
        else ans=ans*ifac[a[i]]%p;
    }
    for(int i=2;i<=m;i++)
    {
        vector<node> tmp;
        for(auto j:v[1])
            for(auto k:v[i])
                tmp.push_back(j*k);
        sort(tmp.begin(),tmp.end());
        vector<node> cur;
        int a=0,k=-1;
        for(auto i:tmp)
        {
            if(k==-1) k=i.k;
            if(k==i.k) a+=i.a;
            else
            {
                cur.push_back({a,k});
                a=i.a,k=i.k;
            }
        }
        cur.push_back({a,k});
        v[1]=cur;
    }   
    bool ok=0;
    for(auto i:v[1])
        if(i.k==n) 
        {
            ok=1;
            ans=ans*i.a%p;
        }
    cout<<ans*ok<<'\n';
    return 0;
}

E. Labeling the Tree with Distances

题意

给定一棵有 $n$ 个结点的树。给出一个大小为 $n-1$ 的数组 $a$。一个点 $u$ 被称为好点当且仅当可以利用数组 $a$ 中分配给 $n-1$ 个点，剩余一个点可以任意指定元素，满足每个点分到的元素恰好等于它到点 $u$ 的距离。求好点的个数。

题解

记录 $i$ 在数组 $a$ 中的出现次数为 $c_i$。那么数组 $a$ 可以用一个哈希来进行表示：$\sum\limits_{i=0}^{n-1}c_ib^i$，$b$ 是哈希的基数。 对一个点来说，最终可能的哈希值只有 $n$ 种。（剩余点到它的距离为 $0\sim n-1$）所以，我们只需要求出每个点的哈希值并检验即可。

对于点 $u$，记每个点到它的距离为 $d_i$，它的哈希值为 $\sum\limits_{i=0}^{n-1}d_ib^i$。可以用换根dp进行计算。第一次，我们先算每个点的子树内的，记为 $dp_x$。则 $dp_x=1+b\sum\limits_{child\ i}dp_i$。第二次，我们考虑向上的那棵子树，有 $dp2_x=dp_{fa_x}-b\times dp_x+b\times dp2_{fa_x}$。每个点的哈希值为 $h_x=dp_x+b\times dp2_x$。

本题的数据比较强，自然溢出好像被卡了。从网上找到一种比较厉害的写法。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=2e5+5;
const ull mod=(1ull<<61)-1;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ull> dist(100,mod-1);
const ull b=dist(rnd);
static inline ull add(ull a, ull b)
{
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}

static inline ull mul(ull a, ull b)
{
    __uint128_t c=__uint128_t(a)*b;
    return add(c>>61,c&mod);
}
ull base[maxn];
void init()
{
    base[0]=1;
    for(int i=1;i<maxn;i++) base[i]=mul(base[i-1],b);
}
ull f1[maxn],f2[maxn];
vector<int> g[maxn];
bool ans[maxn];
void dfs1(int u,int fa)
{
    f1[u]=1;
    for(auto v:g[u])
    {
        if(v==fa) continue;
        dfs1(v,u);
        f1[u]=add(f1[u],mul(f1[v],b));
    }
}
void dfs2(int u,int fa)
{
    for(auto v:g[u])
    {
        if(v==fa) continue;
        f2[v]=add(f1[u],add(mod-mul(f1[v],b),mul(f2[u],b)));
        dfs2(v,u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n;cin>>n;
    ull hsh=0;
    for(int i=1;i<n;i++)
    {
        int a;cin>>a;
        hsh=add(hsh,base[a]);
    }
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0);
    set<ull> s;
    for(int i=0;i<n;i++) s.insert(add(hsh,base[i]));
    for(int i=1;i<=n;i++)
        if(s.find(add(f1[i],mul(f2[i],b)))!=s.end()) ans[i]=1;
        else ans[i]=0;
    int cnt=0;
    for(int i=1;i<=n;i++) 
        if(ans[i]) cnt++;
    cout<<cnt<<'\n';
    for(int i=1;i<=n;i++)
        if(ans[i]) cout<<i<<' ';
    return 0;
}