• 周二. 9月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

暑假集训Day22 B (Lucas+SOSDP)

admin

11月 28, 2021

题目链接在这里:200202.pdf (codeforces.com)

这题非常巧妙,首先看到组合数以及奇偶,奇偶的话是与%2有关的,所以想到Lucas定理。

有组合数有模数想Lucas定理!!!!!!!!!!!

Lucas定理展开是这个样子的:

第一项不用看,我们看第二项,为了让结果是奇数,第二项一定要是1,不能是0,所以不能出现当前位n为0,m为1的情况。

然后我们会发现这就是子集枚举DP的板题:

关于子集枚举的解释这里有个图

 参考博客:(7条消息) B – Binomial Gym – 102576B(Lucas定理,SOS DP)_tomjobs的博客-CSDN博客  [算法模板]SOS DP – GavinZheng – 博客园 (cnblogs.com)

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const LL MAX=1e6+5;
 5 LL n,a[MAX],f[MAX],ans,mx;
 6 LL t;
 7 int main(){
 8     freopen ("b.in","r",stdin);
 9     freopen ("b.out","w",stdout);
10     LL i,j;
11     scanf("%lld",&t);
12     while (t--){
13         scanf("%lld",&n);
14         memset(f,0,sizeof(f));
15         mx=0;
16         for (i=1;i<=n;i++){
17             scanf("%lld",a+i);
18             f[a[i]]++;
19             mx=max(a[i],mx);
20         }
21         LL up=log2(mx)+1;
22         for (i=0;i<=up;i++)
23             for (j=1;j<=mx+1;j++)
24                 if (j&(1<<i))
25                     f[j]+=f[j-(1<<i)];
26         ans=0;
27         for (i=1;i<=n;i++)
28             ans+=f[a[i]];
29         printf("%lld
",ans);
30     }
31     return 0;
32 }
未来是什么样,未来会发生什么,谁也不知道。
但是我知道,
起码从今天开始努力,
肯定比从明天开始努力,
要快一天实现梦想。
千里之行,始于足下! ——《那年那兔那些事儿》

发表回复

您的电子邮箱地址不会被公开。