/* graphpol.h : Polynomial Routines for Graph Theory
K.Shiota
2005.6.12
*/

#ifndef POLSIZE
#define POLSIZE 256
#endif

typedef struct { int deg,cft[POLSIZE]; } POL;
static POL polzero = {-1,{0}};
static POL polone = {0,{1}};

/* 多項式の次数を正しく計算しなおす */
void truedeg(POL *f)
{
	int d=f->deg;
	while((f->cft[d]==0)&&(d>=0)) d--;
	f->deg=d;
}

/* X^d を返す */
POL monomial(int d)
{
	POL h;
	int i;

	for(i=0; i<d; i++) h.cft[i]=0;
	h.cft[d]=1;
	h.deg=d;
	return h;
}

/* 定数式 a を返す */
POL constpol(int a)
{
	POL h;
	if(a==0) return polzero;
	else{
		h.deg=0;
		h.cft[0]=a;
		return h;
	}
}

/* 一次因子 X-a を返す */
POL linearfactor(int a)
{
	POL h;
	h.deg=1;
	h.cft[1]=1;
	h.cft[0]=-a;
	return h;
}

/* 標準入力から多項式を読み込む */
POL polscan()
{
	POL h;
	int d,i,x;

	scanf("%d",&d);
	h.deg=d;
	for(i=d;i>=0;i--){
		scanf("%d",&x);
		h.cft[i]=x;
	}
	truedeg(&h);
	return h;
}

/* 標準入力から対話形式で多項式を読み込む */
POL polinput()
{
	POL h;
	int d,i,x;

	printf("deg = ");
	scanf("%d",&d);
	h.deg=d;
	for(i=d;i>=0;i--){
		printf("%d-th coefficient = ",i);
		scanf("%d",&x);
		h.cft[i]=x;
	}
	truedeg(&h);
	return h;
}

/* ファイルに多項式を出力する, 変数は c */
void fpolwritechar(FILE *fo, POL f, char c)
{
	int i,x,d=f.deg;

	if(d==-1){
		fprintf(fo,"0");
		return;
	}
	for(i=d;i>=0;i--){
		x=f.cft[i];
		if(x!=0){
			if(i<d) fprintf(fo," ");
			if(x<0){
				fprintf(fo,"- ");
				x=-x;
			}
			else{
				if(i<d) fprintf(fo,"+ ");
			}
			if(i==0){
				fprintf(fo,"%d",x);
			}
			else{
				if(x!=1) fprintf(fo,"%d ",x);
				fprintf(fo,"%c",c);
				if(i>1) fprintf(fo,"^%d",i);
			}
		}
	}
}

/* ファイルに多項式を出力する（改行つき）, 変数は c */
void fpolwritecharln(FILE *fo, POL f, char c)
{
	fpolwritechar(fo, f,c);
	fprintf(fo,"＼n");
}

/* ファイルに多項式を出力する, 変数は 'X' */
void fpolwrite(FILE *fo, POL f)
{
	fpolwritechar(fo,f,'X');
}

/* ファイルに多項式を出力する（改行つき）, 変数は 'X' */
void fpolwriteln(FILE *fo, POL f)
{
	fpolwrite(fo,f);
	fprintf(fo,"＼n");
}

/* 画面に多項式を出力する, 変数は c */
void polwritechar(POL f, char c)
{
	fpolwritechar(stdout,f,c);
}

/* 画面に多項式を出力する（改行つき）, 変数は c */
void polwritecharln(POL f, char c)
{
	fpolwritecharln(stdout,f,c);
}

/* 画面に多項式を出力する, 変数は 'X' */
void polwrite(POL f)
{
	polwritechar(f,'X');
}

/* 画面に多項式を出力する（改行つき）, 変数は 'X' */
void polwriteln(POL f)
{
	polwrite(f);
	printf("＼n");
}

/* f がゼロ多項式か否か判定する */
int polzeroq(POL f)
{
	if(f.deg==-1) return 1; else return 0;
}

/* f が定数式 1 か否か判定する */
int poloneq(POL f)
{
	if((f.deg==0)&&(f.cft[0]==1)) return 1; else return 0;
}

/* ふたつの多項式 f と g が等しいか否か判定する */
int polsameq(POL f, POL g)
{
	int i,d=f.deg;
	if(d!=g.deg) return 0;
	for(i=d; i>=0; i--) if(f.cft[i]!=g.cft[i]) return 0;
	return 1;
}

/* 多項式 f の定数 c 倍を返す */
POL poltimes(int c, POL f)
{
	int i;
	POL h;

	if(c==0) h=polzero;
	else{
		h.deg=f.deg;
		for(i=0; i<=h.deg; i++) h.cft[i]=c*f.cft[i];
	}
	return h;
}

/* 多項式 f の最高次の係数を返す */
int leadingcft(POL f)
{
	if(polzeroq(f)) return 0;
	else return f.cft[f.deg];
}

/* 多項式 f がモニックであるか否か判定する */
int monicq(POL f)
{
	if(polzeroq(f)) return 0;
	if(f.cft[f.deg]==1) return 1; else return 0;
}

/* 多項式 f の定数項を返す */
int constantterm(POL f)
{
	if(polzeroq(f)) return 0;
	else return f.cft[0];
}

/* ふたつの多項式 f と g の和を返す */
POL poladd(POL f, POL g)
{
	int i;
	POL h;

	if(f.deg>g.deg){
		for(i=0; i<=g.deg; i++) h.cft[i]=f.cft[i]+g.cft[i];
		for(i=g.deg+1; i<=f.deg; i++) h.cft[i]=f.cft[i];
		h.deg=f.deg;
	}
	else{
		for(i=0; i<=f.deg; i++) h.cft[i]=f.cft[i]+g.cft[i];
		for(i=f.deg+1; i<=g.deg; i++) h.cft[i]=g.cft[i];
		h.deg=g.deg;
		if(f.deg==g.deg) truedeg(&h);
	}
	return h;
}

/* ふたつの多項式 f と g の差を返す */
POL polsub(POL f, POL g)
{
	int i;
	POL h;

	if(f.deg>g.deg){
		for(i=0; i<=g.deg; i++) h.cft[i]=f.cft[i]-g.cft[i];
		for(i=g.deg+1; i<=f.deg; i++) h.cft[i]=f.cft[i];
		h.deg=f.deg;
	}
	else{
		for(i=0; i<=f.deg; i++) h.cft[i]=f.cft[i]-g.cft[i];
		for(i=f.deg+1; i<=g.deg; i++) h.cft[i]=-g.cft[i];
		h.deg=g.deg;
		if(f.deg==g.deg) truedeg(&h);
	}
	return h;
}

/* ふたつの多項式 f と g の積を返す */
POL polmul(POL f, POL g)
{
	int i,j,d,c;
	POL h;

	if(polzeroq(f)||polzeroq(g)){
		h=polzero;
	}
	else{
		d=f.deg+g.deg;
		h.deg=d;
		for(i=0; i<=d; i++) h.cft[i]=0;
		for(i=0; i<=f.deg; i++){
			c=f.cft[i];
			for(j=0; j<=g.deg; j++) h.cft[i+j]+=c*g.cft[j];
		}
	}
	return h;
}

/* ふたつの多項式 f を g で割った商を返す, 余りは *r */
POL poldiv(POL f, POL g, POL *r)
{
	int j,d,e,c;
	POL h=polzero;
	*r=f;
	if(polzeroq(g)){
		printf("division by zero polynomial＼n");
		exit(1);
	}
	if(g.cft[g.deg]!=1){
		printf("division by non-monic polynomial＼n");
		exit(1);
	}
	if(f.deg<g.deg){
		h.deg=-1;
		*r=f;
		return h;
	}

	h.deg=f.deg-g.deg;
	d=g.deg;
	while(r->deg>=d){
		e=r->deg-d;
		c=r->cft[r->deg];
		h.cft[e]=c;
		if(c!=0){
			r->cft[r->deg]=0;
			for(j=0; j<d; j++) r->cft[j+e]-=c*g.cft[j];
		}
		truedeg(r);
	}
	return h;
}

/* 多項式 f を 定数 c で割った商を返す（余りは無視する） */
POL poldivint(int c, POL f)
{
	int i;
	POL h;

	if(c==0){
		printf("division by 0＼n");
		exit(1);
	}
	else{
		h.deg=f.deg;
		for(i=0; i<=h.deg; i++) h.cft[i]=f.cft[i]/c;
	}
	truedeg(&h);
	return h;
}

/* 多項式 f の a での値を返す */
int poleval(POL f, int a)
{
	int i,x=0;
	for(i=f.deg;i>=0;i--) x=(x*a)+f.cft[i];
	return x;
}