ACM 10326 Q10326: The Polynomial Equation
作法 : DP
利用 d311 "數學少女的難題" 所導出的遞迴式 做編修
算出根與係數
請不要暴力算出根與係數
以下作法 在DEV-C++編譯時,無法正確的顯示 (用INT 就OK)
/******************************************************/
#include<stdio.h>
#include<stdlib.h>
int n,m;
long long int w[101],value[101];
int recursion (int t)
{
int n,m;
long long int p[101][101]={0};
for(n=0;n<=t;n++)
{
p[n][0]=1;
for(m=1;m<=n;m++)
p[n][m]=p[n-1][m]+p[n-1][m-1]*value[n];
}
for(n=0;n<=t;n++)
w[n]=p[t][n];
}
main()
{
while(scanf("%d",&n)==1)
{
int a,b,c;
value[0]=1;
for(a=1;a<=n;a++)
{
scanf("%lld",&value[a]);
w[a]=0;
}
w[0]=0;
recursion(n);
if(n!=1)
printf("x^%d ",n);
else printf("x ");
for(a=1;a<=n-1;a++)
{
if(a%2==1) w[a]*=-1;
if(w[a]<0)
{
w[a]*=-1;
if(n-a!=1)
{
if(w[a]!=1)
printf("- %lldx^%d ",w[a],n-a);
else printf("- x^%d ",n-a);
}
else
{
if(w[a]!=1)
printf("- %lldx ",w[a]);
else printf("- x ");
}
}
else if(w[a]>0)
{
if(n-a!=1)
{
if(w[a]!=1)
printf("+ %lldx^%d ",w[a],n-a);
else printf("+ x^%d ",n-a);
}
else
{
if(w[a]!=1)
printf("+ %lldx ",w[a]);
else printf("+ x ");
}
}
}
if(n%2==1) w[n]*=-1;
if(w[n]>=0)
printf("+ %lld ",w[n]);
else
{
w[n]*=-1;
printf("- %lld ",w[n]);
}
printf("= 0\n");
}
return 0;
}