Description
简单的题目,既是礼物,也是毒药。
B 君设计了一道简单的题目,准备作为 (gift) 送给大家。
输入一个长度为 (n) 的数列(a_1,a_2,…,a_n)
问有多少个长度大于等于 2 的不上升的子序列 (a_{b_1},a_{b_2},…,a_{b_k}) 满足
这里要特别注意,因为我们只考虑不上升子序列,所以在求组合数的过程中,一定满足 (ngeqslant m),也就是 (inom{a_{b_i}−1}{a_{b_i}}) 中一定有 (a_{b_i}−1geqslant a_{b_i})。
我们在这里强调取模 (x\%y) 的定义:
其中 (lfloor n
floor) 表示小于等于 (n) 的最大整数。
(x\%2>0),就是在说 (x) 是奇数。
与此同时,经验告诉我们一个长度为 (n) 的序列,子序列个数有 (O(2n)) 个,所以我们通过对答案取模来避免输出过大。
B 君觉得 G 君说的十分有道理,于是再次强调了这些基本概念。
最后,G 君听说这个题是作为 (gift) 送给大家,她有一句忠告。
"Vorsicht, Gift!"
“小心……剧毒!”
Input
第一行一个整数 (n) 。
接下来 (n) 行,每行一个整数,这 (n) 行中的第 (i) 行,表示(a_i)。
Output
一行一个整数表示答案。
Sample Input
4
15
7
3
1
Sample Output
11
HINT
- 对于前 10% 的测试点,(nleqslant 9,1leqslant a_ileqslant 13);
- 对于前 20% 的测试点,(nleqslant 17,1leqslant a_ileqslant 20);
- 对于前 40% 的测试点,(nleqslant 1911,1leqslant aileqslant 4000);
- 对于前 70% 的测试点,(nleqslant 2017);
- 对于前 85% 的测试点,(nleqslant 100084);
- 对于 100% 的测试点, (1leqslant nleqslant 211985,1leqslant a_ileqslant 233333)。所有的(a_i)互不相同,也就是说不存在(i,j)同时满足(1leqslant i<jleqslant n)和(a_i=a_j)。
题目说了(\%2),那不就是要=1就好了。然后组合数(inom{m}{n}\%2),嗯,Lucas定理啊。。。然后这不就只剩4种情况了?(inom{0}{0}=1,inom{1}{0}=1,inom{0}{1}=1,inom{1}{1}=1),就一个等于0,肯定就它不能出现对吧?那就是不能存在(a_{b_i})为偶,(a_{b_{i+1}})为奇的情况。但其实,这个性质没啥作用。。。
我们换个方向考虑,从Lucas定理的角度考虑,我们知道Lucas定理是:(inom{m}{n}\%2=inom{lfloorfrac{m}{2}
floor}{lfloorfrac{n}{2}
floor}\%2 imesinom{m\%2}{n\%2}),然后这个是不是很熟悉?二进制分解!如果说存在某一位(m)为1,(n)不为1,那么,答案就为0了。所以,答案不为0的情况,当且仅当(n&m=m),答案为1。所以我们可以直接枚举一个集合的超集转移过来,或者枚举一个集合的子集,转移过去。
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=211985,M=233333,p=1e9+7;
int f[M+10],val[N+10];
bool vis[M+10];
int main(){
int n=read(),Ans=0;
for (int i=1;i<=n;i++) f[val[i]=read()]=1;
for (int i=1;i<=n;i++){
int sta=val[i];
for (int s=(sta-1)&sta;s;s=(s-1)&sta){
if (vis[s]) continue;
f[s]=(f[s]+f[sta])%p;
}
vis[sta]=1;
}
for (int i=1;i<=n;i++) Ans=(Ans+f[val[i]])%p;
printf("%d
",(Ans-n+p)%p);
return 0;
}