### 题解 CF848E 【Days of Floral Colours】

posted on 2019-02-28 22:02:37 | under 题解 |

# 本题题解

1.每个点的度数恰好是1

2.有边的点之间的距离要么小于等于2要么恰好是n

3.如果$(i,j)$有边，那么在$(i,j)$正对面的点$(i',j')$也必须有边

4.至少有一对点距离为n并且有边相连

## 从一个naive的$O(n^2)$dp开始

$$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)=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)$$

$$(g(n-1)+g(n-3))^(n-1)^2$$

$$\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))$$

(如果直接写“自己卷自己”形式的分治fft优化上述的dp我们将会得到一个优秀的$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$$

$$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}$$

## 生成函数的求导

$$g(n)=g(n-2)+g(n-4),g(0)=1,g(1)=0$$

$$G(z)=\frac{1}{1-z^{2}-z^{4}}$$

$$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)$$

$$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$$

$$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}(z)=\frac{N(z)P_{2}(z)+P_{1}(z)M(z)z}{N(z)(Q(z)-P_{2}(z)z^3)}$$

$$F(x)=\frac{P(x)}{1-C(x)}$$

$$F(x)(1-C(x))=P(x)$$

$$F(x)=F(x)C(x)+P(x)$$

#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);//拜拜程序~
}