結果

問題 No.265 数学のテスト
コンテスト
ユーザー kyuridenamida
提出日時 2015-08-07 22:46:35
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 1,570 bytes
コンパイル時間 1,362 ms
コンパイル使用メモリ 165,392 KB
実行使用メモリ 9,984 KB
最終ジャッジ日時 2024-11-24 11:17:11
合計ジャッジ時間 2,388 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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];
	}
	res.resize(d+1);
	return res;
}


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