欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P3773 [CTSC2017]吉夫特(Lucas定理,dp)

程序员文章站 2022-10-05 07:58:38
题意 满足$b_1 < b_2 < \dots < b_k$且$a_{b_1} \geqslant a_{b_2} \geqslant \dots \geqslant a_{b_k}$ Sol 组合数取模? 肯定考虑Lucas定理 考虑Lucas定理在最后一步肯定会化为$C(1, 1), C(1, ......

题意

洛谷P3773 [CTSC2017]吉夫特(Lucas定理,dp)

满足$b_1 < b_2 < \dots < b_k$且$a_{b_1} \geqslant a_{b_2} \geqslant \dots \geqslant a_{b_k}$

 

Sol

组合数取模?

肯定考虑Lucas定理

考虑Lucas定理在最后一步肯定会化为$C(1, 1), C(1, 0), C(0, 0), C(0, 1)$。

很显然$C(0,1)$不存在,而其他的都等于$1$,因此当最后分解为$C(0, 1)$的时候不满足条件。

具体怎么判断呢?观察上式可以得到一个普遍的规律:若$C(x, y) \{x = 0, 1 \ y=0,1 \}$,则$x\&y = y$

根据Lucas定理,显然我们可以把这个公式推广开来。

若$C(n,m)$为奇数,则$n \& m = m$

有了这个定理,我们就可以dp了。直接枚举子集就好。

时间复杂度:

枚举子集的复杂度是$O(3^n)$的,在此题中我们需要枚举二进制位,

因此复杂度为$3^{max log233333}$

#include<iostream>
#define LL long long 
using namespace std;
const int mod = 1000000007;
LL f[233334], N, ans = 0;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) {
        int x; cin >> x;
        for(int j = x; j <= 233333; j = j + 1 | x)
            (f[x] += f[j]) %= mod;
        (ans += f[x]) %= mod;
        f[x]++;
    }
    cout << ans;
    return 0;
}