题解 CF914G Sum the Fibonacci
2024-10-19 13:49:14
题目大意
给出\(n,s_{1,2,...,n}\),定义一个五元组\((a,b,c,d,e)\)合法当且仅当:
- \[1\le a,b,c,d,e\le n
\] - \[(s_a\vee s_b)\wedge s_c \wedge (s_d\oplus s_e)=2^i,i\in \mathbb{Z}
\] - \[s_a\wedge s_b=0
\]
求出对于所有合法的五元组\((a,b,c,d,e)\):
\[\sum f(s_a\vee s_b)f(s_c)f(s_d\oplus s_e)
\]
\]
其中\(f(i)\)表示第\(i\)位斐波拉契数列。
思路
其实这个题应该算\(\text {FST}\)的入门级题目,也不是很难。
首先,我们定义\(v(a,b,c,d,e)=(s_a\vee s_b)\wedge s_c \wedge (s_d\oplus s_e)\)。于是我们可以把式子写成这样一个形式:
\[\sum_{i} \sum_{v(a,b,c,d,e)=2^i} [s_a\wedge s_b=0]f(s_a\vee s_b)f(s_c)f(s_d\oplus s_e)
\]
\]
\[=\sum_{p} \sum_{i\wedge j\wedge k=2^p} f(i)f(j)f(k)(\sum_{s_a\vee s_b=i,s_a\wedge s_b=0}1)(\sum_{s_a\oplus s_b=k}1)
\]
\]
然后我们就发现第一个括号里面的可以用子集卷积求到,后面那个可以用异或卷积求到,总的又可以用并卷积求到。于是我们就可以在\(\Theta(w\log ^2w)\)的时间内求到了。其中\(w\)是值域。
\(\text {Code}\)
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define inv2 500000004
#define mod 1000000007
#define MAXN 1000005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int lim = 1;
void mul (int &a,int b){a = 1ll * a * b % mod;}
void del (int &a,int b){a = a >= b ? a - b : a + mod - b;}
void add (int &a,int b){a = a + b >= mod ? a + b - mod : a + b;}
void ORFWT (int *A,int type){
for (Int i = 1;i < lim;i <<= 1)
for (Int j = 0;j < lim;j += i << 1)
for (Int k = 0;k < i;++ k)
if (type == 1) add (A[i + j + k],A[j + k]);
else del (A[i + j + k],A[j + k]);
}
void ANDFWT (int *A,int type){
for (Int i = 1;i < lim;i <<= 1)
for (Int j = 0;j < lim;j += i << 1)
for (Int k = 0;k < i;++ k)
if (type == 1) add (A[j + k],A[i + j + k]);
else del (A[j + k],A[i + j + k]);
}
void XORFWT (int *A,int type){
for (Int i = 1;i < lim;i <<= 1)
for (Int j = 0;j < lim;j += i << 1)
for (Int k = 0;k < i;++ k){
int x = A[j + k],y = A[i + j + k];
if (type == 1) A[j + k] = (x + y) % mod,A[i + j + k] = (x + mod - y) % mod;
else A[j + k] = 1ll * (x + y) * inv2 % mod,A[i + j + k] = 1ll * (x + mod - y) * inv2 % mod;
}
}
int n,s,fib[1 << 17],cnt[1 << 17],A[1 << 17],S[1 << 17],f[18][1 << 17],h[1 << 17],sum[1 << 17];
signed main(){
read (n);
fib[0] = 0,fib[1] = cnt[1] = 1;int maxn = 0;
for (Int i = 2;i < (1 << 17);++ i) fib[i] = (fib[i - 1] + fib[i - 2]) % mod,cnt[i] = cnt[i >> 1] + (i & 1);
for (Int i = 1,s;i <= n;++ i) read (s),maxn = max (maxn,s),add (f[cnt[s]][s],1),add (h[s],1),add (sum[s],fib[s]);
int logn = 0;while (lim <= maxn) lim <<= 1,logn ++;
for (Int i = 0;i <= logn;++ i) ORFWT (f[i],1);
for (Int i = 0;i <= logn;++ i){
for (Int j = 0;j < lim;++ j) S[j] = 0;
for (Int j = 0;j <= i;++ j)
for (Int k = 0;k < lim;++ k)
add (S[k],1ll * f[j][k] * f[i - j][k] % mod);
ORFWT (S,-1);
for (Int j = 0;j < lim;++ j) if (cnt[j] == i) add (A[j],S[j]);
}
XORFWT (h,1);
for (Int i = 0;i < lim;++ i) mul (h[i],h[i]);
XORFWT (h,-1);
for (Int i = 0;i < lim;++ i) mul (A[i],fib[i]),mul (h[i],fib[i]);
ANDFWT (A,1),ANDFWT (h,1),ANDFWT (sum,1);
for (Int i = 0;i < lim;++ i) mul (A[i],h[i]),mul (A[i],sum[i]);
ANDFWT (A,-1);
int ans = 0;for (Int i = 1;i < lim;i <<= 1) add (ans,A[i]);
write (ans),putchar ('\n');
return 0;
}
最新文章
- leetcde37. Sudoku Solver
- 工具第二天 cocoaPods 私有库的创建
- 【linux】man和--help
- javascript笔记---貌似大叔
- JavaScript中的运算符种类及其规则介绍
- STM32系统时钟
- linux shell less 命令---转
- Asp.net 实现图片缩放 无水印(方法一)
- 最长回文子串(百度笔试题和hdu 3068)
- C++拾遗(八)类——概念、定义与实现
- (转)js prototype 详解
- input 输入框获得/失去焦点时隐藏/显示文字(jquery版)
- 源码(05) -- java.util.AbstractCollection<;E>;
- oracle和mysql分页
- split函数用法
- 解决CentOS(6和7版本),/etc/sysconfig/下没有iptables的问题
- selenium 定位无标签的元素
- Cmd下修改文件访问控制权限
- Mysql查询缓存Query_cache的功用
- [转载]Browser Link feature in Visual Studio Preview 2013
热门文章
- ES6——简单的多态
- HTML5存储 ——Web Storage(localStorage 和 sessionStorage)
- 100个裁判对n个选手做无并列排名问题探析
- 小程序 读取照片 EXIF 元信息
- vue-class和style样式绑定
- Redis-技术专区-让你彻底会使用“Redis中最陌生且最强大的集合”(ZSET)【前篇】
- 哲学家就餐问题-Java语言实现死锁避免
- 从IT圈“鄙视链”看前端开发有多难?
- webservice学习总结(一)-- WebService相关概念介绍
- Qt 程序发布以及打包成exe安装包