雨默合肥做网站推广,vi设计可以做哪方面的,网站美食建设图片,简要叙述如何规划建设一个企业网站5322 Hope [CDQ分治FFT加速计算dp] 题意
每一个每一个排列,排列中每个数向它后面第一个比它大的数连一条边.
每个排列对于答案的贡献是这个排列所生成的图中的每一个联通量中点的个数的平方之积.
例如:排列 1,2,3,6,4,51,2,3,6,4,51,2,3,6,4,5
其中 1,2,3,61,2,3,61,2,3,6形…5322 Hope [CDQ分治FFT加速计算dp] 题意
每一个每一个排列,排列中每个数向它后面第一个比它大的数连一条边.
每个排列对于答案的贡献是这个排列所生成的图中的每一个联通量中点的个数的平方之积.
例如:排列
1,2,3,6,4,51,2,3,6,4,51,2,3,6,4,5
其中
1,2,3,61,2,3,61,2,3,6形成一个大小为444的联通分量.
4,54,54,5形成一个大小为222的联通分量.
那么这个排列的贡献就是42∗22644^2*2^2 6442∗2264.
我们需要求所有排列的贡献.
题解
这种题做法一般就是dpdpdp.
我们枚举排列中最大的数nnn的所在的位置,当nnn的位置固定以后,所有在nnn前面的数都会与nnn形成一个连通分量.而后面的所有的数就组成了一个子问题.
定义dp[n]dp[n]dp[n]表示nnn的所有排列所形成的贡献之和.
我们可以得到递推公式.
dp[n]∑i1nCn−1i−1∗(i−1)!∗i2∗dp[n−i]dp[n] \sum_{i1}^{n}C_{n-1}^{i-1}*(i-1)!*i^2*dp[n-i]dp[n]∑i1nCn−1i−1∗(i−1)!∗i2∗dp[n−i]
化简得到
dp[n](n−1)!∑i1ni2∗dp[n−i](n−i)!dp[n] (n-1)!\sum_{i1}^{n}i^2*\frac{dp[n-i]}{(n-i)!}dp[n](n−1)!∑i1ni2∗(n−i)!dp[n−i]
记F[i]dp[i]i!,G[i]i2F[i]\frac{dp[i]}{i!},G[i]i^2F[i]i!dp[i],G[i]i2
那么
dp[n](n−1)!∑i1nG[i]F[n−i]dp[n] (n-1)!\sum_{i1}^{n}G[i]F[n-i]dp[n](n−1)!∑i1nG[i]F[n−i]
观察到dp[n]dp[n]dp[n]的递推公式是一个卷积的形式.
求卷积我们显然想到了FFT/NTTFFT/NTTFFT/NTT来加速dpdpdp的计算,对于要求出所有的dp[n]dp[n]dp[n],因此我们需要用CDQCDQCDQ分治来辅助计算FFT/NTTFFT/NTTFFT/NTT.
采用分治策略,即将区间F[l,r]F[l,r]F[l,r]分成区间F[l,mid]F[l,mid]F[l,mid]和F[mid1,r]F[mid1,r]F[mid1,r]两个区间.
用F[l,mid]F[l,mid]F[l,mid]区间的内容和GGG多项式做卷积,即可计算出F[l,mid]F[l,mid]F[l,mid]部分对于F[mid1,r]F[mid1,r]F[mid1,r]的影响.注意!这里要求F[l,mid]F[l,mid]F[l,mid]必须已经完整的被计算出来了.随后再地归计算F[mid1,r]F[mid1,r]F[mid1,r]部分,解决它们内部的贡献以来.
因此代码的大致框架就是:
void solve(int l,int r) {if(l r) return ;int mid (l r) 1;solve(l,mid);//保证区间F[l,mid]已经被完整的计算出来了Conv();//求卷积,计算F[l,mid]对F[mid1,r]的贡献.注意此时F[1,l-1]对F[mid1,r]的贡献早已被求过了.//注意在此时,F[mid1,r]内部依赖于F[1,mid]的贡献已经全部被计算出来了,因此下一步求内部F[mid1,r]对F[mid1,r]的贡献.solve(mid1,r);
}举个栗子
当n4n4n4时刻 初始[1,1][1,1][1,1]就算完整的被计算出来了. 先求[1,1][1,1][1,1]对[2,2][2,2][2,2]的贡献,从而得到了完整的[1,2][1,2][1,2]. 然后计算[1,2][1,2][1,2]对[3,4][3,4][3,4]的贡献,此时[3,3][3,3][3,3]已经被完整的计算出来了. 然后算[3,3][3,3][3,3]对于[4,4][4,4][4,4]的贡献,导致[4,4][4,4][4,4]被完整的计算出来. 至此[1,4][1,4][1,4]都被完整的计算出来了.
注意
其中计算[l,mid][l,mid][l,mid]对[mid1,r][mid1,r][mid1,r]的贡献的时候,需要注意:
x∈[mid1,r]x \in [mid1,r]x∈[mid1,r]
F[x]←F[l0]∗G[x−l]...F[l(mid−l)]∗G[x−mid]F[x] \leftarrow F[l0]*G[x-l] ... F[l(mid-l)]*G[x-mid]F[x]←F[l0]∗G[x−l]...F[l(mid−l)]∗G[x−mid]
将F[l],F[l1],...,F[mid]F[l],F[l1],...,F[mid]F[l],F[l1],...,F[mid]填在数组a[0],a[1],...,a[mid−l]a[0],a[1],...,a[mid-l]a[0],a[1],...,a[mid−l]的位置.
将G[0],G[1],G[2],...,G[n]G[0],G[1],G[2],...,G[n]G[0],G[1],G[2],...,G[n]填在数组b[0],b[1],b[2],..,b[n]b[0],b[1],b[2],..,b[n]b[0],b[1],b[2],..,b[n]的位置. 然后求个卷积ca⨂bc a\bigotimes bca⨂b
最后卷积数组的c[x−l]c[x-l]c[x−l]位置的值就是F[x]F[x]F[x].
描述上稍微有点问题,FFF和dpdpdp的关系有点混淆,诸位看我代码就ok了.
代码
#include iostream
#include algorithm
#include cstring
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)
#define clr(x) memset(x,0,sizeof(x))
#define setinf(x) memset(x,0x3f,sizeof(x))
#define Max(x,y) x std::max(x,y)
#define Min(x,y) x std::min(x,y)
#define Add(x,y) x (((x)(y))%P)
#define Sub(x,y) x (((x)-(y)P%P)
#define Mul(x,y) x ((x)*(y)%P)
typedef long long LL;
const int N 1 20;
const int P 998244353;
const int G 3;
const int NUM 20;LL wn[NUM];
LL a[N], b[N];LL quick_mod(LL a, LL b, LL m)
{LL ans 1;a % m;while(b){if(b 1){ans ans * a % m;b--;}b 1;a a * a % m;}return ans;
}void GetWn()
{for(int i 0; i NUM; i){int t 1 i;wn[i] quick_mod(G, (P - 1) / t, P);}
}
void Rader(LL a[], int len)
{int j len 1;for(int i 1; i len - 1; i){if(i j) std::swap(a[i], a[j]);int k len 1;while(j k){j - k;k 1;}if(j k) j k;}
}void NTT(LL a[], int len, int on)
{Rader(a, len);int id 0;for(int h 2; h len; h 1){id;for(int j 0; j len; j h){LL w 1;for(int k j; k j h / 2; k){LL u a[k] % P;LL t w * a[k h / 2] % P;a[k] (u t) % P;a[k h / 2] (u - t P) % P;w w * wn[id] % P;}}}if(on -1){for(int i 1; i len / 2; i)std::swap(a[i], a[len - i]);LL inv quick_mod(len, P - 2, P);for(int i 0; i len; i)a[i] a[i] * inv % P;}
}void Conv(LL a[], LL b[], int n)
{NTT(a, n, 1);NTT(b, n, 1);for(int i 0; i n; i)a[i] a[i] * b[i] % P;NTT(a, n, -1);
}LL dp[N],Fac[N],iFac[N];void solve(int l,int r) {if(l r) return ;int mid (l r) 1;solve(l,mid);int len 1;while(len (r-l1)) len 1;rep(i,0,len) {b[i] 1LL*i*i%P;}rep(i,l,mid) {a[i-l] dp[i]*iFac[i]%P;}rep(i,mid-l1,len) a[i] 0;Conv(a,b,len);rep(i,mid1,r) {dp[i] (dp[i] (a[i-l]*Fac[i-1]%P))%P;}solve(mid1,r);
}int main()
{Fac[0] iFac[0] 1;rep(i,1,N-1) {Fac[i] Fac[i-1]*i % P;iFac[i] quick_mod(Fac[i],P-2,P);}GetWn();dp[0] 1;solve(0,100000);int n;while(std::cin n) {std::cout dp[n] std::endl;}return 0;
}
