我的线段树自带 $10$ 倍常数.
$Count$
对于每一种 $\prod a_i\not=n^m$ 的选法,都恰好存在另一种对应的选法 $\prod \frac n {a_i}$ .
随便选的方案数为 $(\sigma(n))^{2m}$ ,再加上 $\prod a_i=n^m$ 的方案数,除以 $2$ 就是答案.
于是只需要算 $\prod a_i=n^m$ 的方案数.
将 $n$ 分解质因数,显然每个质因子可以分开算方案,答案是每个质因子的贡献乘积.
每个质因子的贡献就是一个整数划分问题, $dp$ 一下,因为方案数只与质因子质数有关,所以可以最后一起加入贡献.
$Delete$
每次删掉最长的一个单调序列,直到删完.
假设当前的序列长度为 $n$ ,最长上升子序列长度为 $a$ ,最长下降子序列长度为 $b$ .
根据 $Dilworth$ 定理,用最长上升子序列覆盖这个序列至少需要的子序列数目也是 $b$ .
所以就有 $a\cdot b\ge n$ ,得到 $\max(a,b)\ge \sqrt n$ .
于是每次操作至少会使得一个长度为 $n$ 的序列长度减少 $\sqrt n$ ,当 $n=64000$ 时,一定可以在 $500$ 次内删完.
$Floor\ it$
考虑斐波那契数列的两个特征根 $\phi_1=\frac {1+\sqrt 5} 2,\phi_2=\frac {1-\sqrt 5} 2$ ,其中 $\phi_1$ 就是题目中给出的 $x$ .
构造数列 $a_i=\phi_1^i+\phi_2^i$ ,则 $a$ 有递推式 $a_i=a_{i-1}+a_{i-2},a_1=1,a_2=3$ ,可知 $\forall i\in \mathbb N+,a_i\in \mathbb N+ $.
当 $n$ 为偶数时, $0<\phi_2^n<1,\lfloor x^n\rfloor=a_n-1$ .
当 $n$ 为奇数时, $-1<\phi_2^n<0,\lfloor x^n \rfloor=a_n$ .
用矩阵快速幂 $O(\log n)$ 求 $a_n$ 即可.