HDU 6057 – Kanade’s convolution | 2017 Multi-University Training Contest 3

HDU 6057 – Kanade’s convolution | 2017 Multi-University Training Contest 3

大家好,又见面了,我是全栈君。

/*
HDU 6057 - Kanade's convolution [ FWT ]  |  2017 Multi-University Training Contest 3
题意:
	给定两个序列 A[0...2^m-1], B[0...2^m-1]
	求 C[0...2^m-1]	,满足:
		C[k] = ∑[i&j==k] A[i^j] * B[i|j]
	m <= 19
分析:
	看C[k]的形式与集合卷积的形式接近,故转化式子时主要向普通的集合卷积式方向靠
	与三种位运算都相关的结论是 : i^j + i&j = i|j
	设 x = i^j, y = i|j,则显然 k = y-x,且 k 与 x 互成关于 y 的补集,即 k = x^y 
	
	再来关心给定(x,y),符合 x = i^j, y = i|j的(i,j)对的数目
		注意到相同的位 i&j 是确定的,x = i^j 是i和j不同的位的数目,这部分谁是 0 谁是 1 不固定
			故(i,j)对的数目为 2^bits(x)

	此时重写原式: C[k] = ∑ [k == x^y] [k == y-x] A[x]*2^bits(x) * B[y]
	
	设 A'[x] = A[x]*2^bits(x)
	由于 [k == x^y],第二个条件 [k == y-x] 等价于 bits(k) == bits(y) - bits(x)
		C[k] = ∑ [k == x^y] [bits(k) == bits(x) - bits(y)] A'[x] * B[y]
	
	将 A,B,C三个数组按 bits 划分:
		C[bits(k)][k] = ∑ [k == x^y] A[bits(x)][x]*2^bits(x) * B[bits(y)][y]
	
	最后按不同的维度(bits)做 FWT即可
*/
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 1<<20;
int rev2;
long long inv( long long a , long long m)
{
	if (a == 1) return 1;
	return inv(m%a, m) * (m - m/a) % m;
}
void FWT(int a[], int n) {
    for (int d = 1; d < n; d <<= 1)
        for (int m = d<<1, i = 0; i < n; i += m)
            for (int j = 0; j < d; j++)
            {
                int x = a[i+j], y = a[i+j+d];
                a[i+j] = (x+y) % MOD;
                a[i+j+d] = (x-y+MOD) % MOD;
            }
}
void UFWT(int a[], int n) {
    for (int d = 1; d < n; d <<= 1)
        for (int m = d<<1, i = 0; i < n; i += m)
            for (int j = 0; j < d; j++)
            {
                int x = a[i+j], y = a[i+j+d];
                a[i+j] = 1LL*(x+y) * rev2 % MOD;
                a[i+j+d] = (1LL*(x-y)*rev2 % MOD + MOD) % MOD;
            }
}
int a[20][N], b[20][N], c[20][N];
int bits[N];
int m, n;
void init()
{
    rev2 = inv(2, MOD);
    bits[0] = 0;
    for (int i = 1; i < N; i++) bits[i] = bits[i>>1] + (i&1);
}
int main()
{
    init();
    scanf("%d", &m);
    n = 1<<m;
    for (int i = 0; i < n; i++)
    {
        int x; scanf("%d", &x);
        a[bits[i]][i] = 1LL*x * (1<<bits[i]) % MOD;
    }
    for (int i = 0; i < n; i++)
    {
        int x; scanf("%d", &x);
        b[bits[i]][i] = x;
    }
    for (int i = 0; i <= m; i++) FWT(a[i], n);
    for (int i = 0; i <= m; i++) FWT(b[i], n);
    for (int i = 0; i <= m; i++)
        for (int j = i; j <= m; j++)
            for (int k = 0; k < n; k++)
            {
                c[j-i][k] = (c[j-i][k] + 1LL*a[i][k] * b[j][k] % MOD) % MOD;
            }
    for (int i = 0; i <= m; i++) UFWT(c[i], n);
    long long ans = 0, base = 1;
    for (int i = 0; i < n; i++)
    {
        ans = ( ans + c[bits[i]][i] * base % MOD ) % MOD;
        base = base * 1526 % MOD;
    }
    printf("%lld\n", ans);
}

  

转载于:https://www.cnblogs.com/nicetomeetu/p/7291383.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108268.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Jmm模型_fgls模型

    Jmm模型_fgls模型一、什么是JMM模型Java内存模型(即JavaMemoryModel,简称JMM)本身是一种抽象的概念,并不真实存在,它描述的是一组规则或规范,通过这组规范定义了程序中各个变量(包括实例字段,静态字段和构成数组对象的元素)的访问方式。由于JVM运行程序的实体是线程,而每个线程创建时JVM都会为其创建一个工作内存(有些地方称为栈空间),用于存储线程私有的数据,而Java内存模型中规定所有变…

  • CTR预估算法之FM, FFM, DeepFM及实践

    CTR预估算法之FM, FFM, DeepFM及实践目录目录CTR预估综述FactorizationMachines(FM)算法原理代码实现Field-awareFactorizationMachines(FFM)算法原理代码实现DeepFM算法原理代码实现参考文献CTR预估综述点击率(Clickthroughrate)是点击特定链接的用户与查看页面,电子邮…

  • oracle srvctl命令,用srvctl命令配置service

    oracle srvctl命令,用srvctl命令配置service.用srvctl命令配置service除了用DBCA图形方式,还可以使用命令方式配置service,这种方法对于维护远程尤其有用。无论是创建还是维护都是用一个命令srvctl,先看一下srvctl命令和service相关的语法,如下:创建service[oracle@felix1~]$srvctladdservi.用srvctl命令配置service除了用DBCA图形方式,还可以使用…

  • CMD-NET命令详解[通俗易懂]

    CMD-NET命令详解[通俗易懂]本文转自http://www.cnblogs.com/chenjq0717/archive/2010/05/09/1730934.html  net命令大全,net命令用法,net网络命令,net命令使用,net命令集,net命令介绍,net常用命令,net命令的使用技巧,net命令如何使用 大家在操作Windows9X/NT/2000/XP/2003系统的过程中,都会或多或少

  • 什么是DrawCall?「建议收藏」

    前言游戏开发圈里的人一定听过优化游戏要降低DrawCall,这样到底什么是DrawCall呢?Unity中应该如何降低DrawCall,这里就来讲解一下关于DrawCall知识点。1.是谁拖了后腿?通俗的来说就是Cpu:(#`O′)喂你好,是Gpu吗?快点醒醒我这里又有画画的任务了(Cpu调用Gpu的次数),打一个比方比如上传很多文件到百度云或其他地方时,都会把它压缩到一个文件夹里…

  • tcp四次挥手,为什么是四次?「建议收藏」

    tcp四次挥手,为什么是四次?「建议收藏」四次挥手的原因;为什么要有TIME_WAIT状态?2MSL的的意义;四次挥手中如果有一次挥手失败怎么处理?

发表回复

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

关注全栈程序员社区公众号