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)


相关推荐

  • javaweb分页显示_java分页查询原理思路

    javaweb分页显示_java分页查询原理思路效果图如下:实现步骤:1.创建实体User.class,参考代码如下:publicclassUser{ privateStringname; privateintage; privateStringgender; publicStringgetName(){ returnname; } publicvoidsetName(Stri…

  • RewriteCond 详解

    RewriteCond 详解RewriteCond重写规则执行条件语法:RewriteCondTestStringCondPattern生效域:serverconfig,virtualhost,directory,.htaccess特别的上面的TestString,可提供反向引用.引用模式为:%N其中N为(0&lt;=N&lt;=9),引用当前若干Rew…

  • Nginx教程_nginx docker

    Nginx教程_nginx dockernginx定时任务完成日志切割date-dyesterdaydate-s’2014-11-2708:55:00’clock-wdate-dyesterday+%Y%m%d–日志脚本#!/bin/bashbase_path=’/usr/local/nginx/logs’log_path=$(date-dyesterday+”%Y%m”)day=$(date-dyeste…

    2022年10月22日
  • Tomcat的下载及安装

    Tomcat的下载及安装一、Tomcat下载1、打开Tomcat官网,默认进入官网首页,官网地址为:https://tomcat.apache.org/2、左侧的导航栏可以看到Download(下载),以及最近相关版本的Tomcat(9、8、7…),这里选择的是Tomcat8,点击进入3、进入tomcat8的相关页面后会显示一些该版本的信息,可以忽略,鼠标下滑进行查找4、这里我们可以看到…

  • 新东方俞敏洪

    新东方俞敏洪新东方俞敏洪作者:郑志颖http://www.caigou.com.cn/news/20170405133.shtml俞敏洪互联网时代的教育技术一个人在具体环境中接受教育,受什么影响?我看受四个因素的影响:时间因素、空间因素、师资因素和工具因素。传…

  • Log4j简单配置

    Log4j简单配置Log4j是一组强大的日志组件,在项目中时常需要用它提供一些信息,这两天学习了一下它的简单配置。第一步,我们需要导入log4j-1.2.14.jar到lib目录下第二步,在src下建立log4j.pr

发表回复

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

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