[ACM-ICPC Asia Beijing Regional Contest 2018 Reproduction problem] [JZOJ100148] 胖头鱼与方程【数学】【牛顿恒等式】

Description

以下为魔改版题面

n, m ≥ 1, n ≤ 6, n+m ≤ 10, |ai| ≤ 120
保证|bi| < 10^12

Solution

首先，此题的关键是一个叫牛顿恒等式的东西。

考虑多项式$F(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$F(x)=an​xn+an−1​xn−1+⋯+a1​x+a0​
令其所有根为$x_1,x_2,...,x_n$x1​,x2​,...,xn​
设$b_i=a_{n-i}$bi​=an−i​（反位），$S_k=\sum\limits_{i=1}^{n}x_i^k$Sk​=i=1∑n​xik​

恒有
$\sum\limits_{i=1}^{k}S_ib_{k-i}+k\times b_k=0,k\in \N^*$i=1∑k​Si​bk−i​+k×bk​=0,k∈N∗

证明就不说了，网上有不少的论文有讲。

有了这个式子，就意味着我们只要求出了多项式的每一项，就可以递推出它的所有根的次幂和。
有了根的次幂和，也可以递推出多项式的每一项。

那么先求出原多项式的$1$1到$n*m$n∗m次幂，递推回新多项式的时候只需把$S_i$Si​改成$S_{i*m}$Si∗m​即可。

由于原题保证了不会爆long long
实测过程中次幂和也不会爆long long 。。。

Code

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define LL long long
#define N 150
using namespace std;
LL s[N],a[N],b[N]; 
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	while(n!=0||m!=0)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		fo(i,0,n-1) scanf("%lld",&a[n-i]);
		a[0]=1;
		memset(s,0,sizeof(s));
		fo(i,1,m*n)
		{
			s[i]=-(LL)i*a[i];
			fo(j,1,i-1) s[i]-=s[j]*a[i-j];
		}
		b[0]=1;
		fo(i,1,n)
		{
			fo(j,1,i) b[i]-=s[j*m]*b[i-j];
			b[i]/=i;
		}
		fod(i,n,1) printf("%lld ",b[i]);
		printf("\n");
		scanf("%d%d",&n,&m);	
	}
}