解题报告-洛谷P3773 [CTSC2017] 吉夫特

P3773 [CTSC2017] 吉夫特

题目描述

简单的题目，既是礼物，也是毒药。

B 君设计了一道简单的题目，准备作为 gift 送给大家。

输入一个长度为 \(n\) 的数列 \(a_1, a_2, \cdots , a_n\) 问有多少个长度大于等于 \(2\) 的不上升的子序列满足：

\[\prod _{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2 = \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \binom{a_{b_{k-1}}}{a_{b_k}} \bmod 2 > 0 \]

输出这个个数对 \(1000000007\) 取模的结果。

G 君看到题目后，为大家解释了一些基本概念。

我们选择任意多个整数 \(b_i\) 满足

\[1 \leq b_1 < b_2 < \dots < b_{k-1} < b_k \leq n \]

我们称 $a_{b_1}, a_{b_2}, \cdots, a_{b_k} $ 是 \(a\) 的一个子序列。

如果这个子序列同时还满足

\[a_{b_1} \geq a_{b_2} \geq \cdots \geq a_{b_{k-1}}\geq a_{b_k} \]

我们称这个子序列是不上升的。

组合数 $\binom {n} {m} $ 是从 \(n\) 个互不相同的元素中取 \(m\) 个元素的方案数，具体计算方案如下：

\[\binom {n}{m}=\frac{n!}{m!(n-m)!}=\frac{n \times (n-1) \times \cdots \times 2 \times 1}{(m \times (m-1) \cdots \times 2 \times 1)((n-m)\times(n-m-1)\times \cdots \times 2 \times 1)} \]

这里要特别注意，因为我们只考虑不上升子序列，所以在求组合数的过程中，一定满足 \(n \geq m\) ，也就是 \(\binom {a_{b_{i-1}}}{a_{b_i}}\) 中一定有 \(a_{b_{i-1}} \geq a_{b_i}\) 。

我们在这里强调取模 \(x \mod y\) 的定义：

\(x \bmod y = x -\left \lfloor \frac{x}{y} \right \rfloor \times y\)

其中 \(\left \lfloor n \right \rfloor\) 表示小于等于 \(n\) 的最大整数。

\(x \bmod 2 > 0\) ，就是在说 \(x\) 是奇数。

与此同时，经验告诉我们一个长度为 \(n\) 的序列，子序列个数有 \(O(2^n)\) 个，所以我们通过对答案取模来避免输出过大。

B 君觉得 G 君说的十分有道理，于是再次强调了这些基本概念。

最后， G 君听说这个题是作为 gift 送给大家，她有一句忠告。

“Vorsicht, Gift!”

“小心. . . . . .剧毒！ ”

输入格式

第一行一个整数 \(n\)。

接下来 \(n\) 行，每行一个整数，这 \(n\) 行中的第 \(i\) 行，表示 \(a_i\)。

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

4
15
7
3
1

输出 #1

11

说明/提示

对于前 \(10\%\) 的测试点，\(n \leq 9\)，\(1\leq a_i\leq 13\)。

对于前 \(20\%\) 的测试点，\(n\leq 17\)，\(1\leq a_i\leq 20\)。

对于前 \(40\%\) 的测试点，\(n\leq 1911\)，\(1\leq a_i\leq 4000\)。

对于前 \(70\%\) 的测试点，\(n\leq 2017\)。

对于前 \(85\%\) 的测试点，\(n\leq 100084\)。

对于 \(100\%\) 的测试点，\(1\leq n\leq 211985\)，\(1\leq a_i\leq 233333\)。所有的 \(a_i\) 互不相同，也就是说不存在 \(i, j\) 同时满足 \(1\leq i < j\leq n\) 和 \(a_i = a_j\)。

---

解题报告

参考题解：题解 P3773 - 洛谷专栏

一道很有意思的数论题。

首先，对于大组合数取模的求解，可以用卢卡斯定理

\[对于质数 p，有： \binom {n}{k} \equiv \binom { \lfloor {n/p} \rfloor } { \lfloor {k/p} \rfloor } \times \binom {n \mod p}{k \mod p} \pmod{p} \]

应用于本题，就有：

\[\binom {n}{k} \equiv \binom {\lfloor n/2 \rfloor}{\lfloor k/2 \rfloor} \times \binom {n \mod 2}{k \mod 2} \pmod{2} \]

对于 \(\dbinom {n \mod 2}{k \mod 2}\) 就只有 \(\dbinom {0}{1}、\dbinom {1}{0}、\dbinom {0}{0}、\dbinom {1}{1}\)，其中 \(\dbinom {0}{1}\) 为 \(0\)，其他都为 \(1\)。

那么就只需考虑 \(\dbinom {\lfloor n/2 \rfloor}{\lfloor k/2 \rfloor}\) ，不断重复这一过程。

我们可以发现，这就是将 \(n\) 和 \(k\) 按二进制从低位一位位的拆解，同时为了使 \(\dbinom {n}{k} \bmod 2 >0\)，其中不应该出现 \(\dbinom {0}{1}\)，即在二进制下的 \(n\) 和 \(k\) 不存在某一位时 \(n\) 为 \(0\) 而 \(k\) 为 \(1\)，如果将一个数的二进制表示视为这个数中 \(1\) 的位置的集合的状压表示，设数 \(x\) 对应的集合为 \(S_x\)，这个表述又等价于：\(S_k\) 是 \(S_n\) 的子集。

将这个性质带入到题目中，如果数列 \(a\) 的一个不上升的子序列 \(a_{b_1},a_{b_2},a_{b_3},\cdots ,a_{b_k}\) 满足要求，必定有 \(S_{a_{b_1}} \supseteq S_{a_{b_2}} \supseteq\cdots \supseteq S_{a_{b_k}}\) 。

可以考虑动态规划，设 \(dp[x]\) 表示前 \(i\) 个数中以数 \(x\) 为结尾的满足要求的不上升子序列数（关于 \(i\) 的维度已省略），根据以上性质，有以下转移方程：

\[dp[x]=\sum dp[y]+1,(S_y \supseteq S_x) \]

接下来统计 \(\sum dp[x]\) 就可以了。

复杂度 \(O(3^{ \max_{i=1}^{n} a_i})\)，代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int mod=(1E+9)+7;
const int N=2501100;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }return f*x;
}int n,ans;
int dp[N];signed main()
{n=read();for(int i=1;i<=n;i++){int x=read();for(int j=x&(x-1);j;j=(j-1)&x)dp[j]=(dp[j]+dp[x]+1)%mod;ans=(ans+dp[x])%mod;}printf("%lld\n",ans);return 0;
}