GDKOI 2024 鸡题解

Rainbow_qwq · 2024-01-20 19:53:50 · 题解

通过找规律，发现 f(n,m) 满足如下关系式：

f(2,m)=(m+1)^2

f(3,m)=\frac{1}{3}m^3+2m^2+\frac{8}{3}m+1

f(4,m)=\frac{7}{3}m^3+5m^2+\frac{11}{3}m+1

f(5,m)=\frac{7}{12}m^4 + \frac{17}{3}m^3+\frac{89}{12} m^2+\frac{13}{3}m+1

f(6,m)=\frac{25}{6}m^4 + \frac{38}{3}m^3+\frac{71}{6} m^2+\frac{16}{3}m+1

f(7,m)=\frac{5}{6}m^5 + \frac{37}{3}m^4 + \frac{133}{6}m^3+\frac{47}{3} m^2+6m+1

f(n,m) = 2f(n-1,m)+2m\cdot f(n-2,m)-(2m+2)f(n-3,m)-(m^2+2m-1)f(n-4,m)+2m\cdot f(n-5,m)+m^2f(n-6,m)

据此计算即可。时间复杂度 O(n)，可以优化到 O(\log n)。

核心代码：

int n;
modint m;
modint f[maxn];

signed main()
{
    n=read(),m=read(),initmod();
    f[2]=(m+1)*(m+1);
    f[3]=m*m*m/3+m*m*2+m*8/3+1;
    f[4]=m*m*m*7/3+m*m*5+m*11/3+1;
    f[5]=m*m*m*m*7/12+m*m*m*17/3+m*m*89/12+m*13/3+1;
    f[6]=m*m*m*m*25/6+m*m*m*38/3+m*m*71/6+m*16/3+1;
    f[7]=m*m*m*m*m*5/6+m*m*m*m*37/3+m*m*m*133/6+m*m*47/3+m*6+1;
    For(i,8,n)f[i]=f[i-1]*2+f[i-2]*2*m+f[i-3]*((-m)*2-2)+f[i-4]*((-m)*m-m*2+1)+f[i-5]*m*2+f[i-6]*m*m;
    cout<<f[n].x;
    return 0;
}

我们不加证明地猜测两个结论：

当 n 固定时，答案是一个关于 m 的多项式。
当 m 固定时，答案序列 f_n 存在一个较短的递推式。

首先写一个快一点的指数级暴力，比如对每种差分数组算上下界然后加起来，可以跑出 n\le 13,0\le m\le 3 的结果。

据此可以 BM 求出 1\le m\le 3 的所有递推式，发现第二条结论是正确的，而且递推式长度仅为 6：

m=1$：$(2,2,-4,-2,2,1)
m=2$：$(2,4,-6,-7,4,4)
m=3$：$(2,6,-8,-14,6,9)

容易~~找规律~~观察出递推式为 (2,2m,-(2m+2),-((m+1)^2-2),2m,m^2)。

那现在问题在于固定 m 求出 f(2\sim 7,m) 的值，之后可以使用递推式。

由于第一条结论，可以暴力跑出 n,m\le 8 的答案，然后插值求出 n=2\sim 7 时 m 满足的多项式。

GDKOI 2024 鸡 题解

GDKOI 2024 鸡题解