题目来源: 2019-2020 XX Opencup GP of Tokyo: E. Count Modulo 2

题目链接: http://codeforces.com/gym/102586/problem/E

题面

一共 \(T\) 组数据.

现有 \(k\) 个 两两不同 的数字 \(A_1,A_2,\cdots,A_k\). 给定正整数 \(N,S\), 构造数列 \(a_1,a_2,\cdots,a_N\), 满足下列条件:

  1. \(\displaystyle\sum_{i=1}^Na_i=S\).
  2. \(\forall i\in[1,N]\), \(a_i\in\{A_1,A_2,\cdots,A_k\}\).

求构造的方案数在模 \(\mathbf 2\) 意义下的结果.

数据范围

\[ 1\le T\le 5 \]

\[ 1\le N\le10^{18} \]

\[ 0\le S\le 10^{18} \]

\[ 1\le k\le 200 \]

\[ 0\le A_1<A_2<\cdots<A_k\le10^5 \]

题解

组合数学计算

若数列 \(a\) 满足题设条件, 则 \(a\) 由若干个 \(A_1,A_2,\cdots,A_k\) 组成. 设 \(a\) 由 \(t_i\) 个 \(A_i\) (\(i=1,2,\cdots,k\)) 组成, 则由题意有: \[ \begin{aligned} t_1A_1+t_2A_2+\cdots+t_kA_k&=S\\ t_1+t_2+\cdots+t_k&=N \end{aligned}\tag1 \] 由于数列中的元素顺序任意交换后仍满足条件. 于是将命题 \((1)\) 对应的数列归为一类, 则这样的一类中的数列数量, 依组合数学, 可知: \[ C=\frac{N!}{t_1!t_2!\cdots t_k!} \] 注意到只考虑模 \(2\) 意义下的结果, 于是只考虑 \(C\bmod 2\ne0\) 的情况即可. 由于模数为 \(2\), 只要 \(C\bmod2\ne0\), 就一定有 \(C\bmod2=1\), 对结果的贡献为 \(1\).

二进制拆位

定理

\(n!\) 的标准分解式为: \[ n!=\prod_{p}{p^{\alpha(p,n)}} \] \[ \newcommand{\flor}[1]{\left\lfloor #1 \right\rfloor}\alpha(p,n)=\sum_{i}{\left\lfloor\frac{n}{p^i}\right\rfloor} \] 由上述定理, \(C\) 的标准分解式为: \[ C=\prod_{p}{p^{A_p}} \] \[ \begin{aligned} A_p&=\sum_{i}{\flor{\frac{N}{p^i}}}-\sum_{j=1}^k\sum_{i}{\flor{\frac{t_j}{p^i}}}\\ &=\sum_{i}\left(\flor{\frac{N}{p^i}}-\sum_{j=1}^k\flor{\frac{t_j}{p^i}}\right) \end{aligned} \]

于是, 对于任意素数 \(p\), \(C\bmod p\ne0\) 的充分必要条件是 \(A_p=0\).

由于 \(\forall i\), \[ \sum_{j=1}^k\flor{\frac{t_j}{p^i}}\le\flor{\sum_{j=1}^k\frac{t_j}{p^i}}=\flor{\frac{N}{p^i}}\tag2 \] 于是 \(A_p=0\) 的充分必要条件是: \(\forall i\), \((2)\) 式等号成立.

从 \(p\) 进制数运算的角度来看, \(\flor{x/p^i}\) 就是 \(x\) 的 \(p\) 进制数去掉低 \(i\) 位的结果, 等号成立的条件就是 \(t_1,t_2,\cdots,t_k\) 的低 \(i\) 位之和不会在第 \(i+1\) 位上产生进位. 因为: \[ \flor{\frac{N}{p^i}}=\flor{\sum_{i=1}^k\frac{t_j}{p^i}}=\sum_{j=1}^k\flor{\frac{t_j}{p^i}}+\flor{\sum_{j=1}^k\left\{\frac{t_j}{p^i}\right\}} \] 其中: \(\{x\}\) 表示 \(x\) 的小数部分, \(\displaystyle\flor{\sum_{j=1}^k\left\{\frac{t_j}{p^i}\right\}}\) 就是产生的进位.

由于 \(\forall i\), 第 \(i\) 位都不产生进位, 若用 \(x[i]\) 表示 \(x\) 的第 \(i\) 位数字 (最低位为 \(0\)), 则可以得到 \(\forall i\), \[ \sum_{j=1}^kt_j[i]=N[i] \] 对于上述命题, 考虑 \(p=2\) 的特例, 有一个比较好的性质: \(C\bmod 2\) 的结果只有 \(0,1\) 两种取值. \(\forall i\), \(N[i]\) 只有 \(0,1\) 两种取值. 若 \(N[i]=0\), 则 \(t_1[i]=t_2[i]=\cdots=t_k[i]=0\). 否则, \(t_1[i],t_2[i],\cdots,t_k[i]\) 中有且仅有一个 \(1\). 这时, 讨论 \(t_1[i],t_2[i],\cdots,t_k[i]\) 哪个是 \(1\) 即可. 如果 \(t_{xi}[i]=1\), 则会带来 \(2^{i-1}A_{xi}\) 的贡献. 于是只需要讨论, 有多少种 \(A_{x1}, A_{x2},\cdots\) 的选择方案, 使得 \[ \sum_{N[i]=1}2^{i-1}A_{xi}=S \] 即可.

背包问题转化

对于选择方案, 其实本质是一个背包问题: 对于重量为 \(2^{i-1}\) 的物品, 若 \(N[i]=1\), 则你可以选择 \(A_1,A_2,\cdots,A_k\) 个, 否则不能选择; 最终让背包容量为 \(S\). 令 \(dp(i,v)\) 为考虑了 \(i\) 位, 且已占用背包容量为 \(v\) 的方案数, 则状态转移为: \[ dp(i,v)=\begin{cases} \displaystyle \sum_{j=1}^kdp(i-1,v-2^{i-1}A_j)& N[i]=1\\ dp(i-1,v)&N[i]=0 \end{cases} \]

或者写为 \[ dp(i,v)\stackrel{+}\longrightarrow \begin{cases} dp(i+1,v+2^i A_j)&j=1,2,\cdots,k&N[i]=1\\ dp(i+1,v)&&N[i]=0 \end{cases} \]

最终答案为 \(dp(\flor{\log N}+1,S)\). 时间复杂度为 \(O(kS\log N)\), 不能接受, 考虑优化.

二进制优化

注意到考虑了 \(i\) 位后, 低 \(i\) 位的值不再改变. 我们只需要考虑低 \(i\) 位与 \(S\) 的低 \(i\) 位相同的情况即可, 转移的时候不需要再考虑这些, 这样我们只需要记录 \(v\) 去掉低 \(i\) 位后的值 \(v'\) 即可.

记 \(v=2^{i-1}v'+S\bmod 2^{i-1}\), 于是状态转移变成了: \[ dp(i,v')= \begin{cases} \displaystyle\sum_{j=1}^kdp(i-1,2v'+S[i]-A_j)&j=1,2,\cdots,k&N[i]=1\\ dp(i-1,2v'+S[i])&&N[i]=0 \end{cases} \] 或者写为: \[ dp(i,v')\stackrel{+}\longrightarrow \begin{cases} \displaystyle dp\left(i+1,\frac{v'+A_j-S[i]}2\right)&j=1,2,\cdots,k&N[i]=1\\ \displaystyle dp\left(i+1,\frac{v'-S[i]}2\right)&&N[i]=0 \end{cases}\tag3 \] 最终答案即 \(dp(\flor{\log N}+1, 0)\). 记 \(\boldsymbol A:=\{A_1,A_2,\cdots,A_k\}\), \(\bar A=\sup\boldsymbol A\) 若 \(v'\le\bar A\), 则 \[ \frac{v'+A_j-S[i]}{2}\le\frac{\bar A+\bar A-S[i]}{2}\le\bar A \] 由于状态边界 \(dp(0,0)=1\) 的 \(v'=0\le\bar A\), 于是所有有效的状态都满足 \(v'\le\bar A\), 状态转移时 \(v'>\bar A\) 的情况不再考虑. 于是时间复杂度为 \(O(k\bar A\log N)\), 空间复杂度 \(O(\bar A\log N)\).

Bitset 优化

由于动态转移的过程是模 \(2\) 意义下的加法, 本质上是 \(0,1\) 之间的异或, 自然考虑 bitset 优化的可能性. bitset 可以快速地进行整体异或, 左移, 右移等操作. 如何利用这个特性呢? 注意到下标的整体转移可以左移右移, 而 \((3)\) 式的分子就是整体转移, 于是考虑先整体转移再除以 \(2\) 的中间状态.

记 \(tdp(i,v')=dp(i,v'/2)\), 这样 \((3)\) 式的状态转移就可以写成: \[ dp(i,v')\stackrel{+}\longrightarrow \begin{cases} \displaystyle tdp\left(i+1,v'+A_j\right)&j=1,2,\cdots,k&N[i]=1\\ \displaystyle tdp\left(i+1,v'\right)&&N[i]=0 \end{cases}\tag3 \]

\[ tdp(i+1,v')\stackrel{+}\longrightarrow dp\left(i+1,\flor{\frac{v'}2}\right)\quad v'[0]=S[i] \]

\[ dp(i+1,v')=tdp(i+1,2v'+S[i])\tag4 \]

\((3)\) 式的转移可以通过右移, 进行整体转移, 这一步是 \(O(k\bar A)\) 的, 但是获得了 \(1/64\) 的常数. \((4)\) 式的转移可以直接每一位计算, 这一步是 \(O(\bar A)\) 的. 于是整体复杂度获得了 \(1/64\) 的常数, 速度加快了.

注意: \(dp\) 的 \(v'\le\bar A\), 于是中间状态 \(tdp\) 的 \(v'\le2\bar A\). bitset 类的长度应该为 \(2\bar A\).

代码实现

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int as[210], ck[64], cks[64];
const int mxn = 2.05e5;
bitset<mxn> dp[64], tdp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        ll n, s, k;
        cin >> n >> s >> k;
        for (int i = 0; i < k; ++i)
            cin >> as[i];
        for (ll i = 0; i < 63; ++i)
            if ((n >> i) & 1ll)
                ck[i] = 1;
        for (ll i = 0; i < 63; ++i)
            if ((s >> i) & 1ll)
                cks[i] = 1;
        dp[0].set(0);
        int frm;
        for (int i = 0; i <= 62; ++i)
        {
            if (ck[i])
                for (int j = 0; j < k; ++j)
                    tdp ^= (dp[i] << as[j]);
            else
                tdp = dp[i];
            for (int kp = cks[i]; kp < mxn; kp += 2)
                dp[i + 1][kp >> 1] = tdp[kp];
            tdp.reset();
        }
        cout << dp[63][0] << "\n";
        for (int i = 0; i < 64; ++i)
            dp[i].reset();
        memset(ck, 0, sizeof(ck));
        memset(cks, 0, sizeof(cks));
    }
    return 0;
}

花絮

二进制优化的题目很多, 我的思路来自 XJTUOJ-1046 mob的科学麻将, 这也是一道经典的二进制优化的题目. 题目链接: https://oj.xjtuicpc.com/problem/1046. 本题的题解可以见本人编写的《小学期实录》第91页.

这道题调了许多时间, 少任意一个优化, 或者数组开小了, 都会造成 Wrong Answer 或者 Time Limit Exceeded.