题解 P5377 【[THUPC2019]鸽鸽的分割】

· · 题解

警告：解法非常玄学，暴力

鉴于本蒟蒻实在太弱，跳出来的第一个想法只有找规律

tips:$为了描述方便，我们一下统称答案为$d

当n=1时，d=1

当n=2时，d=2

当n=3时，d=4

当n=4时，d=8

当n=5时，d=16

如果你单纯的认为d=2^{n-1}，那么你就错了。

当n=6时，d=31。

这就非常的让人头秃，我们找出规律，似乎变得没有办法了。

但是我在网上找到了一句话。

任何一个6项的数列，一定可以用一个不超过5次的式子表达出来

也就是用类似an^5+bn^4+cn^3+dn^2+en+f的数列表达出来

只要把a,b,c,d,e,f分别算出来就可以了。

代入本题中:

n=1$时，$d=1^5a+1^4b+1^3c+1^2d+1e+f=a+b+c+d+e+f=1 n=2$时，$d=2^5a+2^4b+2^3c+2^2d+2e+f=32a+16b+8c+4d+2e+f=2 n=3$时，$d=3^5a+3^4b+3^3c+3^2d+3e+f=243a+81b+27c+9d+3e+f=4 n=4$时，$d=4^5a+4^4b+4^3c+4^2d+4e+f=1024a+256b+64c+16d+4e+f=8 n=5$时，$d=5^5a+5^4b+5^3c+5^2d+5e+f=3125a+625b+125c+25d+5e+f=16 n=6$时，$d=6^5a+6^4b+6^3c+6^2d+6e+f=7776a+1296b+216c+36d+6e+f=31

可以解六元五次方程得，

a=0,b=\frac{1}{24},c=-\frac1 4,d=\frac {23} {24},e=-\frac34,f=1

代入，并变形可得式子

\frac{n^4-6n^3+23n^2-18n+24}{24}

程序就很简单了。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
        cout<<(n*n*n*n-6*n*n*n+23*n*n-18*n+24)/24<<endl;
    return 0;
}