题解 CF848E 【Days of Floral Colours】

~~据说题目的背景是来自于[花色日和](https://music.163.com/#/song?id=29154917),喜欢v曲的可以去听听看吧……~~ 生成函数好题啊……十分考验生成函数的基本功是否扎实…… 备注:这里的做法是$O(40n)$的(虽然这个复杂度记号并不标准就是了)，应该远远快于$O(nlogn)$的多项式求逆和$O(nlog^2n)$的分治fft ## 前置芝士：计算能力 本题解涉及类似于给一个分式求2阶导以及对十几次的多项式进行加减乘除之类的dirty work，如果对自己的计算能力没有信心的话 **请善用[wolfram alpha](https://www.wolframalpha.com)** ## 前置芝士:生成函数 请确保您精通生成函数那一套理论 ------ # 本题题解 由于翻译是机翻所以这里简要解释一下题意…… 给定一个2n的点的环，环上的每个点都有标号，现在要给这个环连一些边，需要满足以下限制 1.每个点的度数恰好是1 2.有边的点之间的距离要么小于等于2要么恰好是n 3.如果$(i,j)$有边，那么在$(i,j)$正对面的点$(i',j')$也必须有边 4.至少有一对点距离为n并且有边相连 定义一个环的权值按照如下方法计算 删掉所有距离为n并且有边的点对，这样环会分裂成若干个段，这个环的权值就是所有段长度的乘积 求所有合法的环的权值之和模998244353的结果 ------ ## 从一个naive的$O(n^2)$dp开始 _这里就不放图了，dp数组的定义和官方题解的定义是一样的，可以去官方题解看图_ 一个非常重要的性质是:环是对称的，确定1到n之间的连边情况就可以反着推出来后一半的连边情况 我们发现距离为n的点对恰好是面对面的，因此面对面的点连边不会影响其他的点的连边情况 由于至少有一对点是面对面的，因此我们可以以一个面对面的点对为轴将整个环撕成两个长度为n的序列 接下来无非就是观察环当中可能出现哪些图形然后把他们用相应的dp数组表示就可以了 经过观察我们发现可能出现的图形有以下几种  那么我们发现右上角那种图形非常讨厌，因为两边的点分别属于两个段 那么我们先来处理只有图形2,3的段的**方案数**，设$g(n)$表示长度为n并且只含图形2,3的段的方案数 很容易的可以得到一个递推式是 $$g(n)=g(n-2)+g(n-4),g(0)=g(2)=1,g(1)=g(3)=0$$ 为了方便起见我们再定义几个数组 $$g_{0}(n)=g(n)n^2$$ $$g_{1}(n)=g(n)(n+1)^2$$ $$g_{2}(n)=g(n)(n+2)^2$$ 接下来我们设$f_{0}(n)$表示以一个图形4开头,有一段长度为n的段的序列的权值和 设$f_{1}(n)$表示以一个图形4开头，中间有一个长度为n的段，以$1/3$个图形1结尾的序列的权值和 设$f_{2}(n)$表示以$2/3$个图形4开头，中间有一个长度为n的段，以$1/3$个图形1结尾的序列的权值和 那么我们可以将这些图形拼来拼去，最后可以得到这样的转移式子 $$f_{0}(n)=g_{0}(n)+\sum_{i+j=n-1}g_{0}(j)f_{0}(i)+\sum_{i+j=n-2}g_{1}(j)f_{1}(i)$$ $$f_{1}(n)=g_{1}(n)+\sum_{i+j=n-1}g_{1}(j)f_{0}(i)+\sum_{i+j=n-3}g_{2}(j)f_{1}(i)$$ $$f_{2}(n)=g_{2}(n)+\sum_{i+j=n-1}g_{1}(j)f_{1}(j)+\sum_{i+j=n-3}g_{2}(j)f_{2}(j)$$ 如果只是朴素的实现转移的话复杂度是$O(n^2)$的，现在让我们来考虑如何根据这三个数组拼凑出答案来 最后的答案是一个环并且至少会有一对距离为n的点，那么我们可以钦定点1和点n+1一定是一对同色点，对于不是的情况我们可以把得到的方案逆时针旋转一个角度从而生成这样的方案 首先是只有一对距离为n的点的情况，这种方案的贡献和是 $$(g(n-1)+g(n-3))^(n-1)^2$$ 其中n-1的一项表示最后的方案当中不存在图形1而n-3的一项表示存在图形1 其次是有更多对距离为n的点的方案，对于这种情况我们对点1和点n+1是否是一对同色点进行分情况讨论，对于是同色点的情况我们直接计数而对于不是同色点的情况，我们尝试着用一个1和n+1是同色点的方案逆时针旋转一个角度来得到这种方案 那么此时我们发现此时一个方案会被计算好几次，因为我们有许多不同的旋转角度可以得到这种方案，采用计数题当中的常见技巧，我们选择最小的旋转角度进行计数 那么此时我们需要枚举第二对距离为n的同色点与点1的距离 我们可以得到这样的柿子 $$\sum_{i=2}^{n-2}i(i-1)^2(g(i-1)f_{0}(n-i-1)+2g(i-2)f_{1}(n-i-2)+g(i-3)f_{2}(n-i-3))$$ 其中第一项表示有i种不同的旋转角度可以选择，(其他情况第二对点将会变成第一对点，这个自己画图理解下),平方项表示距离的对答案的贡献 第二项表示剩下的序列是f1型时对答案的贡献，第3项表示的是f2型序列对答案的贡献，第3项表示f3型序列对答案的贡献 (如果直接写“自己卷自己”形式的分治fft优化上述的dp我们将会得到一个优秀的 $O(nlog^2n)$算法) 如此这般我们就得到了一个简单易懂(并不的)$O(N^2)/O(nlog^2n)$算法了,让我们尝试加速这个算法 ## 使用生成函数表示转移 我们发现我们的转移方程都是一些数列做卷积的形式，这启示我们列几个生成函数的柿子出来 那么我们不妨设 $$G_{0}(z)=\sum_{k}g_{0}(k)z^k$$ $$G_{1}(z)=\sum_{k}g_{1}(k)z^k$$ $$G_{2}(z)=\sum_{k}g_{2}(k)z^k$$ $$F_{0}(z)=\sum_{k}F_{0}(k)z^k$$ $$F_{1}(z)=\sum_{k}F_{1}(k)z^k$$ $$F_{2}(z)=\sum_{k}F_{2}(k)z^k$$ 那么刚才转移方程就可以重新写成生成函数的形式 $$F_{0}(z)=G_{0}(z)+G_{0}(z)F_{0}(z)z+G_{1}(z)F_{1}(z)z^3$$ $$F_{1}(z)=G_{1}(z)+G_{1}(z)F_{0}(z)z+G_{2}(z)F_{1}(z)z^3$$ $$F_{2}(z)=G_{2}(z)+G_{1}(z)F_{1}(z)z+G_{2}(z)F_{2}(z)z^3$$ 我们如果把$G_{0,1,2}(z),z,z^3$这些项当成常数，把$F_{0}(z),F_{1}(z)$ 这些多项式当成变量，那么前两个递推式就是一个二元一次方程组，用前面的柿子解出$F_{1}(z)$之后我们就可以用$F_{1}(z)$表示$F_{2}(z)$了 那么稍微解一下方程我们可以得到这样的表达式~~(dirty works警告)~~ $$F_{0}(z)=\frac{G_{1}(z)z^3-G_{0}(z)(G_{2}(z)z^3-1)}{(G_{0}(z)z-1)(G_{2}(z)z^3-1)-G_{1}^{2}(z)z^4}$$ $$F_{1}(z)=\frac{G_{1}(z)}{(G_{0}(z)z-1)(G_{2}(z)z^3-1)-G_{1}^{2}(z)z^4}$$ $$F_{2}(z)=\frac{G_{2}(z)+G_{1}(z)zF_{1}(z)}{1-G_{2}(z)z^3}$$ 如果我们使用多项式求逆和多项式乘法直接求解上面的生成函数，复杂度是$O(nlogn)$的，当然代价是ntt和求逆出了名的大常数 那么有没有更块的做法呢？答案是有的 ## 生成函数的求导 让我们从问题的开头开始 我们定义了一个数列$g$满足递推式 $$g(n)=g(n-2)+g(n-4),g(0)=1,g(1)=0$$ 那么如果我们稍微观察一下这个柿子就会立马得知这个数列的奇数项是没有值的，而偶数项和斐波那契数列数列是一样的，具体点讲我们有$g(2n)=fib(n)$那么我们可以很快的求出数列$g$的生成函数就是 $$G(z)=\frac{1}{1-z^{2}-z^{4}}$$ 那么问题来了，我们知道了$G(z)$的生成函数并没有什么卵用，因为我们需要的是$G_{0,1,2}(z)$的生成函数，而数列$g_{0,1,2}$是$g$数列乘了一个下标，这就让我们非常头痛了…… 此时我们想到了求导这个有趣的工具 如果我们将数列$g$的生成函数$G(z)$求导之后再乘上z,那么产生的新数列$g'$的通项公式就是$g'(n)=g(n)n$ 不过我们要拼凑的数列是形如$g_{0}(n)=g(n)n^2$的形式，为了凑出二次项，我们将生成函数求二阶导之后乘上$z^2$，得到的数列$g''$的通项公式就是$g''(n)=g(n)n(n-1)=g(n)n^2-g(n)n$ 此时我们稍微配上一些系数就能用$g,g',g''$三个数列拼凑出$g_{0},g_{1},g_{2}$了 具体点来讲我们有这样的柿子 $$G_{0}(z)=z^2G''(z)+zG'(z)$$ $$G_{1}(z)=z^2G''(z)+3zG'(z)+G(z)$$ $$G_{2}(z)=z^2G''(z)+5zG'(z)+4G(z)$$ 然后现在我们需要接着做一些dirty works,比如求2阶导以及把几个分式加起来，相信大家可以很快的手算出来(算不出来的可以像我一样使用wolfram alpha)，总之我们得到了这样的三个生成函数 $$G_{0}(z)=\frac{16z^8+12z^6+20z^4+4z^2}{-z^{12}-3z^{10}+5z^6-3z^2+1}$$ $$G_{1}(z)=\frac{9z^8+2z^6+23z^4+6z^2+1}{-z^{12}-3z^{10}+5z^6-3z^2+1}$$ $$G_{2}(z)=\frac{4z^8-4z^6+24z^4+4z^2+4}{-z^{12}-3z^{10}+5z^6-3z^2+1}$$ (相当考验人类智慧的爆算……，建议还是用wolfram alpha帮你计算好了) 然后经过观察我们发现这三个生成函数的分母都是一样的，有所不同的只是分母而已 那么我们可以令 $$Q(z)=-z^{12}-3z^{10}+5z^6-3z^2+1$$ $$P_{0}(z)=16z^8+12z^6+20z^4+4z^2$$ $$P_{1}(z)=9z^8+2z^6+23z^4+6z^2+1$$ $$P_{2}(z)=4z^8-4z^6+24z^4+4z^2+4$$ 那么我们就会发现$G_{0,1,2}(z)=\frac{P_{0,1,2}(z)}{Q(z)}$ 此时在$F_{0}(z),F_{1}(z)$上下同时乘以$Q^2(z)$我们就可以用$P_{0,1,2}(z),Q(z)$来表示$F_{0}(z),F_{1}(z)$了 具体来讲我们会得到这样的柿子 $$F_{0}(z)=\frac{P_{1}(z)Q(z)z^3-P_{0}(z)(P_{2}(z)z^3-1)}{(P_{0}(z)z-1)(P_{2}(z)z^3-1)-P_{1}^{2}(z)z^4}$$ $$F_{1}(z)=\frac{P_{1}(z)Q(z)}{(P_{0}(z)z-1)(P_{2}(z)z^3-1)-P_{1}^{2}(z)z^4}$$ 那么问题来了，如何消去$F_{2}$当中的$F_{1}$呢? 一种可行的方法当然是爆算，不过我们为了在这里减少一点计算量可以令$F_{1}(z)=\frac{M(z)}{N(z)}$ 然后在$F_{2}$的分母上下同时乘上一个$N(z)Q(z)$我们就可以得到这样的柿子了 $$F_{2}(z)=\frac{N(z)P_{2}(z)+P_{1}(z)M(z)z}{N(z)(Q(z)-P_{2}(z)z^3)}$$ 好啦你会说我们胡乱推了一波柿子最后不还是要写多项式求逆吗？ 仔细观察我们推出来的柿子，你会发现和之前的求逆不同的是,我们推出来的式子的分子和分母都是一个**低阶的多项式**，次数不会超过40，这有什么用呢？ 这里科普一个暴力计算$\frac{P(x)}{Q(x)}$的方法 我们令$F(x)=\frac{P(x)}{Q(x)},C(x)=1-Q(x)$ 那么可以很容易的得到 $$F(x)=\frac{P(x)}{1-C(x)}$$ $$F(x)(1-C(x))=P(x)$$ $$F(x)=F(x)C(x)+P(x)$$ 上面的柿子实际上描述了一个常系数线性递推式,如果$C(x)$的次数不是很大我们完全可以暴力计算$F(x)$比如在这道题中我们就可以用这个trick非常块的把$F_{0,1,2}$三个生成函数的前n项算出来 于是我们就得到了一个$O(40n)/O(n)$的算法了，可以轻松的通过本题~ 上代码~ ```Cpp #include<cstdio> #include<algorithm> using namespace std;const int N=1e5+10;const int S=40; typedef unsigned long long ll;const ll mod=998244353; struct poly { int a[S+10]; inline int& operator [](const int & x){return a[x];} poly(){for(int i=0;i<S;i++)a[i]=0;} friend poly operator * (poly a,poly b) { poly c;for(int i=0;i<S;i++) for(int j=0;j<S&&i+j<S;j++)c[i+j]+=a[i]*b[j];return c; } friend poly operator +(poly a,poly b){poly c;for(int i=0;i<S;i++)c[i]=a[i]+b[i];return c;} friend poly operator -(poly a,poly b){poly c;for(int i=0;i<S;i++)c[i]=a[i]-b[i];return c;} poly operator <<(const int& x){poly c;for(int i=S-1;i>=x;i--)c[i]=a[i-x];return c;} }a,b,c,q,fz,fm,fz1,fm1;int n; ll f0[N];ll c0[N];ll f1[N];ll c1[N];ll f2[N];ll c2[N];ll g[N];ll sqr[N]; inline void calc(poly& fz,poly& fm,ll* f,ll* c)//暴力除法 { for(int i=0;i<S;i++)f[i]=(mod+fz[i])%mod; for(int i=0;i<S;i++)c[i]=(mod-fm[i])%mod;(c[0]+=1)%=mod; for(int i=0;i<=n;i++) for(int j=1;j<S&&j<=i;j++)(f[i]+=f[i-j]*c[j])%=mod; } int main() { a[8]=16;a[6]=12;a[4]=20;a[2]=4;b[8]=9;b[6]=2;b[4]=23;b[2]=6;b[0]=1; c[8]=4;c[6]=-4;c[4]=24;c[2]=4;c[0]=4;q[12]=-1;q[10]=-3;q[6]=+5;q[2]=-3;q[0]=+1; scanf("%d",&n);//按照推出来的柿子计算f1,f2,f3 fz=((b*b)<<3)-a*((c<<3)-q);fm=((c<<3)-q)*((a<<1)-q)-((b*b)<<4);calc(fz,fm,f0,c0); fz=b*q;fm=((c<<3)-q)*((a<<1)-q)-((b*b)<<4);calc(fz,fm,f1,c1); fz1=c*fm+((b*fz)<<1);fm1=fm*(q-(c<<3));calc(fz1,fm1,f2,c2); g[0]=1;g[2]=1;for(int i=4;i<=n;i++)g[i]=(g[i-2]+g[i-4])%mod; for(int i=1;i<=n;i++)sqr[i]=(ll)i*i%mod; ll ans=(g[n-1]+g[n-3])*sqr[n-1]%mod*n%mod; for(int i=2;i<=n-2;i++) { ll ret=0;(ret+=g[i-1]*f0[n-i-1])%=mod;(ret+=g[i-2]*f1[n-i-2]*2)%=mod; if(3<=i&&i<=n-3)(ret+=g[i-3]*f2[n-i-3])%=mod; (ans+=ret*sqr[i-1]%mod*i)%=mod; }printf("%I64d",ans);//拜拜程序~ } ```