hdoj-1398-Square Coins

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int _max = 350;
int c1[_max], c2[_max];//c1[i]:当前多项式x^i的系数
vector<int> v;//cnt[i]:第i个字母的个数 v[i]:第i个字母的权值
//输出价值为t(指数)的组成方法个数(系数)
int main() {
    int t, i, j, k;
    for (int l = 1; l <= 17; ++l) {
        v.push_back(l * l);
    }
    while (cin >> t) {
        if (t == 0)
            break;
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));
        for (int i = 0; i <= t; i += v[0]) c1[i] = 1;
        for (i = 1; i < 17; ++i) {//第i个表达式
            for (j = 0; j <= t; ++j) {//我们只关心c1和c2运算结果指数<=t的
                for (k = 0; k + j <= t; k += v[i])//k是c2的指数
                    c2[k + j] += c1[j];//c1里的第j个元素与c2里指数为k的元素运算
            }
            for (j = 0; j <= t; ++j) {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        int res = 0;
        cout<<c1[t]<<endl;
    }
    return 0;
}