专栏首页数据结构与算法洛谷P3773 [CTSC2017]吉夫特(Lucas定理,dp)

洛谷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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • loj#6032. 「雅礼集训 2017 Day2」水箱(并查集 贪心 扫描线)

    一个连通块的内状态使用两个变量即可维护\(ans\)表示联通块内的最大答案,\(f\)表示联通块内\(k=1\)的数量

    attack
  • 洛谷P4027 [NOI2007]货币兑换(dp 斜率优化 cdq 二分)

    设\(f[i]\)表示到第\(i\)天所持有软妹币的最大数量,显然答案为\(max_{i = 1}^n f[i]\)

    attack
  • 2491 玉蟾宫

    2491 玉蟾宫 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 大师 Master 题目描述 Description   有一天...

    attack
  • 清北集训Day6T1(生成函数)

    听rqy说可以用生成函数做,感觉比较有意思 我们考虑在DP转移的时候, $5,7,9$这三个数是没有限制的 因此他们出现的次数用01串表示的话就是$111111...

    attack
  • BZOJ 1257: [CQOI2007]余数之和sum【神奇的做法,思维题】

    1257: [CQOI2007]余数之和sum Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 4474  So...

    Angel_Kitty
  • 使用Nginx的proxy_cache缓存功能取代Squid|--|下一篇区分桃花和樱花

    Nginx从0.7.48版本开始,支持了类似Squid的缓存功能。这个缓存是把URL及相关组合当作Key,用md5编码哈希后保存在硬盘上,所以它可以支持任意UR...

    后端技术探索
  • 【CodeForces 672B】Different is Good

    因为只能是26个字母,显然大于26的不可能有答案,其它情况ans+=u[i]-1;u[i]是字母出现的次数。

    饶文津
  • 剑指OFFER之从二叉搜索树的后序遍历序列(九度OJ1367)

    题目描述: 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 输入: ...

    用户1154259
  • php按照权重随机

    10,'b'=>20,'c'=>50) * @return string key 键名 */ function roll($weight ...

    苦咖啡
  • 计算字符串相似度算法——Levenshtein

    Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。

    shirayner

扫码关注云+社区

领取腾讯云代金券