夏晓光(loveJY)的博客

CTSC2017DxTx

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

$\Pi _{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \mod 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}} \mod 2 > 0$

\binom{k}{n}=\frac{n!}{k!(n-k)!}$$假设$n!$2因子数为a,$k!$2因子为b,$(n-c)!$的因子为c 那么如果$\binom{k}{n}$为奇数$a=b+c$ 怎么求$x!$的2因子个数?首先将x除2,相当于提取一个公因数的过程,然后答案就是 $$f(x)=\sum_{i=1}^{inf}{\frac{x}{2^i}}

设g(x)=x,那么

g(x)=g(x/2)+(x/2)+(x mod 2)=\sum_{i=1}^{inf}{\frac{x}{2^i}}+(二进制下1个数)$$所以$x!$的2因子个数就是(x-x在二进制下1个数) 所以$\binom{k}{n}$为奇数条件为n在二进制下1个数+(n-k)在二进制下1的个数 所以我们观察一下n有1个1,k并没有,那么 n: ....0.... k: ....1.... n-k:...11... 所以k和(n-k)二进制下1的个数和一定大于n,所以必须k所有的1~n都有才能符合条件,综上$\binom{k}{n}$是奇数的条件$(n&k)=k$ 那么后面$f_i$表示$a_i$开头子序列个数用桶存一下每个$a_i$出现位置i,计算$f_i$考虑下一个放什么,也就是枚举$a_i$判断能否放在i后面然后统计下方案 复杂度为$O(3^{log{maxa}})$的 code: ```cpp #include<bits/stdc++.h> using namespace std; #define RI register int namespace fastIO { #define BUF_SIZE (1<<19) static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE; inline char nc() { if(p1 == pend) { p1 = buf; pend = buf + fread(buf, 1, BUF_SIZE, stdin); } return *p1++; } inline int read() { int x = 0, f = 1; char s = nc(); for(; !isdigit(s); s = nc())if(f == '-')f = -1; for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0'; return x * f; } } using namespace fastIO; const int P = 1e9 + 7; const int MAXN = 2e5 + 4e4; int a[MAXN], T[MAXN], f[MAXN]; int n, ans; int main() { // freopen("test.in", "r", stdin); n = read(); for(RI i = 1; i <= n; ++i)a[i] = read(), T[a[i]] = i; for(RI i = n; i >= 1; --i) { f[i] = 1; for(RI j = a[i] & (a[i] - 1); j; j = a[i] & (j - 1)) if(T[j] > i)f[i] = (f[i] + f[T[j]]) % P; ans = (ans + f[i]) % P; } ans = (ans - n + P) % P; printf("%d\n", ans); return 0; } ```