电子产品展示网站,销客多微分销系统,长春集团网站建设,怎么给网站做访问量干货满满的良心博客传送至只有小怪的村庄——请开始你的逆天之路A#xff1a;P1919B#xff1a;P4157刷怪升级——转战玄灵大陆C#xff1a;P6300D#xff1a;P3763E#xff1a;P3321F#xff1a;P5641G#xff1a;P4986H#xff1a;P4721——获得知识药剂一瓶——分治…
干货满满的良心博客传送至只有小怪的村庄——请开始你的逆天之路AP1919BP4157刷怪升级——转战玄灵大陆CP6300DP3763EP3321FP5641GP4986HP4721——获得知识药剂一瓶——分治FFTFFTFFTIP3338JP4173KP5748LP3702MP5667NP4245——拾得知识药丸一颗——三模数NTTNTTNTTOP5488PP4199QP4061缘遇逆天秘籍——金牌打野RP4841S[UVA4671]K-neighbor substringsTSP8372 TSUM - Triple SumsU[CodeChef - COUNTARI]Arithmetic ProgressionsVCodeForces528D Fuzzy SearchWCodeForces 954I Yet Another String Matching Problem因为对卷积还不是很清楚所以开始疯狂的刷题之路会慢慢更新的。 前面没有来源标注的题目题号洛谷上面都有。 FFT,NTTFFT,NTTFFT,NTT是卷积运算中常见的优化→O(nlogn)\rightarrow O(nlogn)→O(nlogn) 因为文字量极大很有可能会有细节错误欢迎指出谢谢o(·ω·)m 传送至只有小怪的村庄——请开始你的逆天之路
AP1919
【模板】A*B Problem升级版FFT快速傅里叶
将输入的a,ba,ba,b每一位拆成对应的多项式系数
手玩一下普通乘法的计算法则发现从左到右对应多项式次数从0,n−10,n-10,n−1依次递增
两数相乘是符合卷积形式下标是相加的
所以将这个串反转从左到右从000开始编号
然后套FFTFFTFFT跑出乘积结果再转回系数表达式
此时某些位置上的值可能很大这就涉及到进位的问题
从左到右扫一遍即可完成进位
最后倒着输出便是ACACAC
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 4000100
struct complex {double x, i;complex(){}complex( double X, double I ) {x X, i I;}
}A[maxn], B[maxn];double pi acos( -1.0 );complex operator ( complex a, complex b ) {return complex( a.x b.x, a.i b.i );
}complex operator - ( complex a, complex b ) {return complex( a.x - b.x, a.i - b.i );
}complex operator * ( complex a, complex b ) {return complex( a.x * b.x - a.i * b.i, a.x * b.i a.i * b.x );
}char a[maxn], b[maxn];
int r[maxn], ans[maxn];
int len;void FFT( complex *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x v[j k], y v[j k i] * w;v[j k] x y;v[j k i] x - y;}}}
}int main() {scanf( %s %s, a, b );int n strlen( a ), m strlen( b );for( int i 0;i n;i ) A[n - i - 1] complex( a[i] - 0, 0 );for( int i 0;i m;i ) B[m - i - 1] complex( b[i] - 0, 0 );len 1; int l 0;while( len ( n m ) ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );FFT( A, 1 );FFT( B, 1 );for( int i 0;i len;i )A[i] A[i] * B[i]; FFT( A, -1 );for( int i 0;i len;i )ans[i] ( A[i].x / len 0.5 );for( int i 0;i len;i )if( ans[i] 9 ) ans[i 1] ans[i] / 10, ans[i] % 10;while( ! ans[len - 1] ) len --;for( int i len - 1;~ i;i -- )printf( %d, ans[i] );return 0;
}BP4157
[SCOI2006]整数划分
这道题显然大整数是可做的
但是都学到现在了一般我是不怎么打大整数的而且现在可能也打不出来
有个结论尽可能得分333最后若是4/24/24/2就不分了
这个结论不需要证吧考场上肯定是找规律找出来的
可以套在FFTFFTFFT上不就是多项式只有个常数项罢了照样可以算
xxx个333求乘积就对FFTFFTFFT进行快速幂处理进位问题即可 刷怪升级——转战玄灵大陆
CP6300
悔改
第一次见到这种应用记在小本本上 ✍
想了一会儿列了个n3n^3n3的dpdpdp转移只能搞555分✧*٩(㉨)و✧ 果断放弃
然后木头拼接起来长度相加突然想到了生成函数
发现可以用长度为iii的木头数量作为xix^ixi的系数两端拼在一起就是生成函数的二次幂
火速开敲马上测样例(⊙_⊙;)393\ 93 9怎么肥事
仔细想了一下ε(д*)…两个长度为111的木头和一个长度为888的木头拼接了算成了两根新木头但是按题目来说必须有一个长度111木头不用
。)#)))≦我陷入了沉思……
我应该取两种拼接木头个数更少的一方但是这样子怎么写呢 到此为止我走向了题解 一类取min类型的卷积到普通乘法卷积的转化
∑ijkmin(toti,totj)∑d1∑ijk[ai≥d][aj≥d]\sum_{ijk}min(tot_i,tot_j)\sum_{d1}\sum_{ijk}[a_i\ge d][a_j\ge d]∑ijkmin(toti,totj)∑d1∑ijk[ai≥d][aj≥d]
也就是说枚举木头个数每次都卷积
Fd(x)∑[ai≥d]xiF_d(x)\sum[a_i\ge d]x^iFd(x)∑[ai≥d]xi
ansk12∑d1[xk]Fd(x)2ans_k\frac{1}{2}\sum_{d1}[x^k]F_d(x)^2ansk21∑d1[xk]Fd(x)2
将tottottot数组离散化直接暴力卷积
据题解说本质不同的FdF_dFd是O(n)O(\sqrt{n})O(n)最坏情况为12...O(D2)12...O(D^2)12...O(D2)
复杂度O(mnlogm)O(m\sqrt{n}logm)O(mnlogm)常数不大 现在才明白为什么有的题目明明没有取模也有题解代码用的NTTNTTNTT 因为NTTNTTNTT不用敲复数那么多玩意儿 只需要取一个非常大的模数使得答案永远不可能超过即可 妙(・。・) #include cmath
#include cstdio
#include iostream
#include algorithm
using namespace std;
#define maxn 400100
struct complex {double x, i;complex(){}complex( double X, double I ) { x X, i I;}
}A[maxn];const double pi acos( -1.0 );complex operator ( complex a, complex b ) {return complex( a.x b.x, a.i b.i );
}complex operator - ( complex a, complex b ) {return complex( a.x - b.x, a.i - b.i );
}complex operator * ( complex a, complex b ) {return complex( a.x * b.x - a.i * b.i, a.x * b.i a.i * b.x );
}int n, m, len;
int tot[maxn], r[maxn], ans[maxn], tmp[maxn];void FFT( complex *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x v[j k], y v[j k i] * w;v[j k] x y;v[j k i] x - y;}}}
}int main() {scanf( %d %d, n, m );for( int i 1, x;i n;i ) {scanf( %d, x );tot[x] ;}len 1; int l 0;while( len ( m 1 ) ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int i 1;i m;i ) tmp[i] tot[i];sort( tmp 1, tmp m 1 );int T unique( tmp 1, tmp m 1 ) - tmp - 1;for( int i 1;i T;i ) {for( int j 0;j len;j )A[j] complex( tot[j] tmp[i], 0 );FFT( A, 1 );for( int j 0;j len;j )A[j] A[j] * A[j];FFT( A, -1 );for( int j 0;j len;j )ans[j] ( tmp[i] - tmp[i - 1] ) * int( A[j].x / len 0.5 );}int maxx 0, ansLen;for( int i 0;i len;i )if( ans[i] / 2 maxx ) maxx ans[i] / 2, ansLen i;printf( %d %d\n, maxx, ansLen );return 0;
}DP3763
[TJOI2017]DNA
曾经放在后缀数组板块的题又被拉出来处决了不应该是来处决我了
字符集大小只有{A,T,G,C}\{A,T,G,C\}{A,T,G,C}考虑分开枚举处理 等于枚举字符的设为111反之为000
以样例‘C’‘C’‘C’为例
S0:ATCGCCCTAS_0:ATCGCCCTAS0:ATCGCCCTA
S:CTTCAS\ \ :CTTCAS :CTTCA
S0:001011100S_0:001011100S0:001011100
S:10010S\ \ :10010S :10010
假设S0S_0S0的长度为nnnSSS的长度为mmm
对于S0[k,km−1]S_0[k,km-1]S0[k,km−1]与S[0,m−1]S[0,m-1]S[0,m−1]相同字符的个数则表示∑i0m−1S0[ik]∗S[i]\sum_{i0}^{m-1}S_0[ik]*S[i]∑i0m−1S0[ik]∗S[i]
令T[m−i−1]S[i]T[m-i-1]S[i]T[m−i−1]S[i]代替SSS式子可化为∑i0m−1S0[ik]∗T[m−i−1]\sum_{i0}^{m-1}S_0[ik]*T[m-i-1]∑i0m−1S0[ik]∗T[m−i−1]
发现此时是可以FFTFFTFFT卷积的将下标看作多项式xix^ixi
∑ijmk−1S0[i]∗T[j]\sum_{ijmk-1}S_0[i]*T[j]∑ijmk−1S0[i]∗T[j]
对于四种字符FFTFFTFFT做四遍加在一起就是子串与碱基序列相同字符的个数了
最后判断相差是否能控制在333以内就知道这个子串碱基能否被改成吃藕碱基了
卷积后的xmk−1x^{mk-1}xmk−1项才代表原碱基序列中[k,km−1][k,km-1][k,km−1]与吃藕碱基的匹配要转化一下
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 400100
struct complex {double x, i;complex(){}complex( double X, double I ) {x X, i I;}
}A[maxn], B[maxn];const double pi acos( -1.0 );complex operator ( complex a, complex b ) {return complex( a.x b.x, a.i b.i );
}complex operator - ( complex a, complex b ) {return complex( a.x - b.x, a.i - b.i );
}complex operator * ( complex a, complex b ) {return complex( a.x * b.x - a.i * b.i, a.x * b.i a.i * b.x );
}int len;
int r[maxn];void FFT( complex *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x v[j k], y v[j k i] * w;v[j k] x y;v[j k i] x - y;}}}
}int T;
char S0[maxn], S[maxn], ch[4] { A, G, T, C };
int tot[maxn];int main() {scanf( %d, T );while( T -- ) {scanf( %s %s, S0, S );memset( tot, 0, sizeof( tot ) );int n strlen( S0 ), m strlen( S );len 1; int l 0;while( len ( n m ) ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int j 0;j 4;j ) {for( int i 0;i n;i )A[i] complex( S0[i] ch[j], 0 );for( int i 0;i m;i )B[m - i - 1] complex( S[i] ch[j], 0 );FFT( A, 1 );FFT( B, 1 );for( int i 0;i len;i )A[i] A[i] * B[i];FFT( A, -1 );for( int i m - 1;i m n - 1;i ) tot[i - m 1] int( A[i].x / len 0.5 );for( int i 0;i len;i )A[i] B[i] complex( 0, 0 );}int ans 0;for( int i 0;i n - m 1;i ) //tot[i]:S0[i,im-1]和S[0,m-1]相同字符的个数 if( m - tot[i] 3 ) ans ;printf( %d\n, ans );}return 0;
}EP3321
[SDOI2015]序列统计
虽然以前做过一次但是肯定是迷迷糊糊的现在重新再做一遍代码就找以前的博客吧哈哈哈哈哈,ԾㅂԾ,
相乘目前来说是超越已有工具的考虑相乘转化为相加→\rightarrow→ 指数相加→\rightarrow→生成函数
但是好像没有哪个数学定理告诉我相乘转化为指数相加后取模答案不变的
卡在这里了(ˉ▽ˉ)…
再考虑设dpi,jdp_{i,j}dpi,j表示选了iii个数相乘的结果取模mmm等于jjj的方案数则有很简单的转移
f[i1][j×kmodm]∑k∈Sf[i][j]f[i1][j\times k\mod m]\sum_{k∈S}f[i][j]f[i1][j×kmodm]∑k∈Sf[i][j]
好像也转换不了形式使其长得像FFTFFTFFT啊凸(艹皿艹 ) 尽管做过但是还是没想出来啊/(ㄒoㄒ)/去看一下之前写的题解 b▽d 题目没说清楚mmm是个质数尽管说了我也不太想得到
指数的相加可以用mmm的原根来做底数
dpdpdp转移也稍有不同
f[ii][j]∑j1×j2%mjf[i][j1]×f[i][j2]f[ii][j]\sum_{j_1\times j_2\% mj}f[i][j_1]\times f[i][j_2]f[ii][j]∑j1×j2%mjf[i][j1]×f[i][j2]
但是大致想了75%75\%75%左右出来已经相比于之前完全0%0\%0%好多了 FP5641
【CSGRound2】开拓者的卓识、
(ρ)推半天推的是个什么玩意儿柿子噢 这个柿子从上往下推似乎推不出什么玩意儿推了有一会儿确实不会处理
考虑反过来从下往上推
令ansrsumk,1,rans_rsum_{k,1,r}ansrsumk,1,r考虑每个aia_iai的贡献假设aia_iai出现了cic_ici次
显然答案表示为ansr∑i1nai⋅cians_r\sum_{i1}^na_i·c_iansr∑i1nai⋅ci
cic_ici还有一种含义理解位置iii在[1,r][1,r][1,r]中被k−1k-1k−1重区间覆盖的方案数
减一是因为最大的区间已经是被确定为[1,r][1,r][1,r]
等价于选择k−1k-1k−1个区间[l1,r1],[l2,r2]...[lk−1,rk−1][l_1,r_1],[l_2,r_2]...[l_{k-1},r_{k-1}][l1,r1],[l2,r2]...[lk−1,rk−1]
使得1≤li,ri≤r,[li,ri]⊆[li1,ri1],i∈[li,ri]1\le l_i,r_i\le r,[l_i,r_i]\subseteq[l_{i1},r_{i1}],i∈[l_i,r_i]1≤li,ri≤r,[li,ri]⊆[li1,ri1],i∈[li,ri]的方案数 或者…༼ ∗ •̀ (oo) •́ ∗ ༽可以枚举理解
sum1,l,rsum_{1,l,r}sum1,l,r就是ala_lal到ara_rar的和
sum2,l,rsum_{2,l,r}sum2,l,r可以看作选择一个区间[l1,r1]⊆[l,r][l_1,r_1]\subseteq [l,r][l1,r1]⊆[l,r]然后把al1a_{l_1}al1到ar1a_{r_1}ar1的和再加到答案里面
sum3,l,rsum_{3,l,r}sum3,l,r选择一个区间[l2,r2]⊆[l1,r1][l_2,r_2]\subseteq [l_1,r_1][l2,r2]⊆[l1,r1]再对其做一遍sum2,l2,r2sum_{2,l_2,r_2}sum2,l2,r2相当于再选一个区间[l2,r2]⊆[l1,r1][l_2,r_2]\subseteq [l_1,r_1][l2,r2]⊆[l1,r1]将al2a_{l_2}al2到ar2a_{r_2}ar2的和再累计到答案中
………….
sumk,l,rsum_{k,l,r}sumk,l,r就是选择k−1k-1k−1个区间 继续等价于lil_ili在[1,i][1,i][1,i]中选rir_iri在[i,r][i,r][i,r]中选一共在[1,i][1,i][1,i]中选k−1k-1k−1个可重位置在[i,r][i,r][i,r]中选k−1k-1k−1个可重位置的方案数
令TnmT_{n}^mTnm表示在nnn个盒子中选择mmm个盒子的方案数
则cic_ici方案数即为Tik−1×Tr−i1k−1T_{i}^{k-1}\times T_{r-i1}^{k-1}Tik−1×Tr−i1k−1
TnmT_n^mTnm也是非常好求的就是数学中经典的隔板法
用m−1m-1m−1个板将盒子分成mmm份每份合并看作是最后的一个超级盒子那么一共就选择了mmm个超级盒子符合TTT的含义
所以就可以用组合数来计算此时就是不重位置的挑选了TnmCnm−1mT_n^mC_{nm-1}^mTnmCnm−1m
那么ciC(i)(k−1)−1k−1×C(r−i1)(k−1)−1k−1Cik−2k−1×Cr−ik−1k−1c_iC_{(i)(k-1)-1}^{k-1}\times C_{(r-i1)(k-1)-1}^{k-1}C_{ik-2}^{k-1}\times C_{r-ik-1}^{k-1}ciC(i)(k−1)−1k−1×C(r−i1)(k−1)−1k−1Cik−2k−1×Cr−ik−1k−1
ansr∑i1naiCik−2k−1×Cr−ik−1k−1ans_r\sum_{i1}^na_iC_{ik-2}^{k-1}\times C_{r-ik-1}^{k-1}ansr∑i1naiCik−2k−1×Cr−ik−1k−1
令giCik−1k−1,fiCik−2k−1g_iC_{ik-1}^{k-1},f_iC_{ik-2}^{k-1}giCik−1k−1,fiCik−2k−1
则ansr∑i1ngr−i∗fians_r\sum_{i1}^ng_{r-i}*f_iansr∑i1ngr−i∗fi
就可以卷积了有模数选择NTTNTTNTT
由于kkk非常的大预处理组合数显然不可做那就使用组合数的递推式即可
巧妙发现fiai×gi−1f_ia_i\times g_{i-1}fiai×gi−1fif_ifi也可递推获得
#include cstdio
#include iostream
using namespace std;
#define mod 998244353
#define int long long
#define maxn 400100
int n, k, len;
int a[maxn], r[maxn], f[maxn], g[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}void NTT( int *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( opt 1 ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ) );for( int j 0;j len;j ( i 1 ) )for( int k 0, w 1;k i;k , w w * omega % mod ) {int x v[j k], y v[j k i] * w % mod;v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod;}}if( opt -1 ) {int inv qkpow( len, mod - 2 );for( int i 0;i len;i )v[i] v[i] * inv % mod;}
}signed main() {scanf( %lld %lld, n, k );for( int i 1;i n;i )scanf( %lld, a[i] );g[0] 1, g[1] k % mod, f[1] a[1];for( int i 2;i n;i ) {g[i] g[i - 1] * ( i k - 1 ) % mod * qkpow( i, mod - 2 ) % mod;f[i] a[i] * g[i - 1] % mod;}len 1; int l 0;while( len ( n 1 ) ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );NTT( f, 1 );NTT( g, 1 );for( int i 0;i len;i )f[i] f[i] * g[i] % mod;NTT( f, -1 );for( int i 1;i n;i )printf( %lld , f[i] );return 0;
}GP4986
逃离
题意大概是这个亚子。走的范围是一个环红线代表C(x)∗tC(x)*tC(x)∗t绿线代表A(x)∗tA(x)*tA(x)∗t蓝线代表B(x)∗tB(x)*tB(x)∗t 非常小学鸡化容易操作将蓝绿线各自平移成一条线段然后与圆的半径构成直角三角形要从一个点一起出去则斜边就是$ hdxrie 的走法直角边就是的走法直角边就是的走法直角边就是 Althen $的走法 根据直角三角形法则有(A(x)∗t)2(B(x)∗t)2(C(x)∗t)2(A(x)*t)^2(B(x)*t)^2(C(x)*t)^2(A(x)∗t)2(B(x)∗t)2(C(x)∗t)2
化简得A2(x)B2(x)C2(x)A^2(x)B^2(x)C^2(x)A2(x)B2(x)C2(x)
定义一个新函数f(x)C2(x)−A2(x)−B2(x)f(x)C^2(x)-A^2(x)-B^2(x)f(x)C2(x)−A2(x)−B2(x)
最后的即是求函数f(x)f(x)f(x)的零点当然必须满足x∈[L,R]x∈[L,R]x∈[L,R]
而求一个函数的根近似解套用一阶牛顿迭代
xx0−f(x0)f′(x0)xx_0-\frac{f(x_0)}{f(x_0)}xx0−f′(x0)f(x0) 随便找一个点x0x_0x0然后做这个点的切线斜率就是对点x0x_0x0求导f’(x0)f’(x_0)f’(x0)
从这个切线的根与xxx轴的交点出发做一根垂线和曲线相交于xxx点
不停重复上述过程直到逼近原函数的零点附近
稍微解释一下牛顿迭代的公式
对于一条直线解析式ykxbykxbykxb那么关于x0x_0x0的切线即为f(x0)f′(x0)x0bf(x_0)f(x_0)x_0bf(x0)f′(x0)x0b
根据初中知识知道切线斜率还可以写成y−y0x−x0\frac{y-y_0}{x-x_0}x−x0y−y0那么用切线的零点和x0x_0x0重写切线解析式f′(x0)0−f(x0)x−x0⇒xx0−f(x0)f′(x0)f(x_0)\frac{0-f(x_0)}{x-x_0}\Rightarrow xx_0-\frac{f(x_0)}{f(x_0)}f′(x0)x−x00−f(x0)⇒xx0−f′(x0)f(x0) 最后就是设置一个牛顿迭代次数tititi暴算去逼近零点如果有的话
当然这过程中要和L,RL,RL,R比大小保证是答案是在范围内的
#include cmath
#include cstdio
#include iostream
using namespace std;
#define maxn 400100
#define eps 1e-10
struct complex {double x, i;complex(){}complex( double X, double I ) {x X, i I;}
}A[maxn];const double pi acos( -1.0 );complex operator ( complex a, complex b ) {return complex( a.x b.x, a.i b.i );
}complex operator - ( complex a, complex b ) {return complex( a.x - b.x, a.i - b.i );
}complex operator * ( complex a, complex b ) {return complex( a.x * b.x - a.i * b.i, a.x * b.i a.i * b.x );
}int len;
int r[maxn];void FFT( complex *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x v[j k], y v[j k i] * w;v[j k] x y, v[j k i] x - y;}}}
}int La, Lb, Lc, n;
double L, R;
int a[maxn], b[maxn], c[maxn], f[maxn], g[maxn];void work( int n, int *ans ) {len 1; int l 0;while( len ( n 1 ) ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int i 0;i len;i )A[i] complex( ans[i], 0 );FFT( A, 1 );for( int i 0;i len;i )A[i] A[i] * A[i];FFT( A, -1 );for( int i 0;i len;i )ans[i] int( A[i].x / len 0.5 );n len;
}double calc_f( double x ) {double ans 0, mi 1;for( int i 0;i n;i )ans f[i] * mi, mi * x;return ans;
}double calc_g( double x ) {double ans 0, mi 1;for( int i 0;i n;i )ans g[i] * mi, mi * x;return ans;
}int main() {scanf( %d %d %d %lf %lf, La, Lb, Lc, L, R );for( int i 0;i La;i )scanf( %d, a[i] );for( int i 0;i Lb;i )scanf( %d, b[i] );for( int i 0;i Lc;i )scanf( %d, c[i] );work( La, a );work( Lb, b );work( Lc, c );n max( La, max( Lb, Lc ) );for( int i 0;i n;i )f[i] c[i] - a[i] - b[i];for( int i 0;i n;i )g[i] f[i 1] * ( i 1 );int ti 50;double x ( L R ) / 2.0;while( ti ) {double tmp calc_f( x );if( fabs( tmp ) eps ) break;x x - tmp / calc_g( x );x max( x, L ), x min( x, R );ti --;}if( ti ) printf( %.8f\n, x );else printf( Inconsistent! );return 0;
}HP4721——获得知识药剂一瓶——分治FFTFFTFFT
【模板】分治 FFT
对于蒟蒻来说还是算一个新知识嘚学Y(_、)Y
分治FFT是一种基于CDQ分治的算法主要用于在O(nlog2n)O(nlog^2n)O(nlog2n)的时间复杂度计算已知g1g_1g1到gn−1g_{n-1}gn−1f01f_01f01求fi∑j1ifi−j⋅gjf_i\sum_{j1}^if_{i-j}·g_jfi∑j1ifi−j⋅gj
考虑分治l,r,mid⌊lr2⌋l,r,mid\lfloor\frac{lr}{2}\rfloorl,r,mid⌊2lr⌋计算左半段[l,mid][l,mid][l,mid]对于右半段[mid1,r][mid1,r][mid1,r]的贡献
设x∈[mid1,r]x∈[mid1,r]x∈[mid1,r]那么对fxf_xfx的贡献转移wxw_xwx即为wx∑ilmidfigx−iw_x\sum_{il}^{mid}f_ig_{x-i}wx∑ilmidfigx−i
不妨将推导范围扩大一点先保证fi0,i∈[mid1,r]f_i0,i∈[mid1,r]fi0,i∈[mid1,r]
wx∑ilx−1figx−i∑i0x−l−1fil⋅gx−l−iw_x\sum_{il}^{x-1}f_ig_{x-i}\sum_{i0}^{x-l-1}f_{il}·g_{x-l-i}wx∑ilx−1figx−i∑i0x−l−1fil⋅gx−l−i
令Aifil,Bigi1A_if_{il},B_ig_{i1}Aifil,Bigi1代回上式wx∑i0x−l−1AiBx−l−i−1w_x\sum_{i0}^{x-l-1}A_iB_{x-l-i-1}wx∑i0x−l−1AiBx−l−i−1
发现此时的A,BA,BA,B可以进行FFTFFTFFT卷积
每次操作的长度为r−l1r-l1r−l1总长度nlognnlognnlogn一共lognlognlogn层所以时间复杂度大概在O(nlog2n)O(nlog^2n)O(nlog2n) #include cstdio
#include iostream
using namespace std;
#define mod 998244353
#define int long long
#define maxn 400100
int r[maxn], f[maxn], g[maxn], A[maxn], B[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}void NTT( int *v, int opt, int len ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( opt 1 ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ) );for( int j 0;j len;j ( i 1 ) )for( int k 0, w 1;k i;k , w w * omega % mod ) {int x v[j k], y v[j k i] * w % mod;v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod;}}if( opt -1 ) {int inv qkpow( len, mod - 2 );for( int i 0;i len;i )v[i] v[i] * inv % mod;}
}void mul( int *A, int *B, int n, int l ) {for( int i 0;i n;i ) r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );NTT( A, 1, n );NTT( B, 1, n );for( int i 0;i n;i ) A[i] A[i] * B[i] % mod;NTT( A, -1, n );
}void CDQ( int L, int R ) {if( L R ) return;int mid ( L R ) 1;CDQ( L, mid );int len 1, l 0;while( len R - L 1 ) len 1, l ;for( int i L;i mid;i ) A[i - L] f[i];for( int i 1;i R - L;i ) B[i - 1] g[i];mul( A, B, len, l );for( int i mid 1;i R;i )f[i] ( f[i] A[i - L - 1] ) % mod;for( int i 0;i len;i ) A[i] B[i] 0;CDQ( mid 1, R );
}signed main() {int n;scanf( %lld, n );for( int i 1;i n;i )scanf( %lld, g[i] );f[0] 1;CDQ( 0, n - 1 );for( int i 0;i n;i )printf( %lld , f[i] );return 0;
}IP3338
[ZJOI2014]力
Fj∑i1j−1qi×qj(i−j)2−∑ij1nqi×qj(i−j)2,EjFjqj⇒Ej∑i1j−1qi(i−j)2−∑ij1nqi(i−j)2F_j\sum_{i1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{ij1}^n\frac{q_i\times q_j}{(i-j)^2},E_j\frac{F_j}{q_j}\Rightarrow E_j\sum_{i1}^{j-1}\frac{q_i}{(i-j)^2}-\sum_{ij1}^n\frac{q_i}{(i-j)^2}Fji1∑j−1(i−j)2qi×qj−ij1∑n(i−j)2qi×qj,EjqjFj⇒Eji1∑j−1(i−j)2qi−ij1∑n(i−j)2qi
把ijijij加进去其实是不影响的代码又不会真的去除我们只一心想要卷积
∑i1jqi(i−j)2−∑ijnqi(i−j)2\sum_{i1}^{j}\frac{q_i}{(i-j)^2}-\sum_{ij}^n\frac{q_i}{(i-j)^2}∑i1j(i−j)2qi−∑ijn(i−j)2qi
设fiqi,gi1i2f_iq_i,g_i\frac{1}{i^2}fiqi,gii21
∑i1jfigj−i−∑ijnfigi−j\sum_{i1}^jf_ig_{j-i}-\sum_{ij}^nf_ig_{i-j}∑i1jfigj−i−∑ijnfigi−j
令f0g00f_0g_00f0g00
∑i0jfi∗gj−i−∑ijnfigi−j\sum_{i0}^jf_i*g_{j-i}-\sum_{ij}^nf_ig_{i-j}∑i0jfi∗gj−i−∑ijnfigi−j
左边已经是一个卷积的形式了接下来只考虑右边即可
一般卷积形式都会把求和符号的下标换成从000开始
并且用两个数组的下标去凑成一个求和上限的恒定值
∑ijnfigi−j∑i0n−jfijgi\sum_{ij}^nf_ig_{i-j}\sum_{i0}^{n-j}f_{ij}g_{i}∑ijnfigi−j∑i0n−jfijgi
设hifn−ih_if_{n-i}hifn−i
∑i0n−jhn−i−j∗gi\sum_{i0}^{n-j}h_{n-i-j}*g_i∑i0n−jhn−i−j∗gi
两边都变成了完美的卷积形式(๑′ᴗ‵๑)
∑i0jf[i]∗g[j−i]−∑i0n−jh[n−i−j]∗g[i]\sum_{i0}^jf[i]*g[j-i]-\sum_{i0}^{n-j}h[n-i-j]*g[i]∑i0jf[i]∗g[j−i]−∑i0n−jh[n−i−j]∗g[i]
设多项式F(x)∑i0nfi,G(x)∑i0ngi,H(x)∑i0nhiF(x)\sum_{i0}^nf_i,G(x)\sum_{i0}^ng_i,H(x)\sum_{i0}^nh_iF(x)∑i0nfi,G(x)∑i0ngi,H(x)∑i0nhi
令L(x)F(x)∗G(x),R(x)G(x)∗H(x)L(x)F(x)*G(x),R(x)G(x)*H(x)L(x)F(x)∗G(x),R(x)G(x)∗H(x)
则ansili−rn−ians_il_i-r_{n-i}ansili−rn−ili,rn−il_i,r_{n-i}li,rn−i分别表示多项式对应项的系数
#include cmath
#include cstdio
#include iostream
using namespace std;
#define maxn 400100
struct complex {double x, i;complex(){}complex( double X, double I ) {x X, i I;}
}F[maxn], G[maxn], H[maxn];const double pi acos( -1.0 );complex operator ( complex a, complex b ) {return complex( a.x b.x, a.i b.i );
}complex operator - ( complex a, complex b ) {return complex( a.x - b.x, a.i - b.i );
}complex operator * ( complex a, complex b ) {return complex( a.x * b.x - a.i * b.i, a.x * b.i a.i * b.x );
}int len;
int r[maxn];void FFT( complex *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x v[j k], y v[j k i] * w;v[j k] x y;v[j k i] x - y;}}}
}int n;
int main() {scanf( %d, n );for( int i 1;i n;i ) {scanf( %lf, F[i].x ), F[i].i 0;H[n - i] F[i];G[i] complex( 1.0 / i / i, 0 );}len 1; int l 0;while( len ( n 1 ) ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );FFT( F, 1 );FFT( G, 1 );FFT( H, 1 );for( int i 0;i len;i ) F[i] F[i] * G[i], H[i] H[i] * G[i];FFT( F, -1 );FFT( H, -1 );for( int i 1;i n;i )printf( %.3f\n, F[i].x / len - H[n - i].x / len );return 0;
}JP4173
残缺的字符串
读完题迅速反应类似的本系列的D题DNA
考虑分成262626个字母独立考虑包括∗*∗所在位置一直为111即可
将当前枚举的字母所在位置赋为111其余为000
对于B[k,km−1]B[k,km-1]B[k,km−1]和A[0,m−1]A[0,m-1]A[0,m−1]的相同的字符长度个数表示为∑i0m−1B[ki]A[i]\sum_{i0}^{m-1}B[ki]A[i]∑i0m−1B[ki]A[i]
令Tm−i−1AiT_{m-i-1}A_{i}Tm−i−1Ai
∑i0m−1Bki∗Tm−i−1\sum_{i0}^{m-1}B_{ki}*T_{m-i-1}∑i0m−1Bki∗Tm−i−1
同样的卷积
∑ijm−k−1Bi∗Tj\sum_{ijm-k-1}B_i*T_{j}∑ijm−k−1Bi∗Tj
最后toti[m−i−1]B∗Ttot_i[m-i-1]B*Ttoti[m−i−1]B∗T将272727个相同字符个数加起来判断是否长度达到mmm即可
麻溜敲完很不幸——303030剩下全是TLETLETLE╮(╯-╰)╭好吧…
你以为是再次中场休息还是太年轻了骚年又是一个新的好算法呢 ——luoguluoguluogu第一篇题解真的很良心٩(๑н´๑)۶
普通的单模式串匹配
长度为mmm的模式串AAA长度为nnn的文本串BBB求所有位置满足BBB串从第xxx个字符开始的连续mmm个字符与AAA完全相同
Step1定义匹配函数
定义字符串的匹配函数为C(x,y)A(x)−B(y)C(x,y)A(x)-B(y)C(x,y)A(x)−B(y)
在这里形式化的定义“匹配”若C(x,y)0C(x,y)0C(x,y)0则AAA的第xxx个字符与BBB的第yyy个字符相匹配
Step2定义完全匹配函数
定义D(x)∑i0m−1C(i,x−mi1)D(x)\sum_{i0}^{m-1}C(i,x-mi1)D(x)∑i0m−1C(i,x−mi1)若D(x)0D(x)0D(x)0则AAA与BBB以xxx结尾的连续mmm个字符完全匹配
但到这里发现因为带了求和符号所以只要两串所含字符一样势必会有D(x)0D(x)0D(x)0
这就与我们的初衷背道而驰了而导致这种情况发生的原因——C(x,y)C(x,y)C(x,y)自带±±±符号
考虑如何去掉这个符号的影响使得只要两个串的某一位置不匹配完全匹配函数就一定不为000
非常初中数学老师教的——加绝对值但是在解不等式的时候老师教过绝对值也不好弄处理成——平方
此时有D(x)∑i0m−1C(i,x−mi1)2∑i0m−1(A(i)−B(x−mi1))2D(x)\sum_{i0}^{m-1}C(i,x-mi1)^2\sum_{i0}^{m-1}\bigg(A(i)-B(x-mi1)\bigg)^2D(x)∑i0m−1C(i,x−mi1)2∑i0m−1(A(i)−B(x−mi1))2
Step3:Step3:Step3:暴力整式子观察结构不谋手段の优化
先展开看看
D(x)∑i0m−1(A2(i)−2A(i)B(x−mi1)B2(x−mi1))D(x)\sum_{i0}^{m-1}\bigg(A^2(i)-2A(i)B(x-mi1)B^2(x-mi1)\bigg)D(x)∑i0m−1(A2(i)−2A(i)B(x−mi1)B2(x−mi1))
很套路的尝试反转AAA串定义A′(i)A(m−i−1)A(i)A(m-i-1)A′(i)A(m−i−1)
D(x)∑i0m−1(A′2(m−i−1)−2A′(m−i−1)B(x−mi1)B2(x−mi1))D(x)\sum_{i0}^{m-1}\bigg(A^2(m-i-1)-2A(m-i-1)B(x-mi1)B^2(x-mi1)\bigg)D(x)∑i0m−1(A′2(m−i−1)−2A′(m−i−1)B(x−mi1)B2(x−mi1))
一般只想求和符号里面放一个东西求和里面的加减乘除考虑各自拆开
D(x)∑i0m−1A′(m−i−1)2∑i0m−1B(x−mi1)2−2∑i0m−1A′(m−i−1)B(x−mi1)D(x)\sum_{i0}^{m-1}A(m-i-1)^2\sum_{i0}^{m-1}B(x-mi1)^2-2\sum_{i0}^{m-1}A(m-i-1)B(x-mi1)D(x)∑i0m−1A′(m−i−1)2∑i0m−1B(x−mi1)2−2∑i0m−1A′(m−i−1)B(x−mi1)
第一项可以O(m)O(m)O(m)预处理与BBB无瓜sovledsovledsovled
第二项可以O(n)O(n)O(n)预处理前缀和solvedsolvedsolved
第三项看到ta应该是满心欢喜的๑乛◡乛๑卷积小宝贝改写成2∑ijxA′(i)∗B(j)2\sum_{ijx}A(i)*B(j)2∑ijxA′(i)∗B(j)
最后整理一下设T∑i0m−1A′(i)2,pre(x)∑i0xB(i)2,g(x)∑ijxA′(i)∗B(j)T\sum_{i0}^{m-1}A(i)^2,pre(x)\sum_{i0}^{x}B(i)^2,g(x)\sum_{ijx}A(i)*B(j)T∑i0m−1A′(i)2,pre(x)∑i0xB(i)2,g(x)∑ijxA′(i)∗B(j)
进而有D(x)Tpre(x)−pre(x−m)−2g(x)D(x)Tpre(x)-pre(x-m)-2g(x)D(x)Tpre(x)−pre(x−m)−2g(x)
FFTFFTFFT优化算g(x)g(x)g(x)最后O(n)O(n)O(n)算D(x)D(x)D(x)
通配符的单模式串匹配
考虑依葫芦画瓢一样的步骤
Step1定义匹配函数
设通配符的数值为000000乘任何数为000既然想把与通配符的匹配算出来的C(x,y)C(x,y)C(x,y)也变成000不放把数值乘进去
C(x,y)(A(x)−B(y))2⋅A(x)⋅B(y)C(x,y)\big(A(x)-B(y)\big)^2·A(x)·B(y)C(x,y)(A(x)−B(y))2⋅A(x)⋅B(y)
Step2完全匹配函数
D(x)∑i0m−1(A(i)−B(x−mi1))2⋅A(i)⋅B(x−mi1)D(x)\sum_{i0}^{m-1}\big(A(i)-B(x-mi1)\big)^2·A(i)·B(x-mi1)D(x)∑i0m−1(A(i)−B(x−mi1))2⋅A(i)⋅B(x−mi1)
Step3暴力化式子
D(x)∑i0m−1A(i)3B(x−mi1)∑i0m−1B(x−mi1)3A(i)−2∑i0m−1A(i)2B(x−mi1)2D(x)\sum_{i0}^{m-1}A(i)^3B(x-mi1)\sum_{i0}^{m-1}B(x-mi1)^3A(i)-2\sum_{i0}^{m-1}A(i)^2B(x-mi1)^2D(x)∑i0m−1A(i)3B(x−mi1)∑i0m−1B(x−mi1)3A(i)−2∑i0m−1A(i)2B(x−mi1)2
定义A′(i)A(m−i−1)A(i)A(m-i-1)A′(i)A(m−i−1)
D(x)∑i0m−1A′(m−i−1)3B(x−mi1)∑i0m−1B(x−mi1)3A′(m−i−1)−2∑i0m−1A′(x−m−1)2B(x−mi1)2D(x)\sum_{i0}^{m-1}A(m-i-1)^3B(x-mi1)\sum_{i0}^{m-1}B(x-mi1)^3A(m-i-1)-2\sum_{i0}^{m-1}A(x-m-1)^2B(x-mi1)^2D(x)∑i0m−1A′(m−i−1)3B(x−mi1)∑i0m−1B(x−mi1)3A′(m−i−1)−2∑i0m−1A′(x−m−1)2B(x−mi1)2
更妙的地方出现了发现所有小括号加起来都是xxx卷积宝贝作法了ԅ(¯㉨¯ԅ)
D(x)∑ijxA′(i)3B(j)∑ijxB(j)3A′(i)−2∑ijxA′(i)2B(j)2D(x)\sum_{ijx}A(i)^3B(j)\sum_{ijx}B(j)^3A(i)-2\sum_{ijx}A(i)^2B(j)^2D(x)∑ijxA′(i)3B(j)∑ijxB(j)3A′(i)−2∑ijxA′(i)2B(j)2
三次多项式乘法即可〜㉨)〜(▽)
常数稍稍大了点但这不重要吸氧能过的都不叫卡常p(#▽#)o
#include cmath
#include cstdio
#include iostream
#include algorithm
using namespace std;
#define maxn 1200100
struct complex {double x, i;complex(){}complex( double X, double I ) {x X, i I;}
}a[maxn], b[maxn], D[maxn];const double pi acos( -1.0 );complex operator ( complex a, complex b ) {return complex( a.x b.x, a.i b.i );
}complex operator - ( complex a, complex b ) {return complex( a.x - b.x, a.i - b.i );
}complex operator * ( complex a, complex b ) {return complex( a.x * b.x - a.i * b.i, a.x * b.i a.i * b.x );
}int len;
int r[maxn];void FFT( complex *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x v[j k], y v[j k i] * w;v[j k] x y;v[j k i] x - y;}}}
}int m, n, cnt;
char s1[maxn], s2[maxn];
int ans[maxn], A[maxn], B[maxn];int main() {scanf( %d %d %s %s, m, n, s1, s2 );len 1; int l 0;while( len m n ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int i 0;i m;i ) A[i] ( s1[i] * ) ? 0 : s1[i] - a 1;for( int i 0;i n;i )B[i] ( s2[i] * ) ? 0 : s2[i] - a 1;reverse( A, A m );for( int i 0;i len;i ) {a[i] complex( A[i] * A[i] * A[i], 0 );b[i] complex( B[i], 0 );}FFT( a, 1 ), FFT( b, 1 );for( int i 0;i len;i )D[i] D[i] a[i] * b[i];for( int i 0;i len;i ) {a[i] complex( A[i], 0 );b[i] complex( B[i] * B[i] * B[i], 0 );}FFT( a, 1 ), FFT( b, 1 );for( int i 0;i len;i )D[i] D[i] a[i] * b[i];for( int i 0;i len;i ) {a[i] complex( A[i] * A[i], 0 );b[i] complex( B[i] * B[i], 0 );}FFT( a, 1 ), FFT( b, 1 );for( int i 0;i len;i )D[i] D[i] - a[i] * b[i] * complex( 2, 0 );FFT( D, -1 );for( int i m - 1;i n;i )if( fabs( D[i].x / len ) 0.5 ) ans[ cnt] i - m 2;//本来D[i]算的是i-m1 但此题要求下标从1开始 所以要多加1printf( %d\n, cnt );for( int i 1;i cnt;i )printf( %d , ans[i] );return 0;
}KP5748
集合划分计数
题意求n≤1e5n\le 1e5n≤1e5的贝尔数bell(n)bell(n)bell(n)即将nnn个有标号的球划分若干集合的方案数
设fi,jf_{i,j}fi,j表示把iii个数划分为jjj个集合的方案数
那么就有两种转移要么iii自成一个集合要么加入jjj个当中的任意一个集合
fi,jfi−1,j−1fi−1,j×jf_{i,j}f_{i-1,j-1}f_{i-1,j}\times jfi,jfi−1,j−1fi−1,j×j
ans∑i1nfn,ians\sum_{i1}^nf_{n,i}ans∑i1nfn,i
O(n2)O(n^2)O(n2)简单的暴力DPDPDP转移
设fif_ifi表示把nnn个数划分为iii个集合的方案数
(╯▽╰ ) 卡住了——(△) 法一生成函数
指数型生成函数用来解决排列问题普通型生成函数用来解决组合问题
设一个非空集合的指数型生成函数F(x)F(x)F(x)答案的指数型生成函数为G(x)G(x)G(x)
枚举划分的集合集合间不区分有G(x)∑i0∞Fi(x)i!eF(x)G(x)\sum_{i0}^∞\frac{F^i(x)}{i!}e^{F(x)}G(x)∑i0∞i!Fi(x)eF(x)
一个非空集合的指数型生成函数显然为ex−1e^x-1ex−1∑i0∞xii!\sum_{i0}^∞\frac{x^i}{i!}∑i0∞i!xi减去一个空集f01f_01f01
多项式expexpexp即可题目求的是有标号的方案数最后乘以n!n!n!即可
法二分治FFTFFTFFT
枚举第一个元素所在集合大小列出状态转移方程
fi∑j1iCi−1,j−1×fi−j∑j1i(i−1)!(j−1)!(i−j)!×fi−jf_i\sum_{j1}^iC_{i-1,j-1}\times f_{i-j}\sum_{j1}^i\frac{(i-1)!}{(j-1)!(i-j)!}\times f_{i-j}fi∑j1iCi−1,j−1×fi−j∑j1i(j−1)!(i−j)!(i−1)!×fi−j
把带i,ji,ji,j的项分开
fi(i−1)!∑j1i1(j−1)!×fi−j(i−j)!\frac{f_i}{(i-1)!}\sum_{j1}^i\frac{1}{(j-1)!}\times \frac{f_{i-j}}{(i-j)!}(i−1)!fi∑j1i(j−1)!1×(i−j)!fi−j
令Fi1i!,Gifii!F_i\frac{1}{i!},G_i\frac{f_i}{i!}Fii!1,Gii!fi卷积
fi(i−1)!∑j0i−1Fj∗Gi−j−1∑jki−1Fj∗Gk\frac{f_i}{(i-1)!}\sum_{j0}^{i-1}F_{j}*G_{i-j-1}\sum_{jki-1}F_j*G_k(i−1)!fi∑j0i−1Fj∗Gi−j−1∑jki−1Fj∗Gk
FFF是已知多项式预处理即可GGG是一个只与fj,jif_j,jifj,ji有关的多项式最后答案别忘记乘(i−1)!(i-1)!(i−1)!
这不是左边对右边造成贡献的好套路吗——中场休息的分治FFTFFTFFT登场
#include cstdio
#include iostream
using namespace std;
#define int long long
#define mod 998244353
#define maxn 400100
#define n 100000
int r[maxn], fac[maxn], inv[maxn], f[maxn], g[maxn], A[maxn], B[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}void NTT( int *v, int opt, int len ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( opt 1 ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ) );for( int j 0;j len;j ( i 1 ) )for( int k 0, w 1;k i;k , w w * omega % mod ) {int x v[j k], y v[j k i] * w % mod;v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod; }}if( opt -1 ) {int Inv qkpow( len, mod - 2 );for( int i 0;i len;i )v[i] v[i] * Inv % mod;}
}void init() {fac[0] inv[0] 1;for( int i 1;i n;i ) fac[i] fac[i - 1] * i % mod;inv[n] qkpow( fac[n], mod - 2 );for( int i n - 1;i;i -- ) inv[i] inv[i 1] * ( i 1 ) % mod;
}void CDQ( int L, int R ) {if( L R ) { if( L ) f[L] f[L] * fac[L - 1] % mod; return; }int mid ( L R ) 1;CDQ( L, mid );int len 1, l 0;while( len R - L 1 ) len 1, l ;for( int i 0;i len;i ) r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int i L;i mid;i ) A[i - L] f[i] * inv[i] % mod;for( int i 0;i len;i ) B[i] inv[i];NTT( A, 1, len );NTT( B, 1, len );for( int i 0;i len;i ) A[i] A[i] * B[i] % mod;NTT( A, -1, len );for( int i mid 1;i R;i ) f[i] ( f[i] A[i - 1 - L] ) % mod;for( int i 0;i len;i ) A[i] B[i] 0;CDQ( mid 1, R );
}signed main() {init();f[0] 1;CDQ( 0, n );int T;scanf( %lld, T );while( T -- ) {int x;scanf( %lld, x );printf( %lld\n, f[x] );}return 0;
}LP3702
[SDOI2017]序列计数
至少有一个为质数(;¬_¬)俺讨厌至少。。。
转化为满足要求的序列总数减去一个质数都没有的满足要求的序列数
一个质数都没有的序列数不妨把mmm以内的所有质数全都丢掉
设fi,jf_{i,j}fi,j前iii个数的总和取模ppp为jjj的方案数一个质数都没有枚举第iii个选的数
fi,j∑(j1j2)%pjfi−1,j2f_{i,j}\sum_{(j_1j_2)\%pj}f_{i-1,j_2}fi,j∑(j1j2)%pjfi−1,j2j1j_1j1为合数
下面带取模好熟悉EEE题的序列统计⊙﹏⊙!修改转移方程
fi1,j∑(j1j2)%pjfi,j1∗fi,j2f_{i1,j}\sum_{(j_1j_2)\%pj}f_{i,j_1}*f_{i,j_2}fi1,j∑(j1j2)%pjfi,j1∗fi,j2
突然想起ppp好像没保证是质数。。。淦((٩(//̀Д/́/)۶))没有原根指数上的取模就不能进行了
不٩(๑н´๑)۶我是sb这比序列统计还要简单下面的条件是加又不是乘干嘛甩成指数做多此一举
已经是个卷积形式了。。。难道三模数NTTNTTNTT害怕码力{嘎嘎嘎~ 有矩阵快速幂容斥的容斥实在对于现在的我要求太高了
暴力卷积快速幂就可以跑过去(•̀⌄•́乁这算不算搞出这道题了p(#▽#)o
#include cstdio
#define int long long
#define mod 20170408
#define maxn 20000005
#define maxp 400
int n, m, p, cnt;
int f[maxp], g[maxp], c[maxp], F[maxp], G[maxp], prime[maxn];
bool vis[maxn];void mul( int *a, int *b ) {for( int i 0;i p;i )for( int j 0;j p;j )c[i j] ( c[i j] a[i] * b[j] % mod ) % mod;for( int i 0;i p;i )a[i] ( c[i] c[i p] ) % mod, c[i] c[i p] 0;
}signed main() {scanf( %lld %lld %lld, n, m, p );f[1] g[1] F[0] G[0] 1;for( int i 2;i m;i ) {f[i % p] ;if( ! vis[i] ) prime[ cnt] i;else g[i % p] ;for( int j 1;j cnt i * prime[j] m;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) break;}}while( n ) {if( n 1 ) mul( F, f ), mul( G, g );mul( f, f ), mul( g, g );n 1;}printf( %lld\n, ( F[0] - G[0] mod ) % mod );return 0;
}这题的难度放错位置了就当中场休息好了
MP5667
拉格朗日插值2 套拉格朗日差值公式fmx∑i0nf(i)∏i≠jmx−ji−jf_{mx}\sum_{i0}^nf(i)\prod_{i≠j}\frac{mx-j}{i-j}fmx∑i0nf(i)∏iji−jmx−j
∏i≠jmx−j→(mx)(mx−1)...(mx−n)/(mx−i)(mx)!(mx−n−1)!(mx−i)\prod_{i≠j}mx-j\rightarrow (mx)(mx-1)...(mx-n)/(mx-i)\frac{(mx)!}{(mx-n-1)!(mx-i)}∏ijmx−j→(mx)(mx−1)...(mx−n)/(mx−i)(mx−n−1)!(mx−i)(mx)!
对于枚举的iii有[0,i)[0,i)[0,i)小于iii相减为正而对于(i,n](i,n](i,n]的共n−in-in−i个数而言分母为负
所以乘积的符号便由n−in-in−i的奇偶决定(−1)n−i(-1)^{n-i}(−1)n−i
∏jii−j(i−0)(i−1)(i−2)...(2)(1)i!\prod_{ji}i-j(i-0)(i-1)(i-2)...(2)(1)i!∏jii−j(i−0)(i−1)(i−2)...(2)(1)i!
∏iji−j(n−i)(n−i1)...(2)(1)(n−i)!\prod_{ij}i-j(n-i)(n-i1)...(2)(1)(n-i)!∏iji−j(n−i)(n−i1)...(2)(1)(n−i)!不考虑正负上面已经判断了
⇒fmx∑i0n(f(i)×(mx)!(−1)n−ii!(n−i)!(mx−n−1)!(mx−i))\Rightarrow f_{mx}\sum_{i0}^n\bigg(f(i)\times \frac{(mx)!}{(-1)^{n-i}i!(n-i)!(mx-n-1)!(mx-i)}\bigg)⇒fmx∑i0n(f(i)×(−1)n−ii!(n−i)!(mx−n−1)!(mx−i)(mx)!)
把只与xxx有关的式子提出来(−1)n−i(-1)^{n-i}(−1)n−i只带来符号改变不妨放在分子上分母太肥了(;¬_¬)
⇒fmx(mx)!(mx−n−1)!×∑i0n((−1)n−if(i)i!(n−i)!∗1mx−i)\Rightarrow f_{mx}\frac{(mx)!}{(mx-n-1)!}\times \sum_{i0}^n\bigg(\frac{(-1)^{n-i}f(i)}{i!(n-i)!}*\frac{1}{mx-i}\bigg)⇒fmx(mx−n−1)!(mx)!×∑i0n(i!(n−i)!(−1)n−if(i)∗mx−i1)
发现是个卷积形式但是iii的取值不是0≤i≤x0\le i\le x0≤i≤x而达到了nnn与一般的有所区别(・。・)
但是没关系啊ԅ(¯㉨¯ԅ)我们卷积最喜欢的不就是重新定义新函数改变原多项式顺序吗只要最后能很快速地反映所求答案位置
老子把整个序列硬往后挪nnn位第xnxnxn位计算的答案存的就是原来fmxf_{mx}fmx
令Ai(−1)n−if(i)i!(n−i)!,Bi1m−niA_i\frac{(-1)^{n-i}f(i)}{i!(n-i)!},B_i\frac{1}{m-ni}Aii!(n−i)!(−1)n−if(i),Bim−ni1
fxm(xm)!(mx−n−1)!∑i0nAi∗Bnx−i(xm)!(mx−n−1)!∑jknxAj∗Bkf_{xm}\frac{(xm)!}{(mx-n-1)!}\sum_{i0}^nA_i*B_{nx-i}\frac{(xm)!}{(mx-n-1)!}\sum_{jknx}A_j*B_kfxm(mx−n−1)!(xm)!∑i0nAi∗Bnx−i(mx−n−1)!(xm)!∑jknxAj∗Bk
令ixnixnixnx∈[0,n]⇒i∈[n,2n]x∈[0,n]\Rightarrow i∈[n,2n]x∈[0,n]⇒i∈[n,2n]
(im−n)!(im−n−n−1)!∑jkiAj∗Bk\frac{(im-n)!}{(im-n-n-1)!}\sum_{jki}A_j*B_k(im−n−n−1)!(im−n)!∑jkiAj∗Bk
预处理阶乘facii!fac_ii!facii!iii逆元inviinv_iinvii!i!i!阶乘逆元invfaciinvfac_iinvfaci差位的阶乘MS_faci∏j0i−1(m−nj)MS\_fac_i\prod_{j0}^{i-1}(m-nj)MS_faci∏j0i−1(m−nj)m−nim-nim−ni差位逆元MS_invi1MS\_inv_{i1}MS_invi1MS_faciMS\_fac_iMS_faci差位阶乘逆元MS_facinviMS\_facinv_iMS_facinvi则有1(im−n)!MS_faci1,(im−n−1−n)!MS_facinvi−n\frac{1}{(im-n)!}MS\_fac_{i1},(im-n-1-n)!MS\_facinv_{i-n}(im−n)!1MS_faci1,(im−n−1−n)!MS_facinvi−n
最后bb这么多是为了解释代码的一些地方避免不必要的时间投入看代码FFT就是这种玩下标的东西经常容易玩懵找准哪个位置是自己原来求解数组的对应位置是关键
#include cstdio
#include iostream
using namespace std;
#define int long long
#define mod 998244353
#define maxn 1000000
int n, m, len;
int f[maxn], r[maxn], A[maxn], B[maxn];
int inv[maxn], facinv[maxn], fac[maxn];
int MS_fac[maxn], MS_inv[maxn], MS_facinv[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}void NTT( int *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( opt 1 ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ) );for( int j 0;j len;j ( i 1 ) )for( int k 0, w 1;k i;k , w w * omega % mod ) {int x v[j k], y v[j k i] * w % mod;v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod;}}if( opt -1 ) {int Inv qkpow( len, mod - 2 );for( int i 0;i len;i )v[i] v[i] * Inv % mod;}
}void init( int n, int m ) {fac[0] MS_fac[0] MS_inv[0] inv[0] 1;for( int i 1;i ( n 1 | 1 );i ) {fac[i] fac[i - 1] * i % mod;MS_fac[i] MS_fac[i - 1] * ( m - n i - 1 ) % mod;}facinv[n 1 | 1] qkpow( fac[n 1 | 1], mod - 2 );MS_facinv[n 1 | 1] qkpow( MS_fac[n 1 | 1], mod - 2 );for( int i ( n 1 );~ i;i -- ) {facinv[i] facinv[i 1] * ( i 1 ) % mod;MS_facinv[i] MS_facinv[i 1] * ( m - n i ) % mod;}for( int i ( n 1 | 1 );i;i -- ) {inv[i] facinv[i] * fac[i - 1] % mod;MS_inv[i] MS_facinv[i] * MS_fac[i - 1] % mod;}
}signed main() {scanf( %lld %lld, n, m );init( n, m );for( int i 0;i n;i )scanf( %lld, f[i] );len 1; int l 0;while( len n * 3 ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int i 0;i n;i ) {A[i] f[i] * facinv[i] % mod * facinv[n - i] % mod;if( ( n - i ) 1 ) A[i] mod - A[i];}for( int i 0;i ( n 1 );i )B[i] MS_inv[i 1];NTT( A, 1 ), NTT( B, 1 );for( int i 0;i len;i )A[i] A[i] * B[i] % mod;NTT( A, -1 );for( int i n;i ( n 1 );i )printf( %lld , MS_fac[i 1] * MS_facinv[i - n] % mod * A[i] % mod );return 0;
}NP4245——拾得知识药丸一颗——三模数NTTNTTNTT
【模板】任意模数多项式乘法
别称三模数NTTNTTNTT 嘿嘿嘿——才发现这种三模数NTTNTTNTT就是MTTMTTMTT那没事了V●ᴥ●V
当然这题有很多好的解法但是鄙人认为还是应该掌握基础的不要脑子的sb基础做法
{x≡x1(modM1)x≡x2(modM2)x≡x3(modM3)\begin{cases}x\equiv x_1\ \ (mod\ \ M_1)\\x\equiv x_2\ \ (mod\ \ M_2)\\x\equiv x_3\ \ (mod\ \ M_3)\end{cases}⎩⎪⎨⎪⎧x≡x1 (mod M1)x≡x2 (mod M2)x≡x3 (mod M3)
xx1k1M1x2k2M2⇒x1k1M1≡x2(modM2)⇒k1x2−x1M1(modM2)xx_1k_1M_1x_2k_2M_2\Rightarrow x_1k_1M_1\equiv x_2\pmod {M_2}\Rightarrow k_1\frac{x_2-x_1}{M_1}\pmod {M_2}xx1k1M1x2k2M2⇒x1k1M1≡x2(modM2)⇒k1M1x2−x1(modM2)
x≡x1k1M1(modM1M2)x\equiv x_1k_1M_1\pmod {M_1M_2}x≡x1k1M1(modM1M2)令tx1k1M1tx_1k_1M_1tx1k1M1
tk′M1M2x3k3M3⇒tk′M1M2≡x3(modM3)⇒k′x3−tM1M2(modM3)tkM_1M_2x_3k_3M_3\Rightarrow tkM_1M_2\equiv x_3\pmod{M_3}\Rightarrow k\frac{x_3-t}{M_1M_2}\pmod{M_3}tk′M1M2x3k3M3⇒tk′M1M2≡x3(modM3)⇒k′M1M2x3−t(modM3)
∵xM1M2M3⇒xk′M1M2t∵xM_1M_2M_3\Rightarrow xkM_1M_2t∵xM1M2M3⇒xk′M1M2t
中国剩余定理及扩展剩余定理证明
#include cstdio
#include iostream
using namespace std;
#define int long long
#define maxn 400100
int len, n, m, p;
int r[maxn], ans[maxn], B[maxn], F[maxn], G[maxn];
int Mod[5] { 0, 998244353, 469762049, 1004535809 };int qkpow( int x, int y, int mod ) {x % mod;int ret 1;while( y ) {if( y 1 ) ret ret * x % mod;x x * x % mod;y 1;}return ret;
}struct poly {int A[maxn], mod;void NTT( int *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( opt 1 ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ), mod );for( int j 0;j len;j ( i 1 ) )for( int k 0, w 1;k i;k , w w * omega % mod ) {int x v[j k], y v[j k i] * w % mod;v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod;}}if( opt -1 ) {int inv qkpow( len, mod - 2, mod );for( int i 0;i len;i )v[i] v[i] * inv % mod;}}
}ntt[5];int qkmul( int x, int y, int mod ) {x % mod;int ret 0;while( y ) {if( y 1 ) ret ( ret x ) % mod;x ( x x ) % mod;y 1;}return ret;
}void CRT() {int mod_12 Mod[1] * Mod[2];int inv1 qkpow( Mod[1], Mod[2] - 2, Mod[2] );int inv2 qkpow( Mod[2], Mod[1] - 2, Mod[1] );int inv_12 qkpow( mod_12, Mod[3] - 2, Mod[3] );for( int i 0;i len;i ) {int x1 ntt[1].A[i];int x2 ntt[2].A[i];int x3 ntt[3].A[i];int t ( qkmul( x1 * Mod[2], inv2, mod_12 ) qkmul( x2 * Mod[1], inv1, mod_12 ) ) % mod_12;int k ( x3 - t % Mod[3] Mod[3] ) % Mod[3] * inv_12 % Mod[3];ans[i] ( k % p * ( mod_12 % p ) % p t % p ) % p;}
}signed main() {scanf( %lld %lld %lld, n, m, p );for( int i 0;i n;i ) scanf( %lld, F[i] );for( int i 0;i m;i ) scanf( %lld, G[i] );len 1;int l 0;while( len n m ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int k 1;k 3;k ) {ntt[k].mod Mod[k];for( int i 0;i n;i ) ntt[k].A[i] F[i];for( int i 0;i m;i ) B[i] G[i];for( int i m 1;i len;i ) B[i] 0;ntt[k].NTT( ntt[k].A, 1 );ntt[k].NTT( B, 1 );for( int i 0;i len;i ) ntt[k].A[i] ntt[k].A[i] * B[i] % Mod[k];ntt[k].NTT( ntt[k].A, -1 );}CRT();for( int i 0;i n m;i )printf( %lld , ans[i] );return 0;
}OP5488
差分与前缀和 一.前缀和
si∑j0iajs_i\sum_{j0}^ia_jsi∑j0iaj考虑前缀和的式子与卷积式子si∑jkiaj∗bks_i\sum_{jki}a_j*b_ksi∑jkiaj∗bk
发现前缀和相当于是乘了一个系数全是111的多项式∑i0∞1xi\sum_{i0}^∞1\ x_i∑i0∞1 xi
由等比数列公式可得该多项式的闭形式11−x\frac{1}{1-x}1−x1
kkk阶前缀和就相当于卷了kkk次卷积有结合律所以最后相当于原来的数组卷积1(1−x)k\frac{1}{(1-x)^k}(1−x)k1
这个式子的第nnn项系数为Cnk−1nCnk−1k−1C_{nk-1}^{n}C_{nk-1}^{k-1}Cnk−1nCnk−1k−1递推即可
至于为什么是这个系数可以打表验证其实发现前缀和是跟杨辉三角有着某种联系的意会也可
二.差分
差分相当于是乘了一个系数全是−1-1−1的多项式∑i0∞−1xi\sum_{i0}^∞ -1\ x^i∑i0∞−1 xi闭形式为1−x1-x1−x
最后相当于卷积(1−x)k∑i0∞(−1)iCkixi(1-x)^k\sum_{i0}^∞(-1)^iC_k^ix^i(1−x)k∑i0∞(−1)iCkixi
递推即可CkiCki−1×k−i1iC_k^iC_k^{i-1}\times \frac{k-i1}{i}CkiCki−1×ik−i1
#include cstdio
#include iostream
using namespace std;
#define mod 1004535809
#define int long long
#define maxn 400100
int len;
int r[maxn], inv[maxn], A[maxn], B[maxn];int read() {int x 0;char s getchar();while( s 0 || s 9 ) s getchar();while( 0 s s 9 ) {x ( ( x 1 ) ( x 3 ) ( s - 48 ) ) % mod;s getchar();}return x;
}int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}void NTT( int *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( opt 1 ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ) );for( int j 0;j len;j ( i 1 ) ) for( int k 0, w 1;k i;k , w w * omega % mod ) {int x v[j k], y v[j k i] * w % mod;v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod;}}if( opt -1 ) {int Inv qkpow( len, mod - 2 );for( int i 0;i len;i )v[i] v[i] * Inv % mod;}
}signed main() {int n, type, k;scanf( %lld, n );k read();scanf( %lld, type );for( int i 0;i n;i ) scanf( %lld, A[i] );inv[1] 1;for( int i 2;i n;i ) inv[i] ( mod - mod / i ) * inv[mod % i] % mod;B[0] 1;if( ! type ) {for( int i 1;i n;i )B[i] B[i - 1] * ( i k - 1 ) % mod * inv[i] % mod;}else {for( int i 1;i n;i )B[i] ( B[i - 1] * ( k - i 1 mod ) % mod ) % mod * inv[i] % mod;for( int i 1;i n;i )if( i 1 ) B[i] mod - B[i];}len 1;int l 0;while( len ( n 1 ) ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );NTT( A, 1 ), NTT( B, 1 );for( int i 0;i len;i ) A[i] A[i] * B[i] % mod;NTT( A, -1 );for( int i 0;i n;i ) printf( %lld , A[i] );return 0;
}PP4199
万径人踪灭 问不连续的关于某根对称轴对称的回文子序列个数
非常难做正面硬刚刚不动 (-ロ-)(-ロ-)
考虑转化问题关于某根对称轴对称的回文子序列个数-回文子串个数
而对于一个序列求其回文子串个数直接运用manachermanachermanacher即可求解
现在考虑怎么求关于某根对称轴对称的回文子序列个数
对称轴有两种情况假设左右对称两个位置字符相等个数为kkk不算对称轴
①以某个位置为轴
答案为2k1−12^{k1}-12k1−1那些位置以及对称轴选与不选再减去全都不选的情况
②以某两个位置的间隙为轴
答案为2k−12^k-12k−1
考虑每个位置fif_ifi以iii为对称轴的两个位置字符相等的个数
fi∑j0i[sj,si×2−j]f_i\sum_{j0}^i[s_j,s_{i\times 2-j}]fi∑j0i[sj,si×2−j]
非常可以这很卷积套用DDD题DNADNADNA的套路分字符自己卷自己再把个数加起来
注意其实卷积后求出的fif_ifi表示以i2\frac{i}{2}2i为对称轴除不尽就是以位置间隙为轴的意思
位置字符相等个数×2\times 2×2
所以真正的个数应该为fi2\frac{f_i}{2}2fi
但是如果i2\frac{i}{2}2i除得尽代表一个位置的话卷积中的gi2∗gi2g_\frac{i}{2}*g_{\frac{i}{2}}g2i∗g2i便只算了一次
不妨用⌊fi2⌋[2∣i]\lfloor\frac{f_i}{2}\rfloor[2|i]⌊2fi⌋[2∣i]来特别加上即可统计答案就是∑i02n−22⌊fi2⌋[2∣i]−1\sum_{i0}^{2n-2}2^{\lfloor\frac{f_i}{2}\rfloor[2|i]}-1∑i02n−22⌊2fi⌋[2∣i]−1
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 400100
#define int long long
#define MOD 1000000007
#define mod 998244353
int len;
int rev[maxn], A[maxn], B[maxn], f[maxn];int qkpow( int x, int y, int Mod ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % Mod;x x * x % Mod;y 1;}return ans;
}void NTT( int *v, int opt ) {for( int i 0;i len;i )if( i rev[i] ) swap( v[i], v[rev[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( opt 1 ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ), mod );for( int j 0;j len;j ( i 1 ) )for( int k 0, w 1;k i;k , w w * omega % mod ) {int x v[j k], y v[j k i] * w % mod;v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod;}}if( opt -1 ) {int inv qkpow( len, mod - 2, mod );for( int i 0;i len;i )v[i] v[i] * inv % mod;}
}int r[maxn], p[maxn];
char s[maxn];int manacher() {int n ( strlen( s ) 1 | 1 ), idx 0;for( int i 0;i n;i )p[i] ( i 1 ) ? s[idx ] : #;int R -1, C -1;for( int i 0;i n;i ) {r[i] ( R i ) ? min( R - i, r[C * 2 - i] ) : 1;while( i r[i] n ~ ( i - r[i] ) )if( p[i r[i]] p[i - r[i]] ) r[i] ;else break;if( i r[i] R ) R i r[i], C i;}int ans 0;for( int i 0;i n;i )ans ( r[i] 1 );return ans % MOD;
}signed main() {scanf( %s, s );int n strlen( s );len 1;int l 0;while( len ( n 1 ) ) len 1, l ;for( int i 0;i len;i )rev[i] ( rev[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int i 0;i n;i )if( s[i] a ) A[i] 1;for( int i 0;i n;i )if( s[i] b ) B[i] 1;NTT( A, 1 ), NTT( B, 1 );for( int i 0;i len;i )f[i] ( A[i] * A[i] % mod B[i] * B[i] % mod ) % mod;NTT( f, -1 );int ans 0;for( int i 0, k 1;i n * 2 - 2;i , k ^ 1 )ans ( ans qkpow( 2, ( f[i] 1 ) k, MOD ) - 1 MOD ) % MOD;printf( %lld\n, ( ans - manacher() MOD ) % MOD );return 0;
}QP4061
[HEOI2016/TJOI2016]求和
fn∑i0n∑j0iS(i,j)×2j×j!f_n\sum_{i0}^n\sum_{j0}^iS(i,j)\times 2^j\times j!fn∑i0n∑j0iS(i,j)×2j×j!
∵S(i,j)0[ij]∵ S(i,j)0[ij]∵S(i,j)0[ij]
∴fn∑i0n∑j0nS(i,j)×2j×j!∴f_n\sum_{i0}^n\sum_{j0}^nS(i,j)\times 2^j\times j!∴fn∑i0n∑j0nS(i,j)×2j×j!
S(n,m)1m!∑i0m(−1)iCmi(m−i)n∑i0n(−1)ii!(m−i)n(m−i)!S(n,m)\frac{1}{m!}\sum_{i0}^m(-1)^iC_m^i(m-i)^n\sum_{i0}^n\frac{(-1)^i}{i!}\frac{(m-i)^n}{(m-i)!}S(n,m)m!1∑i0m(−1)iCmi(m−i)n∑i0ni!(−1)i(m−i)!(m−i)n
fn∑j0n2j×j!∑i0n∑k0j(−1)kk!⋅(j−k)i(j−k)!∑j0n2j×j!∑k0j(−1)kk!⋅∑i0n(j−k)i(j−k)!f_n\sum_{j0}^n2^j\times j!\sum_{i0}^n\sum_{k0}^j\frac{(-1)^k}{k!}·\frac{(j-k)^i}{(j-k)!}\sum_{j0}^n2^j\times j!\sum_{k0}^j\frac{(-1)^k}{k!}·\frac{\sum_{i0}^n(j-k)^i}{(j-k)!}fn∑j0n2j×j!∑i0n∑k0jk!(−1)k⋅(j−k)!(j−k)i∑j0n2j×j!∑k0jk!(−1)k⋅(j−k)!∑i0n(j−k)i
换一下变量名更好看V●ᴥ●V
fn∑i0n2i×i!∑j0i(−1)jj!⋅∑k0n(i−j)k(i−j)!f_n\sum_{i0}^n2^i\times i!\sum_{j0}^i\frac{(-1)^j}{j!}·\frac{\sum_{k0}^n(i-j)^k}{(i-j)!}fn∑i0n2i×i!∑j0ij!(−1)j⋅(i−j)!∑k0n(i−j)k
令gi(−1)ii!,hi∑k0niki!in1−1(i−1)i!g_i\frac{(-1)^i}{i!},h_i\frac{\sum_{k0}^ni^k}{i!}\frac{i^{n1}-1}{(i-1)i!}gii!(−1)i,hii!∑k0nik(i−1)i!in1−1等比数列公式不可能还有人呢不会吧嘿嘿嘿qwq
fn∑i0n2i×i!∑j0ngj∗hi−jf_n\sum_{i0}^n2^i\times i!\sum_{j0}^ng_j*h_{i-j}fn∑i0n2i×i!∑j0ngj∗hi−j特别的g00,g1n1g_00,g_1n1g00,g1n1
NTTNTTNTT冲鸭
#include cstdio
#include iostream
using namespace std;
#define int long long
#define mod 998244353
#define maxn 400100
int n, m, len;
int r[maxn], f[maxn], g[maxn];
int fac[maxn], inv[maxn], facinv[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}void NTT( int *v, int opt ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( opt 1 ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ) );for( int j 0;j len;j ( i 1 ) )for( int k 0, w 1;k i;k , w w * omega % mod ) {int x v[j k], y v[j k i] * w % mod;v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod;}} if( opt -1 ) {int Inv qkpow( len, mod - 2 );for( int i 0;i len;i )v[i] v[i] * Inv % mod;}
}void init( int n ) {fac[0] inv[0] inv[1] facinv[0] 1;for( int i 1;i n;i )fac[i] fac[i - 1] * i % mod;facinv[n] qkpow( fac[n], mod - 2 );for( int i n - 1;i;i -- )facinv[i] facinv[i 1] * ( i 1 ) % mod;for( int i 2;i n;i )inv[i] ( mod - mod / i ) * inv[mod % i] % mod;
}signed main() {scanf( %lld, n );init( n );for( int i 0;i n;i ) {g[i] facinv[i];if( i 1 ) g[i] mod - g[i];}f[0] 1, f[1] n 1;for( int i 2;i n;i )f[i] ( qkpow( i, n 1 ) - 1 ) * inv[i - 1] % mod * facinv[i] % mod;len 1; int l 0;while( len ( n 1 ) ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );NTT( g, 1 ), NTT( f, 1 ); for( int i 0;i len;i )f[i] f[i] * g[i] % mod;NTT( f, -1 );int ans 0;for( int i 0;i n;i )ans ( ans qkpow( 2, i ) * fac[i] % mod * f[i] % mod ) % mod;printf( %lld\n, ans );return 0;
}缘遇逆天秘籍——金牌打野
搭配生成函数修炼事半功倍哦♪(´ε)
RP4841
[集训队作业2013]城市规划
求nnn个点的简单有标号无向连通图数目
法一分治FFTFFTFFT
设fif_ifi表示iii个点的有标号无向连通图数考虑列状态转移方程
呃—— (-ロ-) 好像转移不动
再设gig_igi表示iii个点的图的数量有i×(i−1)2\frac{i\times (i-1)}{2}2i×(i−1)条边每条可选可不选很容易就得出gi2i×(i−1)2g_i2^\frac{i\times (i-1)}{2}gi22i×(i−1)
gn∑i1nCn−1i−1fign−ig_n\sum_{i1}^nC_{n-1}^{i-1}f_ig_{n-i}gn∑i1nCn−1i−1fign−i
枚举111号点所在连通图的大小联通的方案数即为fif_ifi有标号所以从剩下的点中选i−1i-1i−1个乘Cn−1i−1C_{n-1}^{i-1}Cn−1i−1其余点分成什么样的 图都可以方案数为gn−ig_{n-i}gn−i
gn∑i1nCn−1i−1fign−iCn−1n−1fng0∑i1n−1Cn−1i−1fign−ifn∑i1n−1(n−1)!(i−1)!(n−i)!fign−ig_n\sum_{i1}^nC_{n-1}^{i-1}f_ig_{n-i}C_{n-1}^{n-1}f_ng_0\sum_{i1}^{n-1}C_{n-1}^{i-1}f_ig_{n-i}f_n\sum_{i1}^{n-1}\frac{(n-1)!}{(i-1)!(n-i)!}f_ig_{n-i}gn∑i1nCn−1i−1fign−iCn−1n−1fng0∑i1n−1Cn−1i−1fign−ifn∑i1n−1(i−1)!(n−i)!(n−1)!fign−i
⇒fn(n−1)!gn(n−1)!−∑i1n−1fi(i−1)!gn−i(n−i)!\Rightarrow \frac{f_n}{(n-1)!}\frac{g_n}{(n-1)!}-\sum_{i1}^{n-1}\frac{f_i}{(i-1)!}\frac{g_{n-i}}{(n-i)!}⇒(n−1)!fn(n−1)!gn−∑i1n−1(i−1)!fi(n−i)!gn−i
令Fifi(i−1)!,Gigii!F_i\frac{f_i}{(i-1)!},G_i\frac{g_i}{i!}Fi(i−1)!fi,Gii!gi则FnGn×n−∑i1n−1Fi∗Gn−iF_nG_n\times n-\sum_{i1}^{n-1}F_i*G_{n-i}FnGn×n−∑i1n−1Fi∗Gn−i
分治FFTFFTFFT卷积宝贝又出现了mua!(*╯3╰)
#include cstdio
#include iostream
using namespace std;
#define mod 1004535809
#define int long long
#define maxn 520100
int len;
int r[maxn], fac[maxn], inv[maxn], f[maxn], g[maxn], F[maxn], G[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}void NTT( int *v, int opt, int len ) {for( int i 0;i len;i )if( i r[i] ) swap( v[i], v[r[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( opt 1 ? 3 : mod / 3 1, ( mod - 1 ) / ( i 1 ) );for( int j 0;j len;j ( i 1 ) )for( int k 0, w 1;k i;k , w w * omega % mod ) {int x v[j k], y v[j k i] * w % mod;v[j k] ( x y ) % mod;v[j k i] ( x - y mod ) % mod;}}if( opt -1 ) {int Inv qkpow( len, mod - 2 );for( int i 0;i len;i )v[i] v[i] * Inv % mod;}
}void solve( int L, int R ) {if( L R ) return;int mid ( L R ) 1;solve( L, mid );int len 1, l 0;while( len R - L 1 ) len 1, l ;for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );for( int i L;i mid;i ) F[i - L] f[i];for( int i 1;i R - L;i ) G[i - 1] g[i];NTT( F, 1, len ), NTT( G, 1, len );for( int i 0;i len;i ) F[i] F[i] * G[i] % mod;NTT( F, -1, len );for( int i mid 1;i R;i ) f[i] ( f[i] - F[i - L - 1] mod ) % mod;for( int i 0;i len;i ) F[i] G[i] 0;solve( mid 1, R );
}void init( int n ) {fac[0] inv[0] 1;for( int i 1;i n;i ) fac[i] fac[i - 1] * i % mod;inv[n] qkpow( fac[n], mod - 2 );for( int i n - 1;i;i -- ) inv[i] inv[i 1] * ( i 1 ) % mod;for( int i 1;i n;i )g[i] qkpow( 2, i * ( i - 1 ) / 2 ) * inv[i] % mod, f[i] g[i] * i % mod;
}signed main() {int n;scanf( %lld, n );init( maxn - 1 );solve( 0, n );printf( %lld\n, f[n] * fac[n - 1] % mod );return 0;
}法二生成函数多项式求逆
gn∑i1nCn−1i−1fign−ig_n\sum_{i1}^nC_{n-1}^{i-1}f_ig_{n-i}gn∑i1nCn−1i−1fign−i
换一种推式子的方式
gn∑i1n(n−1)!(i−1)!(n−i)!fign−i⇒gn(n−1)!∑i1nfi(i−1)!gn−i(n−i)!g_n\sum_{i1}^n\frac{(n-1)!}{(i-1)!(n-i)!}f_ig_{n-i}\Rightarrow \frac{g_n}{(n-1)!}\sum_{i1}^{n}\frac{f_i}{(i-1)!}\frac{g_{n-i}}{(n-i)!}gn∑i1n(i−1)!(n−i)!(n−1)!fign−i⇒(n−1)!gn∑i1n(i−1)!fi(n−i)!gn−i
令G′,F,GG,F,GG′,F,G分别为它们的生成函数则G′(x)∑i0∞gi1xii!,F(x)∑i0∞fi1xii!,G(x)∑i0∞gixii!G(x)\sum_{i0}^∞g_{i1}\frac{x^i}{i!},F(x)\sum_{i0}^∞f_{i1}\frac{x^i}{i!},G(x)\sum_{i0}^∞g_i\frac{x^i}{i!}G′(x)∑i0∞gi1i!xi,F(x)∑i0∞fi1i!xi,G(x)∑i0∞gii!xi
G′F∗G⇒FG′GGF*G\Rightarrow F\frac{G}{G}G′F∗G⇒FGG′
多项式求逆即可
#include cmath
#include cstdio
#include iostream
using namespace std;
#define int long long
#define mod 1004535809
#define maxn 600000
int n, len, l;
int r[maxn], a[maxn], b[maxn], c[maxn], d[maxn], fac[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}void NTT( int *c, int f ) {for( int i 0;i len;i ) if( i r[i] ) swap( c[i], c[r[i]] );for( int i 1;i len;i 1 ) {int omega qkpow( f 1 ? 3 : 334845270, ( mod - 1 ) / ( i 1 ) );for( int j 0;j len;j ( i 1 ) ) {int w 1;for( int k 0;k i;k , w w * omega % mod ) {int x c[j k], y c[j k i] * w % mod;c[j k] ( x y ) % mod;c[j k i] ( x - y mod ) % mod;}}}if( f -1 ) {int inv qkpow( len, mod - 2 );for( int i 0;i len;i ) c[i] c[i] * inv % mod;}
}void polyinv( int deg, int *b ) {if( deg 1 ) { b[0] 1; return; }polyinv( deg 1 1, b );for( len 1, l 0;len ( deg 1 ) - 1;len 1, l );for( int i 0;i len;i ) r[i] r[i 1] 1 | ( ( i 1 ) l - 1 );for( int i 0;i deg;i ) c[i] a[i];for( int i deg;i n;i ) c[i] 0;NTT( c, 1 ), NTT( b, 1 );for( int i 0;i len;i ) b[i] ( 2 - b[i] * c[i] % mod mod ) % mod * b[i] % mod;NTT( b, -1 );for( int i deg;i n;i ) b[i] 0;
}signed main() {scanf( %lld, n ); fac[0] 1, n ;for( int i 1;i n;i ) fac[i] fac[i - 1] * i % mod;a[0] 1;for( int i 1;i n;i ) {a[i] qkpow( 2, i * ( i - 1 ) / 2 ) * qkpow( fac[i], mod - 2 ) % mod;d[i] qkpow( 2, i * ( i - 1 ) / 2 ) * qkpow( fac[i - 1], mod - 2 ) % mod;}polyinv( n, b );for( len 1, l 0;len ( n 1 );len 1, l );for( int i 0;i len;i ) r[i] r[i 1] 1 | ( ( i 1 ) l - 1 );NTT( d, 1 ), NTT( b, 1 );for( int i 0;i len;i ) d[i] d[i] * b[i] % mod;NTT( d, -1 );printf( %lld\n, d[n - 1] * fac[n - 2] % mod );return 0;
}法三生成函数多项式lnlnln
设fif_ifi表示iii个点的无标号的无向连通图数量gig_igi表示无标号的图数量令F(x),G(x)F(x),G(x)F(x),G(x)为别为其的EGFEGFEGF枚举连通块个数
G(x)∑i0∞F(x)ii!eF(x)⇒F(x)lnG(x)G(x)\sum_{i0}^∞\frac{F(x)^i}{i!}e^{F(x)}\Rightarrow F(x)lnG(x)G(x)∑i0∞i!F(x)ieF(x)⇒F(x)lnG(x)
最后[xn][x^n][xn]系数即为答案因为题目是有标号的连通图数所以要乘n!n!n!同理gig_igi是无标号的数G(x)G(x)G(x)的系数应为2i×(i−1)2i!\frac{2^\frac{i\times (i-1)}{2}}{i!}i!22i×(i−1) S[UVA4671]K-neighbor substrings
读完题目发现这是 D 的弱化版。同样的思路枚举字符设为 111 其余为 000卷积求出该字符匹配数量。
所有字符匹配数量求和然后判断是否 ≥m−K\ge m-K≥m−K 即可。
唯一的不同就是这个是求 本质不同的子串 数量首先想到的就是哈希。
但是很离谱单模双模哈希怎么样都会挂unsigned long long 自然溢出就可以通过。
#include map
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define ull unsigned long long
#define maxn 800005
map ull, bool mp;
int len, l;
int r[maxn], ans[maxn];
ull Hash[maxn], mi[maxn];
char a[maxn], b[maxn];struct complex {double x, i;complex(){}complex( double X, double I ) { x X, i I; }
}f[maxn], g[maxn], h[maxn];
double pi acos( -1.0 );
complex operator ( complex u, complex v ) {return complex( u.x v.x, u.i v.i );
}
complex operator - ( complex u, complex v ) {return complex( u.x - v.x, u.i - v.i );
}
complex operator * ( complex u, complex v ) {return complex( u.x * v.x - u.i * v.i, u.i * v.x u.x * v.i );
}void FFT( complex *c, int opt ) {for( int i 0;i len;i ) if( i r[i] ) swap( c[i], c[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x c[j k], y c[j k i] * w;c[j k] x y, c[j k i] x - y;}}}
}bool check( int l, int r ) {ull num Hash[r] - Hash[l - 1] * mi[r - l 1];if( mp[num] ) return 0;else { mp[num] 1; return 1; }
}int main() {mi[0] 1;for( int i 1;i maxn;i ) mi[i] mi[i - 1] * 131;int K, Case 0;while( scanf( %d, K ) and ~ K ) {scanf( %s %s, a, b );int n strlen( a ), m strlen( b );for( len 1, l 0;len ( n m );len 1, l ) len 1, l ;for( int i 0;i len;i ) r[i] r[i 1] 1 | ( i 1 ) l - 1; for( char ch a;ch b;ch ) {for( int i 0;i len;i ) {f[i] complex( ch a[i], 0 );h[i] complex( ch b[i], 0 );g[i] complex( 0, 0 );}for( int i 0;i m;i ) g[i] h[m - i - 1];FFT( f, 1 ), FFT( g, 1 );for( int i 0;i len;i ) f[i] f[i] * g[i];FFT( f, -1 );for( int i m - 1;i len;i ) ans[i - m 1] (int)( f[i].x / len 0.5 );}Hash[0] a[0] - a;for( int i 1;i n;i ) Hash[i] Hash[i - 1] * 131 (a[i] - a);int ret 0;for( int i 0;i n - m;i ) if( m - ans[i] K and check( i, i m - 1 ) ) ret ;printf( Case %d: %d\n, Case, ret );for( int i 0;i len;i ) ans[i] 0;mp.clear();}return 0;
}TSP8372 TSUM - Triple Sums
洛谷链接
AiAjAkSA_iA_jA_kSAiAjAkS 已经属于是条件反射了将值当成下标直接卷积就行 ansAiAjAkSans_{A_iA_jA_kS}ansAiAjAkS 。
但是这里有两个问题一个是忽略了 ijkijkijk 的顺序要求在最后答案 /6/6/6 即可。另一个是可能算重因为 AAA 并没有互不相同。
算重就容斥好了。B2Ai,C3AiB_{2A_i},C_{3A_i}B2Ai,C3Ai。
B,CB,CB,C 同样考虑顺序问题所以最后的 ansiai3−3aibi2cians_{i}a_i^3-3a_ib_i2c_iansiai3−3aibi2ci。再 IDFT\text{IDFT}IDFT 回去。
注意 AAA 有负的可能直接整体平移 200002000020000 即可这些都是小细节。
#include cmath
#include cstdio
#include iostream
using namespace std;
#define int long long
#define maxn 500000
int len, l;
int r[maxn];struct complex {double x, i;complex(){}complex( double X, double I ) { x X; i I; }
}a[maxn], b[maxn], c[maxn], ans[maxn];
double pi acos( -1.0 );
complex operator ( complex u, complex v ) {return complex( u.x v.x, u.i v.i );
}
complex operator - ( complex u, complex v ) {return complex( u.x - v.x, u.i - v.i );
}
complex operator * ( complex u, complex v ) {return complex( u.x * v.x - u.i * v.i, u.x * v.i u.i * v.x );
}void FFT( complex *c, int opt ) {for( int i 0;i len;i ) if( i r[i] ) swap( c[i], c[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x c[j k], y w * c[j k i];c[j k] x y, c[j k i] x - y;}}}
}signed main() {int n; scanf( %lld, n );for( int i 1, x;i n;i ) {scanf( %lld, x ); x 20000;a[x].x ;b[x * 2].x ;c[x * 3].x ;}for( len 1, l 0;len 150000;len 1, l );for( int i 0;i len;i ) r[i] r[i 1] 1 | (i 1) l - 1;FFT( a, 1 ), FFT( b, 1 ), FFT( c, 1 );for( int i 0;i len;i ) ans[i] a[i] * a[i] * a[i] - complex( 3, 0 ) * a[i] * b[i] complex( 2, 0 ) * c[i];FFT( ans, -1 );for( int i 0;i len;i ) {int x (int)( ans[i].x / len 0.5 );x / 6;if( x 0 ) printf( %lld : %lld\n, i - 60000, x );}return 0;
}U[CodeChef - COUNTARI]Arithmetic Progressions
分块和 FFTFFTFFT。
选择一个适当的块大小 blockblockblock然后枚举每个块。
将合法的三元组 (Ai,Aj,Ak)(A_i,A_j,A_k)(Ai,Aj,Ak) 分为两种情况考虑。
在块内。 枚举块内的两个点一个做 AiA_iAi一个做 Aj/AkA_j/A_kAj/Ak。 如果第三个是后面块的就需要知道后面未操作块中是该值的个数。 如果第三个是前面块或者本块的因为本块内元素的枚举有序所以不会算重就需要知道前面已操作块和本块已枚举 AiA_iAi 的数是该值的个数。 分别用 suf,pre,cntsuf,pre,cntsuf,pre,cnt 来记录后面未操作块前面已操作块和本块已操作数的信息。在块外。 AjA_jAj 在本块内AiA_iAi 在已操作块中AkA_kAk 在未操作块中。 这就是很常见的卷积了。这也是为什么上一种情况需要单独记录本块已操作数量而不是直接与 preprepre 合并。
最后每个块统计答案的时候顺便将 cnt→precnt\rightarrow precnt→pre 中。
选择好合适的块大小假设值最大值为 mmm时间复杂度为 O(n2blockblock⋅mlogm)O(\frac{n^2}{block}block·m\log m)O(blockn2block⋅mlogm)。
#include cmath
#include cstdio
#include iostream
using namespace std;
#define maxn 200000
int len, l, n, block, Max;
long long ans;
int r[maxn], a[maxn], pre[maxn], cnt[maxn], suf[maxn];struct complex {double x, i;complex(){}complex( double X, double I ) { x X, i I; }
}f[maxn], g[maxn];
double pi acos( -1.0 );
complex operator ( complex u, complex v ) {return complex( u.x v.x, u.i v.i );
}
complex operator - ( complex u, complex v ) {return complex( u.x - v.x, u.i - v.i );
}
complex operator * ( complex u, complex v ) {return complex( u.x * v.x - u.i * v.i, u.x * v.i u.i * v.x );
}void FFT( complex *c, int opt ) {for( int i 0;i len;i ) if( i r[i] ) swap( c[i], c[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j (i 1) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x c[j k], y c[j k i] * w;c[j k] x y, c[j k i] x - y;}}}if( opt -1 ) for( int i 0;i len;i ) c[i].x / len;
}int main() {scanf( %d, n );block sqrt( n );for( int i 1;i n;i ) {scanf( %d, a[i] );Max max( Max, a[i] );suf[a[i]] ;}for( len 1;len (Max 1);len 1, l );for( int i 0;i len;i ) r[i] r[i 1] 1 | (i 1) l - 1;for( int l 1;l n;l block ) {int r min( l block - 1, n ), k;for( int i l;i r;i ) suf[a[i]] --;for( int i l;i r;i ) {for( int j i 1;j r;j ) {k (a[i] 1) - a[j];if( 1 k and k Max ) ans cnt[k] pre[k];k (a[j] 1) - a[i];if( 1 k and k Max ) ans suf[k];}cnt[a[i]] ;}for( int i 0;i Max;i ) {f[i] complex( pre[i], 0 );g[i] complex( suf[i], 0 );}for( int i Max 1;i len;i ) {f[i] complex( 0, 0 );g[i] complex( 0, 0 );}FFT( f, 1 ), FFT( g, 1 );for( int i 0;i len;i ) f[i] f[i] * g[i]; FFT( f, -1 );for( int i l;i r;i ) {ans (long long)( f[a[i] 1].x 0.5 );pre[a[i]] , cnt[a[i]] --;}}printf( %lld\n, ans );return 0;
}VCodeForces528D Fuzzy Search
洛谷链接
做了很多个这种 {A,T,G,C}\text{\{A,T,G,C\}}{A,T,G,C} 的字符 FFT/NTT\text{FFT/NTT}FFT/NTT 的题后我发现 这种多个字符之间的适配问题一般都是拆开单个单个字符做的。
考虑最基础的适配是要求完全相同即 k0k0k0 的严苛条件我们套路地采取的是翻转一个串gi′gm−i−1g_ig_{m-i-1}gi′gm−i−1使得卷积下标和为定值分字符卷积后求和判断是否和数组长度相同。
这是解决字符适配问题的通解基础所有题目都只是在这个的基础上进行系列的改动罢了。
对于一个字符 chchch。
设 fi1/0f_i1/0fi1/0 表示 SiS_iSi 偏差 kkk 以内是否有字符 chchch 出现即 fi[∃j∈[i−k1,ik−1]Sjch]f_i\big[\exist_{j\in[i-k1,ik-1]\ }S_jch\big]fi[∃j∈[i−k1,ik−1] Sjch]。
设 gi1/0g_i1/0gi1/0 表示 TiT_iTi 是否为字符 chchch即 gi[Tich]g_i\big[T_ich\big]gi[Tich]。
同样地翻转 ggggi′gm−i−1g_{i}g_{m-i-1}gi′gm−i−1然后和 fif_ifi 卷积后为 hih_ihi。
则如果 hi≠0h_i\neq 0hi0 也就意味着有 hih_ihi 个 TachT_achTach 在 kkk 偏差内有对应的 SbchS_bchSbch。
注意通过题意可以知道有可能 Ta1,Ta2T_{a_1},T_{a_2}Ta1,Ta2 对应的是同一个 bbb。
多个字符累和 hih_ihi 后对于 himh_imhim 的 iii 位置就意味着整个 TTT 都适配成功。
#include cmath
#include cstdio
#include iostream
using namespace std;
#define maxn 1000000
int r[maxn];
int len, l;struct complex {double x, i;complex(){}complex( double X, double I ) { x X, i I; }
}f[maxn], g[maxn];
double pi acos( -1.0 );
complex operator ( complex u, complex v ) {return complex( u.x v.x, u.i v.i );
}
complex operator - ( complex u, complex v ) {return complex( u.x - v.x, u.i - v.i );
}
complex operator * ( complex u, complex v ) {return complex( u.x * v.x - u.i * v.i, u.x * v.i u.i * v.x );
}void FFT( complex *c, int opt ) {for( int i 0;i len;i ) if( i r[i] ) swap( c[i], c[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), sin( pi / i ) * opt );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x c[j k], y c[j k i] * w;c[j k] x y, c[j k i] x - y;}}}if( opt -1 ) for( int i 0;i len;i ) c[i].x / len;
}#define inf 0x3f3f3f3f
int n, m, k;
int cnt[maxn];
char s[maxn], t[maxn];void work( char ch ) {for( int i 0;i len;i ) f[i] g[i] complex( 0, 0 );int lst -inf;for( int i 0;i n;i ) {if( s[i] ch ) lst i;if( i - lst k ) f[i] complex( 1, 0 );}lst inf;for( int i n - 1;~ i;i -- ) {if( s[i] ch ) lst i;if( lst - i k ) f[i] complex( 1, 0 );}for( int i 0;i m;i )if( t[i] ch ) g[m - i - 1] complex( 1, 0 );FFT( f, 1 ), FFT( g, 1 );for( int i 0;i len;i ) f[i] f[i] * g[i];FFT( f, -1 );for( int i 0;i len;i ) cnt[i] int( f[i].x 0.5 );
}signed main() {scanf( %d %d %d %s %s, n, m, k, s, t );for( len 1;len n m;len 1, l );for( int i 0;i len;i ) r[i] r[i 1] 1 | ( i 1 ) l - 1;work( A ), work( T ), work( G ), work( C );int ans 0;for( int i 0;i len;i ) if( cnt[i] m ) ans ;printf( %d\n, ans );return 0;
}WCodeForces 954I Yet Another String Matching Problem
洛谷链接
两个字符串比对通过一些操作使得相应位是一样的。这种“比对”一般都是转化为图论然后与连通块有关。
基础模型可以认为是两个序列连边 Ai→BiA_i\rightarrow B_iAi→Bi 求连通块个数。
先只考虑两个串的距离如何计算
连边 Si→TiS_i\rightarrow T_iSi→Ti 忽略原本就相同的位置后会形成若干的连通块。
一个联通块中只需要操作 ∣连通块∣−1|连通块|-1∣连通块∣−1 次就能将整个连通块变为相同的字符。
多个连通块之间是有向边的存在是一个有向无环图最后会归中于某个字符。
所以两个串的距离即为 (∑∣连通块∣)−1\Big(\sum{|连通块|}\Big)-1(∑∣连通块∣)−1。
具体实现可以用并查集维护字符集 {a,b,c,d,e,f}\{a,b,c,d,e,f\}{a,b,c,d,e,f}。每次合并原来不同的两个字符集的时候答案 111 即可。
现在考虑有多个 SSS 的子集 S′SS′ 在与 TTT 适配。
设 ansi:ans_i:ansi: 考虑 S[i−∣T∣1,i]S[i-|T|1,i]S[i−∣T∣1,i] 与 TTT 的适配距离答案。
同样地分字符计算贡献再累和。
枚举 S′SS′ 的字符 xxx和 TTT 的字符 yyy 进行适配x≠yx\neq yxy。
我们需要判断是否有 Si′x,TiyS_ix,T_iySi′x,Tiy 的位置如果存在就意味着是需要操作的。
就执行并查集合并答案 111如果之前的某些字符配对组合已经让 x,yx,yx,y 在同一个并查集就不要加这个贡献。
每个 iii 不同结尾适配距离也不同对应的并查集也不同。所以每个位置都要自开一个独立的并查集。
本题的距离适配完全是适配的基础模型翻转 TTT 再卷积为 fff判断 fif_ifi 是否为 111在 fif_ifi 的并查集里面进行合并即可。
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 1000000
int len, l, n, m;
int r[maxn], ans[maxn];
char s[maxn], t[maxn];struct complex {double x, i;complex(){}complex( double X, double I ) { x X; i I; }
}f[maxn], g[maxn];
double pi acos( -1.0 );
complex operator ( complex u, complex v ) {return complex( u.x v.x, u.i v.i );
}
complex operator - ( complex u, complex v ) {return complex( u.x - v.x, u.i - v.i );
}
complex operator * ( complex u, complex v ) {return complex( u.x * v.x - u.i * v.i, u.x * v.i v.x * u.i );
}void FFT( complex *c, int opt ) {for( int i 0;i len;i ) if( i r[i] ) swap( c[i], c[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), opt * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x c[j k], y c[j k i] * w;c[j k] x y, c[j k i] x - y;}}}if( opt -1 ) for( int i 0;i len;i ) c[i].x / len;
}struct DSU {int f[10];void init() { for( int i 0;i 6;i ) f[i] i; }int find( int x ) { return f[x] x ? x : f[x] find( f[x] ); }void merge( int x, int y ) { x find( x ), y find( y ), f[y] x; }
}dsu[maxn];void work( int x, int y ) {for( int i 0;i len;i ) f[i] g[i] complex( 0, 0 );for( int i 0;i n;i ) f[i].x ( s[i] - a x );for( int i 0;i m;i ) g[m - i - 1].x ( t[i] - a y );FFT( f, 1 ), FFT( g, 1 );for( int i 0;i len;i ) f[i] f[i] * g[i];FFT( f, -1 );for( int i 0;i n;i ) {int c int( f[i].x 0.5 );if( ! c ) continue;if( dsu[i].find( x ) ^ dsu[i].find( y ) ) ans[i] , dsu[i].merge( x, y );}
}int main() {scanf( %s %s, s, t );n strlen( s ), m strlen( t );for( len 1;len n m;len 1, l );for( int i 0;i len;i ) r[i] r[i 1] 1 | ( i 1 ) l - 1;for( int i 0;i n;i ) for( int j 0;j 6;j ) dsu[i].init();for( int i 0;i 6;i ) for( int j 0;j 6;j ) if( i ^ j ) work( i, j );for( int i m - 1;i n;i ) printf( %d\n, ans[i] );return 0;
}
