2024.6.20
T1
题面
给定一个正整数 \(a\)，在区间 \([l,r]\) 中选择一个数 \(b\) 使得 \(a\times b\) 为一个完全平方数，若不存在输出 \(-1\)。共 \(T\) 组测试样例
\(1\le T\le 1000,1\le a\le 10^6,1\le l\le r\le 10^{12}\)
解法
\(\mathcal O(\sqrt a)\) 的去除 \(a\)中的平方因子得到 \(a'\)，查询 \(\lceil\frac l{a'}\rceil\sim \lfloor\frac r{a'}\rfloor\)中最小的完全平方数即可
方法
- 划归思想
T2
题面
求大小为 \(n\) 且满足 \(\gcd S+\operatorname{lcm} S=m\) 的不可重集 \(S\) 的个数对 \(P\) 取模的值
\(1\le n,m\le 10^9,10^8\le P\le 10^9+7,P\in \mathbb P\)
解法
因为 \(\gcd S|m\)，所以可以枚举 \(m\) 的因数确定 \(\gcd S\)，接着得到 \(\operatorname{lcm}S=m-\gcd S\)。可以将每个数除以 \(\gcd S\)，令 \(d=\frac{\operatorname{lcm}S}{\gcd S}\)于是答案转化为选取\(n\) 个 \(d\) 的不同因子，使得其\(\operatorname{lcm}=d，\gcd=1\)。这个推导过程记为\(f(a,b)=f(1,\frac ba)\)
可以考虑分别满足每个限制。
当不考虑任何限制的时候，假设 \(d\) 的因子个数为 \(u\) 方案数为\(f_d={u\choose n}\)
先考虑第一个限制， 因为满足限制的方案数为全部减去不满足的，而\(\operatorname {lcm}\not=d\)说明一定等于 \(d\) 的一个因子，所以 \(f_d\leftarrow f_d-\sum_{i|d}f_i\)，既可以 DP 求到满足第一个限制的方案
再考虑第二个限制，因为 \(f(a,b)=f(1,\frac ba)\)，所以对于 \(\gcd=a,\operatorname{lcm}=b\) 的方案，等价于\(\gcd=1,\operatorname {lcm}=\frac ab\) 的方案，所以只需要让 \(f_d\leftarrow f_d-\sum_{i|d}f_i\)，就行了。
最后 \(f_d\) 就是答案，复杂度 \(\mathcal O((d(n))^3+d(n)\sqrt n)\)，其中 \(d(n)\) 表示 \(n\) 的因子个数，但是常数小，跑不满。
方法
-
容斥
见《容斥问题的几种求法》
-
DP
这道题在因子层面而非质因子层面经行考虑，原因有二
-
本题转化后关心的为全体因子，以质因子考虑太麻烦
-
正是因为在关心因子，所以可以建立之间的转移关系
-
-
方程思想
建立量之间的联系，本题建立的 DP状态转移方程
T3
题面
定义两个 \(01\) 串 \(S,T\) 满足\(S\to T\) 当且仅当 \(S\) 中值为 \(1\) 的下标集合是 \(T\) 中值为 \(1\) 的下标集合的子集，定义\(S\leftarrow T\) 当且仅当 \(T\to S\)。
小诗有一个长为 \(n\) 的 \(01\) 串序列 ，其中每个 \(01\) 串长度为 \(m\)，她想知道有多少子序列
\(1\le p_1<p2<\cdots<p_k\le n\)，使得存在 \(1\le t\le k\) 满足\(s_{p_1}\to s_{p_2}\to\cdots\to s_{p_{t}}\leftarrow s_{p_{t+1}}\leftarrow\cdots\leftarrow s_{p_n}\)。
由于答案过大，你只需告诉她答案 \(\bmod 10^9+7\) 的值。
\(1\le n\le 3\times 10^5,1\le m\le 20\)
解法
可以发现本质上是支持修改的高维前缀和
如果直接高维前缀和，修改复杂度为\(\mathcal O(1)\)，查询复杂度为 \(\mathcal O(2^m)\)，如果每次修改超集，则修改复杂度为 \(\mathcal O(2^m)\)，查询复杂度为 \(\mathcal O(1)\)，考虑将两种算法进行平衡。
我们将前 \(\lfloor\frac m2\rfloor\) 为经行高维前缀和，后\(\lceil\frac m2\rceil\) 经行超集修改，这样单词修改与查询复杂度都是 \(\mathcal O(2^{\frac m2})\) 了。总共复杂度 \(\mathcal O(n2^{\frac m2})\)。
方法
-
根号平衡
假设有算法修改查询复杂度分别为 \(\mathcal O(a),\mathcal O(b)\)，则可以优化成 \(\mathcal O(\sqrt{ab})\)。
T4
题面
对于所有长度为 \(n\) 的 \(01\) 串 \(s\)（下标从 \(1\) 开始），定义 \(f(s)=\sum_i[s_i=0][s_{i+1}=1]i\)，令 \(T\) 表示所有 \(n\) 个 \(0\)，\(m\) 个 \(1\) 的 \(01\) 串集合，求 \(\sum_{s\in T}q^{f(s)}\bmod p\)
\(p,q\in \mathbb P,1\le n,m,q\le 10^9,1\le p\le 10^7\)
解法
并不容易发现并且我也不会用数学归纳法证明答案为 q-组合数 \(\begin{bmatrix}m+n\\n\end{bmatrix}_p\)，利用 q-Lucas 公式:
\[当p,q\in \mathbb P，且p\not =q时\\ \begin{bmatrix}n\\m\end{bmatrix}_p\equiv {\lfloor n/p \rfloor\choose \lfloor m/p \rfloor}\begin{bmatrix}n\bmod p\\m\bmod p\end{bmatrix}_p\pmod p \]可以计算
方法
- 数学归纳