【CF914G】Sum the Fibonacci 快速??变换模板
模板 快速 The 变换 sum Fibonacci
2023-09-11 14:15:24 时间
【CF914G】Sum the Fibonacci
题解:给你一个长度为n的数组s。定义五元组(a,b,c,d,e)是合法的当且仅当:
1. $1\le a,b,c,d,e\le n$
2. $(s_a|s_b) \& s_c \& (s_d $^$ s_e)=2^i$,i是某个整数
3. $s_a \& s_b=0$
求$\sum f(s_a|s_b) * f(s_c) * f(s_d $^$ s_e)$,f是斐波那契数列,对于所有合法的五元组(a,b,c,d,e)。答案模$10^9+7$。
$1\le n\le 10^6,0\le s_i< 2^{17}$
题解:说白了就是求:子集和卷积,异或卷积,与卷积。后面两个好求,学了一发子集和卷积。说白了就是强行加了一个占位多项式,即将数组多开一维记录子集中1的个数。然后合并时相当于背包合并,时间复杂度$O(n^22^n)$。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long ll; const int maxn=(1<<17)+4; const ll P=1000000007; const ll inv=500000004; ll a[maxn],c[maxn],d[maxn]; ll fa[maxn][18],fb[maxn][18],f[maxn]; ll ans; int cnt[maxn]; int n,len; inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f; } int main() { n=rd(); int h,i,j,k,x,y,v; f[1]=cnt[1]=1; len=1<<17; for(i=2;i<len;i++) f[i]=(f[i-1]+f[i-2])%P,cnt[i]=cnt[i-(i&-i)]+1; for(i=1;i<=n;i++) v=rd(),fa[v][cnt[v]]++,d[v]++,c[v]=(c[v]+f[v])%P; for(h=1;h<len;h<<=1) for(i=0;i<len;i++) if(i&h) for(j=0;j<=17;j++) fa[i][j]=(fa[i][j]+fa[i-h][j])%P; for(i=0;i<len;i++) for(j=0;j<=17;j++) for(k=0;k<=j;k++) fb[i][j]=(fb[i][j]+fa[i][k]*fa[i][j-k])%P; for(h=1;h<len;h<<=1) for(i=0;i<len;i++) if(i&h) for(j=0;j<=17;j++) fb[i][j]=(fb[i][j]-fb[i-h][j]+P)%P; for(i=0;i<len;i++) a[i]=(a[i]+f[i]*fb[i][cnt[i]])%P; for(h=1;h<len;h<<=1) for(i=0;i<len;i++) if(i&h) x=d[i-h],y=d[i],d[i-h]=(x+y)%P,d[i]=(x-y+P)%P; for(i=0;i<len;i++) d[i]=d[i]*d[i]%P; for(h=1;h<len;h<<=1) for(i=0;i<len;i++) if(i&h) x=d[i-h],y=d[i],d[i-h]=(x+y)*inv%P,d[i]=(x-y+P)*inv%P; for(i=0;i<len;i++) d[i]=d[i]*f[i]%P; for(h=1;h<len;h<<=1) for(i=0;i<len;i++) if(!(i&h)) a[i]=(a[i]+a[i+h])%P,c[i]=(c[i]+c[i+h])%P,d[i]=(d[i]+d[i+h])%P; for(i=0;i<len;i++) a[i]=a[i]*c[i]%P*d[i]%P; for(h=1;h<len;h<<=1) for(i=0;i<len;i++) if(!(i&h)) a[i]=(a[i]-a[i+h]+P)%P; for(i=0;i<17;i++) ans=(ans+a[1<<i])%P; printf("%lld",ans); return 0; }
相关文章
- CMS模板引擎:XHtmlAction
- 第三百一十节,Django框架,模板语言
- 使用模板元编程快速的得到斐波那契数。。
- Thinkphp5 实现动态模板主题多个模板切换
- intellij idea:设置java方法注释模板(intellij idea 2019.2)
- 解决 Visual Studio 2013、2015、2017 工具箱不显示ArcGIS 10.2 控件,及ArcGIS模板丢失问题
- 【项目实战】模板引擎Thymeleaf入门介绍
- Python采集ppt素材模板 (多线程版本),答辩、演讲再也不怕没有好用的PPT模板了(含完整源代码)
- linux驱动开发重点关注内容--摘自《嵌入式Linux驱动模板精讲与项目实践》
- 如何在IDEA中自定义模板、快速生成完整的代码?
- DFS 算法模板——二叉树的遍历非递归写法要会,排列组合的一定要自己画一颗树,变量i和当前遍历层数计数的start_index要注意区分
- C++模板的使用
- 785. 快速排序(模板)
- k8s学习之路 | Day13 k8s 模板插件和命令补全
- Zabbix-自定义模板