题解-Little C Loves 3 III
给定 \(n\) 和序列 \(a_0,a_1,\dots,a_{2^n-1}\) 和 \(b_0,b_1,\dots,b_{2^n-1}\),求序列 \(c_0,c_1,\dots,c_{2^n-1}\) 满足
\[c_i=\left(\sum_{j|k=i,j\&k=0} a_j\cdot b_k\right)\bmod 4
\]
数据范围:\(a_i,b_i\in[0,3]\),\(0\le n\le 21\)。
看到 \(j|k=i\) 便知道要搞个 \(or\) 运算的 \(\texttt{FWT}\),但是如何使得同时满足条件 \(j\&k=0\) 呢?
设 \(bits(x)\) 表示 \(x\) 在二进制下的位数。
考虑如下 \(3\) 个可以利用的因素:
\(\bmod 4\) 相当于在二进制下取两位。
同时满足 \(j|k=i,j\&k=0\) 必有 \(bits(j)+bits(k)=bits(i)\)。
如果满足 \(j|k=i\),且 \(bits(i)\) 一定,必有 \(bits(j)+bits(k)\ge bits(i)\)。
所以可以令 \(f_i=a_i\cdot 4^{bits(i)},g_i=b_i\cdot 4^{bits(i)}\),通过 \(\texttt{FWT}\) 得到 \(ans_i=\sum_{j|k=i}f_j\cdot g_k\),然后最后的答案 \(c_i=\left(\frac{ans_i}{4^{bits(i)}}\right)\bmod 4\)。
抽象地解释一下:
\(\texttt{[]}\) 表示两个二进制位(为 \(0\)),\(\texttt{<>}\) 表示其他(除了答案两位)位的值,是由 \(c_i\) 溢出两位或者由满足 \(bits(j)+bits(k)>bits(i)\) 的 \(j,k\) 变换得的值,可以抛弃。
\(f_j:a_j\underbrace{\texttt{[][]...[][]}}_{bits(j)'s \texttt{[]}}\)
\(g_k:b_k\underbrace{\texttt{[][]...[][]}}_{bits(k)'s \texttt{[]}}\)
\(ans_i:\texttt{<><>...<><>}c_i\underbrace{\texttt{[][]...[][]}}_{bits(i)'s \texttt{[]}}\)
小蒟蒻或许讲不清楚,但我就这个水平了。放代码吧,注意 \(f_j,g_k\) 开 \(\texttt{long long}\)。
//Data
const int M=21,N=1<<M;
int n,m,bit[N+7];
int bits(int x){return (x==0)?0:bit[x]?bit[x]:(bit[x]=bits(x-(x&-x))+1);}
//FWT
void fwt(lng f[],int t){ //or fwt 模板
for(int mid=1;mid<n;mid<<=1)
for(int i=0;i<n;i+=mid<<1)
for(int j=i;j<mid+i;j++) f[mid+j]+=f[j]*t;
}
lng f[N+7],g[N+7],ans[N+7];
//Main
int main(){
n=1<<(m=ri);
for(int i=0,c;i<n;i++){
while(!isdigit(c=fr()));
f[i]=(15ll&c)<<(bits(i)<<1);
//这题是在 CF 上交的,有很多奇奇怪怪的错误,反正这里只能写 15ll&c,写 (lng)(c-'0') 都会挂
}
for(int i=0,c;i<n;i++){
while(!isdigit(c=fr()));
g[i]=(15ll&c)<<(bits(i)<<1);
}
fwt(f,1),fwt(g,1);
for(int i=0;i<n;i++) ans[i]=f[i]*g[i]; // CF 会显示这里挂了
fwt(ans,-1);
for(int i=0;i<n;i++) printf("%lld",(ans[i]>>(bits(i)<<1))&3);
putchar('\n');
return 0;
}
萌新初学多项式,巨佬多多指教,觉得写得不清楚就在评论中随意 \(\texttt{D}\)。祝大家学习愉快!
最新文章
- Kafka 分布式环境搭建
- Flash插件地址
- Operating System Concepts 项目:生产者-消费者问题 线程
- Identity-第二章
- Xcode6中如何修改文件中自动创建的Created by和Copyright
- Solr In Action 笔记(4) 之 SolrCloud分布式索引基础
- Hibernate HQL基础 使用参数占位符
- FreeRTOS--堆内存管理
- Linux--Linux下安装JDk
- 八大排序算法——快速排序(动图演示 思路分析 实例代码Java 复杂度分析)
- cf1000E We Need More Bosses (tarjan缩点+树的直径)
- pip的常用命令
- Linux系统启动和内核管理
- VPC配置介绍
- Redis集群架构【转载】
- Quartz(一):Cron表达式
- python + docker, 实现天气数据 从FTP获取以及持久化(一)
- 原生js三级联动
- cs4.1 编译与安装
- jmeter插件JMeterPlugins-Standard 压力测试