1241: Lagrange's Four-Square Theorem

ラグランジュの四乗定理なんて初めて聞いた。。。
2^15より小さくて四乗未満だから動的計画法でなんとかなりそうと思って適当に漸化式作ってみる
ans[i][j]と置いてiは入力した求めたい合計の値、jは2乗の何個の和であるか（0<=i<=2^15,0<=j<=4)
2乗の値はあらかじめ2^15までで計算しておき、dataという配列に入れている
あとはfor文を適当に回したらでる（ここの説明が難しい）

REP(i,data.size()){
    REP(j,32769){
        if(j+data[i]>32768)break;
        REP(k,4)ans[j+data[i]][k+1]+=ans[j][k];
    }
}

動的計画法の中身はこんな感じ
後はデータの数からあらかじめ計算してって感じ

int ans[32769][5];
int main(){
    vector<int>data;
    for(int i=1;i*i<=32768;i++)data.push_back(i*i);
    ans[0][0]=1;
    REP(i,data.size()){
        REP(j,32769){
            if(j+data[i]>32768)break;
            REP(k,4)ans[j+data[i]][k+1]+=ans[j][k];
        }
    }
    int n;
    while(1){
        cin>>n;
        if(n==0)break;
        int sum=0;
        REP(i,4)sum+=ans[n][i+1];
        cout<<sum<<endl;
    }
}