专栏首页数据结构与算法BZOJ2194: 快速傅立叶之二(NTT,卷积)

BZOJ2194: 快速傅立叶之二(NTT,卷积)

Time Limit: 10 Sec  Memory Limit: 259 MB

Submit: 1776  Solved: 1055

[Submit][Status][Discuss]

Description

请计算C[k]=sigma(a[i]*b[i-k]) 其中 k < = i < n ,并且有 n < = 10 ^ 5。 a,b中的元素均为小于等于100的非负整数。

Input

第一行一个整数N,接下来N行,第i+2..i+N-1行,每行两个数,依次表示a[i],b[i] (0 < = i < N)。

Output

输出N行,每行一个整数,第i行输出C[i-1]。

Sample Input

5 3 1 2 4 1 1 2 4 1 4

Sample Output

24 12 10 6 1

HINT

Source

题目中给的公式不好搞

我们按照套路,将$B$翻转一下

$$C(k) = \sum_0^n a_i * b_{n - 1 - i + k}$$

此时后面的式子就只与$k$有关了

设$$D(n - 1 + k) = \sum_0^n a_i * b_{n - 1 - i + k}$$

直接NTT

#include<cstdio>
#define swap(x,y) x ^= y, y ^= x, x ^= y
#define LL long long 
using namespace std;
const int MAXN = 3 * 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();
    return x * f;
}
const int P = 998244353, g = 3, gi = 332748118;
int N;
int 
LL a[MAXN], b[MAXN], r[MAXN];
LL fastpow(LL a, int p, int mod) {
    LL base = 1;
    while(p) {
        if(p & 1) base = (base * a) % mod;
        a = (a * a) % mod; p >>= 1;
    }
    return base % mod;
}
LL NTT(LL *A, int type, int N, int mod) {
    for(int i = 0; i < N; i++) 
        if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < N; mid <<= 1) {
        LL W = fastpow( (type == 1) ? g : gi, (P - 1) / (mid << 1), mod ); 
        for(int j = 0; j < N; j += (mid << 1)) {
            int w = 1; 
            for(int k = 0; k < mid; k++, w = (w * W) % P) {
                LL x = A[j + k] % P, y = w * A[j + k + mid] % P;
                A[j + k] = (x + y) % P;
                A[j + k + mid] = (x - y + P) % P;
            } 
        }
    }
    if(type == -1) {
        LL inv = fastpow(N, mod - 2, mod);
        for(int i = 0; i < N; i++)
            A[i] = (A[i] * inv) % mod;
    }
}
int main() {
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    N = read();
    for(int i = 0; i < N; i++) 
        a[i] = read(), b[N - i] = read();
    int limit = 1, L = 0;
    while(limit <= N + N) limit <<=1, L++;
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
    NTT(a, 1, limit, P); NTT(b, 1, limit, P);
    for(int i = 0; i <  limit; i++) a[i] = (a[i] * b[i]) % P;
    NTT(a, -1, limit, P);
    for(int i = 0; i < N * 2; i++)
        printf("%d\n",a[i] % P);
    return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ1030: [JSOI2007]文本生成器(AC自动机)

      JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群, 他们现在使用的是GW文本生成器v6版。该软件可以随机...

    attack
  • BZOJ4337: BJOI2015 树的同构(hash 树同构)

    attack
  • P3709 大爷的字符串题(50分)

    题目背景 在那遥远的西南有一所学校 /*被和谐部分*/ 然后去参加该省省选虐场 然后某蒟蒻不会做,所以也出了一个字符串题: 题目描述 给你一个字符串a,每次询问...

    attack
  • 【计算机本科补全计划】CCF计算机职业资格认证 2016-04-1/2(俄罗斯方块)详解

    正文之前 果然,上一篇文章结尾的预言果然一语成谶,2016-09-4我果然没做出来。没错,昨晚到现在都没有做出来,当然,也是我做了一晚上心灰意冷,然后去欺负本文...

    用户1687088
  • 基础练习 字母图形

    ABCDEFG BABCDEF CBABCDE DCBABCD EDCBABC

    刘开心_1266679
  • POJ 2531

    瑾诺学长
  • BZOJ1030: [JSOI2007]文本生成器(AC自动机)

      JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群, 他们现在使用的是GW文本生成器v6版。该软件可以随机...

    attack
  • 快速傅里叶变换FFT& 数论变换NTT

    0(000)2(010)4(100)6(110),1(001)3(011)5(101)7(111)

    饶文津
  • BZOJ4337: BJOI2015 树的同构(hash 树同构)

    attack
  • P3709 大爷的字符串题(50分)

    题目背景 在那遥远的西南有一所学校 /*被和谐部分*/ 然后去参加该省省选虐场 然后某蒟蒻不会做,所以也出了一个字符串题: 题目描述 给你一个字符串a,每次询问...

    attack

扫码关注云+社区

领取腾讯云代金券