锐客网

  1. 首页 > it技术 > >

CF914G|CF914G Sum the Fibonacci

题目描述：
luogu
题解：
FST+FWT。
FWT_OR+FWT_XOR+FWT_AND=快乐。
首先对于这个式子来说，第一部分是个子集卷积，后面都可以用FWT做。
学了一下FST，它的原理基本是这样的：
子集卷积即$f[i]=\sum\limits_{j \subseteq i}g[j]*h[i-j]$，看起来很像FWT_OR但是有另外条件，即$j\&(i-j)=0$。
vfk爷的论文中提到过一种方法，多加一维去除非法情况。
设$cnt[i]$表示$i$的二进制表示中$1$的个数，那么原来的$f[i]$变为$f[cnt[i]][i]$，
原式变为$f[cnt[i]][i] = \sum\limits_{j \subseteq i} g[cnt[j]][j] * h[cnt[i-j]][i-j]$。
（对于$f[i][j]$，只有当$i=cnt[j]$时才可能有值）
这时我们对于所有$f[i]$做FWT_OR，这样的话每一位上的值是$F[i][j] = \sum\limits_{k \subseteq j} f[i][k]$。
然后直接$F[i][j] = \sum\limits_{k <= i} G[k][j] * H[i-k][j]$。
最后逆变换回去就是$f[i][j]$了。

注意$i<2^{17}$可能会有$17$个$1$。
代码：
CF914G|CF914G Sum the Fibonacci
文章图片
CF914G|CF914G Sum the Fibonacci
文章图片

#include #include #include using namespace std; typedef long long ll; const int N = 1000050; const int M = (1<<17)+50; const int MOD = 1000000007; const int inv_2 = (MOD+1)/2; template inline void read(T&x) { T f = 1,c = 0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){c=c*10+ch-'0'; ch=getchar(); } x = f*c; } templateinline void Mod(T&x){if(x>=MOD)x-=MOD; } int n,len=1<<17,s[M],a[M],b[M],c[M],d[20][M],e[20][M],f[M],cnt[M]; void fwt_xor(int*a,int len,int k) { for(int i=1; i
View Code
【CF914G|CF914G Sum the Fibonacci】转载于:https://www.cnblogs.com/LiGuanlin1124/p/11171164.html

    推荐阅读


    上一篇：亲子日记609天

    下一篇：竞赛系统需求分析