結果

問題 No.265 数学のテスト
コンテスト
ユーザー kyuridenamida
提出日時 2015-08-07 22:44:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,280 bytes
コンパイル時間 1,685 ms
コンパイル使用メモリ 172,656 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2024-07-18 05:12:13
合計ジャッジ時間 5,476 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 2
other AC * 8 WA * 6 RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
int d;
const double eps = 1e-9;
// 多項式　たとえば　y=x^3 + -3x +5 なら y=[5,-3,0,1] みたいな表現
typedef vector<double> Poly;

// 無駄な係数0の高次項を消す
Poly normalize(Poly p){
	while( p.size() && p.back() == 0 ) p.pop_back();
	p.resize(d+1);
	return p;
}
//多項式の微分
Poly dfdx(Poly p){
	Poly res;
	if( p.size() != 0 ){
		res.resize(p.size()-1);
		for(int i = 0 ; i < res.size() ; i++)
			res[i] = (i+1) * p[i+1];
	}
	return res;
}
//多項式の割り算 res.first に商 res.second に余り
pair<Poly,Poly> pDiv(Poly f,Poly g){
	f = normalize(f);
	g = normalize(g);
	
	if( g.size() == 0 ) assert( "申し訳ないが0割りはNG" == "" );
	
	int m = max(f.size(),g.size());
	Poly p(m);
	while( f.size() >= g.size() ){
		int deg = f.size() - g.size();
		double coef = f.back() / g.back();
		p[deg] = coef;
		for(int i = 0 ; i < g.size() ; i++)
			f[i+deg] -= coef * g[i];
		f = normalize(f);
	}
	return {normalize(p),normalize(f)};
}

//多項式の計算
double calc(const Poly &p,double x){
	double ans = 0;
	for(int i = 0 ; i < p.size() ; i++)
		ans += p[i] * pow(x,i);
	return ans;
}

//多項式の表示(とりあえずできるだけ自然な表現になるようにしてる
void view(Poly p){
	p = normalize(p);
	if( p.size() == 0 ){
		cout << 0 << endl;
		return;
	}
	int fst = 0;
	for(int i = p.size()-1 ; i >= 0 ; i--){
		if( p[i] == 0 ) continue;
		if( fst++ && p[i] > 0 ) cout << "+";
		if( i != 0 && p[i] == 1 )cout << "";
		else if( i != 0 && p[i] == -1 )cout << "-";	
		else printf("%lf",p[i]);
		if( i >= 2 ) cout << "x^" << i;
		else if( i == 1 ) cout << "x";
	}
	cout << endl;
}

//すつるむ列を1つもってくる
vector<Poly> getSturm(Poly f){
	vector<Poly> fs(2);
	fs[0] = normalize(f);
	fs[1] = normalize(dfdx(f));	
	for(int i = 1 ; ; i++){
		if( fs[i].size() > 1){
			Poly remain = pDiv(fs[i-1],fs[i]).second;
			for( auto &x : remain ) x = -x;
			fs.push_back(normalize(remain));
		}else break;
	}
	if( fs.back().size() == 0 ){
		//　定数が0になっちゃうなら，多分重根の解となる式？を使って次数を下げる問題に帰着させる
		return getSturm(pDiv(f,fs[fs.size()-2]).first);
	}
	return fs;
}


string s;
int p;

Poly operator + (Poly a,Poly b){
	for(int i = 0 ; i < b.size() ; i++) a[i] += b[i];
	return a;
}
Poly operator * (Poly a,Poly b){
	Poly c(d+1);
	for(int i = 0 ; i < a.size() ; i++){
		for(int j = 0 ; j < b.size() ; j++){
			if( i + j < c.size() )
				c[i+j] += a[i]*b[j];		
		}
	}
	return c;
}

Poly f();
Poly g();
Poly h();

Poly f(){
	Poly r = g();
	
	while( s[p] == '+' ){
		p++;
		r = r + g();
	}
	return r;
}
Poly g(){
	Poly r = h();
	while( s[p] == '*' ){
		p++;
		Poly t = h();
		r = r * t;
	}
	return r;
}

Poly h(){
	if( s[p] == 'd' ){
		p += 2;
		Poly r = f();
		p++;
		return dfdx(r);
	}else{
		if( s[p] == 'x' ){
			Poly r(d+1);
			r[1] = 1;
			p++;
			return r;
		}else{
			double ans = 0;
			while( '0' <= s[p] && s[p] <= '9' ) 
				ans = ans * 10 + s[p++] - '0';
			Poly r = Poly(d+1);
			r[0] = ans;
			return r;
		}
	}
}
int main(){
	int N;
	
	cin >> N;
	cin >> d;
	cin >> s;
	p = 0;
	Poly r = f();
	for(int i = 0 ; i < r.size() ; i++)
		cout << (long long)r[i] << (i+1==r.size()?"\n":" ");
	
}
0