「CF1257G」Divisor Set

发表于 分类于

题目链接：https://codeforces.com/problemset/problem/1257/G。

如果我们把每个能组成的数看成一个点，那么这些点和约数关系就构成了偏序集，答案就是最长反链。

由$\rm Dilworth$定理可知，最长反链等于最小链覆盖，所以只需求最小链覆盖。

我们把点按照质因子个数分层，那么显然一层之内没有连边，并且只会向下一层连边（跨层连的边不优，没有意义）。

所以最小链覆盖就是最多那一层的点的个数。

假设第$i$个质数有$a_i$个，那么答案的生成函数就是：

也就是一堆$1+x+x^2+\cdots +x^k$的乘积，注意到系数都是一，容易发现乘出来的多项式系数是对称的，并且是单峰的，所以最大的那个在中间那一项，利用分治算出这个多项式之后直接输出就行了。

复杂度$O(n\log ^2 n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define data asd09123jdf02i3h
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;
 
int n,a[maxn],s[maxn],cnt;
map<int,int > t;
 
int pos[maxn],w[maxn],bit,N,mxn;
 
int qpow(int a,int x) {
    int res=1;
    for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
    return res;
}
 
void gen() {
    for(mxn=1;mxn<=n<<1;mxn<<=1);
    w[0]=1,w[1]=qpow(3,(mod-1)/mxn);
    for(int i=2;i<mxn;i++) w[i]=1ll*w[i-1]*w[1]%mod;
}
 
void init(int l) {
    for(N=1,bit=-1;N<=l;N<<=1,bit++);
    for(int i=0;i<N;i++) pos[i]=pos[i>>1]>>1|((i&1)<<bit);
}
 
int c[2][maxn];
 
void ntt(int *r,int op) {
    for(int i=0;i<N;i++) if(pos[i]>i) swap(r[i],r[pos[i]]);
    for(int i=1,d=mxn>>1;i<N;i<<=1,d>>=1)
        for(int j=0;j<N;j+=i<<1)
            for(int k=0;k<i;k++) {
                int x=r[j+k],y=1ll*w[k*d]*r[i+j+k]%mod;
                r[j+k]=(x+y)%mod,r[i+j+k]=(x-y+mod)%mod;
            }
    if(op==-1) {
        int d=qpow(N,mod-2);reverse(r+1,r+N);
        for(int i=0;i<N;i++) r[i]=1ll*r[i]*d%mod;        
    }
}
 
struct poly {
    vector<int > a;
 
    poly () {a.clear();}
    
    int& operator [] (int x) {return a[x];}
    int size() {return a.size();}
 
    poly operator * (poly x) {
        init(size()+x.size());
        for(int i=0;i<size();i++) c[0][i]=a[i];
        for(int i=0;i<x.size();i++) c[1][i]=x[i];
        for(int i=size();i<N;i++) c[0][i]=0;
        for(int i=x.size();i<N;i++) c[1][i]=0;
        ntt(c[0],1),ntt(c[1],1);
        for(int i=0;i<N;i++) c[0][i]=1ll*c[0][i]*c[1][i]%mod;
        ntt(c[0],-1);
        poly res;
        for(int i=0;i<size()+x.size();i++) res.a.pb(c[0][i]);
        return res;
    }
};
 
poly solve(int l,int r) {
    poly res;
    if(l==r) {
        for(int i=0;i<=a[l];i++) res.a.pb(1);
        return res;
    }
    int L=l,R=r,m=l;
    while(L<=R) {
        int mid=(L+R)>>1;
        if(s[mid]-s[l-1]>=(s[r]-s[l-1])/2) R=mid-1;
        else L=mid+1,m=mid;
    }
    return solve(l,m)*solve(m+1,r);
}
 
int main() {
    read(n);gen();
    for(int i=1,x;i<=n;i++) read(x),t[x]++;
    for(auto x:t) a[++cnt]=x.sc,s[cnt]=a[cnt];
    for(int i=1;i<=n;i++) s[i]+=s[i-1];
    poly ans=solve(1,cnt);
    write(ans[n/2]);
    return 0;
}