ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共7篇）

luogu[愚人节题目3]现代妖怪殖民地 NTT

U34272 [愚人节题目3]现代妖怪殖民地 fft 题目链接 https://www.luogu.org/problemnew/show/U34272 思路虽然是个py题。 ntt(或者fft)模板题,可能稍不注意就会T 代码 #include <bits/stdc++.h&g...

ntt

2019-04-12

0 562

luoguP1919 A*B Problem升级版 ntt

luoguP1919 A*B Problem升级版链接 luogu 思路 ntt模板题代码 #include <bits/stdc++.h> #define ll long long using namespace std; const int N=3e5+7,mod=9...

ntt

2019-04-12

0 583

CF 528D. Fuzzy Search NTT

CF 528D. Fuzzy Search NTT 题目大意给出文本串S和模式串T和k，S,T为DNA序列(只含ATGC)。对于S中的每个位置\(i\)，只要中[i-k,i+k]有一个位置匹配了字符\(i\)，那么就认为\(i\)可以匹配。求S中有多少位置匹配了T。思路一共有四个字母，...

ntt

2019-04-14

0 685

bzoj2194 快速傅立叶之二 ntt

bzoj2194 快速傅立叶之二链接 bzoj 思路对我这种和式不强的人，直接转二维看。发现对\(C_k\)贡献的数对(i,j),都是右斜对角线。既然贡献是对角线，我们可以利用对角线的性质了。不过右斜角线不太好，我们把每一行都reverse一下，换成左斜角线。对角线上\(i+j\...

ntt

2019-04-12

0 564

loj#2020 「AHOI / HNOI2017」礼物 ntt

loj#2020 「AHOI / HNOI2017」礼物链接 bzoj没\(letex\),差评 loj luogu 思路最小化\(\sum\limits_1^n(a_i-b_i)^2\) 设改变量为k \(\sum\limits_1^n(a_i-(b_i+k))^2\) \(\sum\...

ntt

2019-04-13

0 567

UVA - 12298 Super Poker II NTT

UVA - 12298 Super Poker II NTT 链接 Vjudge 思路暴力开个桶，然后统计，不过会T，用ntt或者fft，ntt用个大模数就行了，百度搜索"NTT大模数"。错误我也不知道，改着改着自己就A了思路 #include <b...

ntt

2019-04-18

0 539

luoguP4721 【模板】分治 FFT

P4721 【模板】分治 FFT 链接 luogu 题目描述给定长度为 \(n-1\) 的数组 \(g[1],g[2],..,g[n-1]\)，求 \(f[0],f[1],..,f[n-1]\)，其中 \[f[i]=\sum_{j=1}^if[i-j]g[j]\] 边界为 \(f[0]=1...

ntt 分治

2019-07-18

1 848