problem
我们说一个集合 \(D\) 是一个好的集合，当不存在集合中的两个不同元素 \(a,b\) 使得 \(a\) 是 \(b\) 的约数。
给定一个超大整数的素数表示形式 \(N = \prod_{i=1}^n{p_i}\)，要求从它的所有因子中选择尽可能多的元素组成一个好的集合。
问这个最大的 size 是多少，输出模 998244353 的结果。
\(n\leq 200000\)
Sperner 定理
Sperner 定理：设 \(S\) 是 \(n\) 元非空集合，若 \(\mathcal F\) 是 \(S\) 的子集族且满足 \(\mathcal F\) 中的元素互不包含，则称 \(\mathcal F\) 是 \(S\) 的一个反链，且有
\[|\mathcal F| \leq \binom{n}{n/2}
\]
（明显 n/2 向哪边取整没关系）
solution
那我们相当于是要找出 \(S=\{p_1,p_2,\cdots,p_n\}\) 这个集合的最长反链，所以输出 \(\binom{n}{n/2}\)？错了，有一些 \(p\) 是一样的，考虑的时候也是一样的，我们不妨想成是将相同 \(p_i\) 压缩成一个数，然后这些东西的指数的和要相同，取出指数和等于 \(n/2\) 的所有因数。使用分治 NTT 求出 ?
code
点击查看代码
#include <random>
#include <ctime>
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template<unsigned P> struct modint{
unsigned v; modint():v(0){}
template<class T> modint(T x):v((x%int(P)+int(P))%int(P)){}
modint operator-()const{return modint(P-v);}
modint inv()const{return assert(v),qpow(*this,LL(P)-2);}
modint&operator+=(const modint&rhs){if(v+=rhs.v,v>=P) v-=P; return *this;}
modint&operator-=(const modint&rhs){return *this+=-rhs;}
modint&operator*=(const modint&rhs){v=1ull*v*rhs.v%P; return *this;}
modint&operator/=(const modint&rhs){return *this*=rhs.inv();}
friend int raw(const modint&self){return self.v;}
friend modint qpow(modint a,LL b){modint r=1;for(;b;b>>=1,a*=a) if(b&1) r*=a; return r;}
friend modint operator+(modint lhs,const modint&rhs){return lhs+=rhs;}
friend modint operator-(modint lhs,const modint&rhs){return lhs-=rhs;}
friend modint operator*(modint lhs,const modint&rhs){return lhs*=rhs;}
friend modint operator/(modint lhs,const modint&rhs){return lhs/=rhs;}
friend bool operator==(const modint&lhs,const modint&rhs){return lhs.v==rhs.v;}
friend bool operator!=(const modint&lhs,const modint&rhs){return lhs.v!=rhs.v;}
};
int glim(int x){return 1<<(32-__builtin_clz(x));}
int bitctz(int x){return __builtin_ctz(x);}
const int P=998244353;
typedef modint<998244353> mint;
const mint G = 3, invG = 1 / G;
void ntt(vector<mint>&a,int op){
int n=a.size(); vector<mint> w(n);
for(int i=1,r=0;i<n;i++){
int b=1<<(bitctz(n)-bitctz(i));
r&=b-1,r^=b>>1;
if(i<r) swap(a[i],a[r]);
}
for(int k=1,len=2;len<=n;k<<=1,len<<=1){
mint wn=qpow(op==1?G:invG,(P-1)/len);
for(int i=raw(w[0]=1);i<k;i++) w[i]=w[i-1]*wn;
for(int i=0;i<n;i+=len){
for(int j=0;j<k;j++){
mint x=a[i+j],y=a[i+j+k]*w[j];
a[i+j]=x+y,a[i+j+k]=x-y;
}
}
}
if(op==-1){mint inv=mint(1)/n; for(mint&x:a) x*=inv;}
}
int n, m;
int c[200010], s[200010];
map<int, int> mp;
vector<mint> solve(int l, int r) {
if (l == r)
return vector<mint>(c[l] + 1, 1);
int mid = (l + r) >> 1;
vector<mint> lhs = solve(l, mid);
vector<mint> rhs = solve(mid + 1, r);
int len = glim(lhs.size() + rhs.size() - 1);
lhs.resize(len), rhs.resize(len);
ntt(lhs, 1), ntt(rhs, 1);
for (int i = 0; i < len; i++)
lhs[i] *= rhs[i];
ntt(lhs, -1);
lhs.resize(s[r] - s[l - 1] + 1);
return lhs;
}
int main() {
scanf("%d", &n);
for (int i = 1, x; i <= n; i++)
scanf("%d", &x), mp[x]++;
for (auto elem: mp)
c[++m] = elem.second, s[m] = s[m - 1] + c[m];
shuffle(c + 1, c + m + 1, mt19937{unsigned(time(0))});
printf("%d\n", raw(solve(1, m)[n >> 1]));
return 0;
}