ICPC 2007 Regional Problem J

nobuに考えてもらったDPで__________案の解法を書いてみた。書いてわかったけど__________華麗すぎる。

#include <iostream>
#include <cassert>
#include <vector>
#include <complex>
#include <cmath>
using namespace std;

typedef complex<double> pt;
typedef vector<pt> sol_t;
const double PI = atan(1.)*4;

int main() {
  if (freopen("J.in", "r", stdin) == NULL) assert(false);
  int a,m,b,n;
  while (cin>>a>>m>>b>>n, a|m|b|n) {
    sol_t sa(m), sb(n);
    for (int i = 0; i < m; i++) {
      double val = pow((double)a,1./m);
      sa[i] = polar(val,i*2*PI/m);
    }
    for (int i = 0; i < n; i++) {
      double val = pow((double)b,1./n);
      sb[i] = polar(val,i*2*PI/n);
    }
    const int size = n*m;
    sol_t sol(size);
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        sol[i*n+j] = -sa[i] - sb[j];
    //for (int i = 0; i < size; i++) cout<<sol[i]<<" "; cout<<endl;
    sol_t tbl(size+1);
    tbl[0] = 1.;
    for (int i = 1; i <= size; i++)
      for (int k = i; k > 0; k--)
        tbl[k] += sol[i-1]*tbl[k-1];
    for (int i = 0; i <= size; i++) {
      if (i) cout<<" ";
      cout<<(int)floor(real(tbl[i])+1e-5);
    }
    cout<<endl;
  }
  return 0;
}

sampleは通ったけど本番データは誤差とかオーバーフローとかだいじょうぶかはわからない。
そもそも出力の仕方間違っていたｗスペース最後に含んじゃいけないのね。
さらに、誤差の問題で1e-5まではOKだけどそれよりも小さくするとだめなことがわかった。まぁこの場合0.5足しときゃ安心って話はあるけど、しっかり誤差が見積もれるようになりたいなぁ。