HDU1398 Square Coins

Problem Description

People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17^2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.
There are four combinations of coins to pay ten credits:

ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.

Your mission is to count the number of ways to pay a given amount using coins of Silverland.

Input

The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.

Output

For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.

Sample Input

Sample Output

1
4
27

Source

Asia 1999, Kyoto (Japan)

对于这道题，不难发现我们可以构造一个多项式。对于每一项k[i]x^i，系数k[i]表示面值为i有多少种方案。不难发现，两个这样的多项式相乘的新多项式表示了原来两种取值方案下组合的方案数（因为多项式乘法相当于对于新多项式的每一项i，对于原来两个多项式的两个位置a，b，求出了所有a+b=i时的k[a]*k[b]的和，相当于对每一个i的所有情况做了乘法原理把各个情况之间再做加法原理）。

对于只有每种平方硬币的时候，所得多项式上币值的倍数次项的系数为1（表示枚举这个面值取得个数，每种个数只有一种方案）。我们把这些多项式乘出来就是答案了。（为了练习NTT本题的多项式乘法为快速数论变换NTT）

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<complex>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 256 << 2;
const int P = 998244353, G = 3;
int N, n, m, mx2p, R[maxn << 1], p[maxn << 1], ans[maxn << 1], inv;

void init(int n) {
    for(N = 1; N <= n; N <<= 1) ++mx2p;
    for(register int i = 0; i < N; ++i)
        R[i] = (R[i >> 1] >> 1) | ((i & 1) << mx2p - 1);
}

LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % P;
        b >>= 1, a = a * a % P;
    }
    return ans;
}

void NTT(int * a, int type) {
    for(register int i = 0; i < N; ++i) if(i < R[i]) swap(a[i], a[R[i]]);
    for(register int i = 1; i < N; i <<= 1) {
        int Wn = fpow(G, (P - 1) / (i << 1));
        if(type == -1) Wn = fpow(Wn, P - 2);
        for(register int j = 0, p = i << 1; j < N; j += p) {
            int w = 1;
            for(register int k = 0; k < i; ++k, w = 1LL * w * Wn % P) {
                int x = a[j + k], y = 1LL * a[j + k + i] * w % P;
                a[j + k] = ((x + y) % P + P) % P;
                a[j + k + i] = ((x - y) % P + P) % P;
            }
        }
    }
}

int main() {
    n = 300, init(n << 1);
    for(register int i = 0; i <= n; ++i) ans[i] = 1;
    inv = fpow(N, P - 2);
    for(register int i = 2; i <= sqrt(n); ++i) {
        memset(p, 0, sizeof(p));
        for(register int j = 0; j <= n; j += i * i)
            p[j] = 1;
        NTT(p, 1), NTT(ans, 1);
        for(register int j = 0; j <= N; ++j)
            ans[j] = 1LL * ans[j] * p[j] % P;
        NTT(ans, -1);
        for(register int j = 0; j <= n; ++j)
            ans[j] = 1LL * ans[j] * inv % P;
        for(register int j = n + 1; j <= N; ++j)
            ans[j] = 0;
    }
    while(scanf("%d", &n) && n != 0) {
        printf("%d\n", ans[n]);
    }
    return 0;
}

当然，这么大好机会，怎么能不打个表呢？？

#include<cstdio>
using namespace std;

int n, ans[] = {0, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6, 6, 8, 9, 10, 10, 12, 13, 14, 14, 16, 19, 20, 21, 23, 26, 27, 28, 31, 34, 37, 38, 43, 46, 49, 50, 55, 60, 63, 66, 71, 78, 81, 84, 90, 98, 104, 107, 116, 124, 132, 135, 144, 154, 163, 169, 178, 192, 201, 209, 220, 235, 247, 256, 271, 286, 302, 311, 329, 347, 365, 378, 397, 420, 438, 455, 476, 504, 526, 545, 571, 601, 629, 648, 679, 713, 747, 771, 804, 844, 880, 910, 945, 993, 1035, 1072, 1116, 1167, 1216, 1255, 1306, 1361, 1420, 1466, 1525, 1590, 1653, 1707, 1770, 1846, 1916, 1981, 2055, 2141, 2222, 2291, 2374, 2468, 2563, 2641, 2737, 2846, 2952, 3042, 3145, 3267, 3385, 3491, 3607, 3745, 3880, 3998, 4130, 4279, 4431, 4564, 4714, 4880, 5050, 5201, 5368, 5555, 5742, 5914, 6101, 6312, 6521, 6712, 6921, 7155, 7389, 7601, 7834, 8094, 8355, 8591, 8849, 9139, 9431, 9697, 9984, 10304, 10628, 10923, 11238, 11592, 11953, 12285, 12637, 13027, 13424, 13793, 14180, 14607, 15048, 15460, 15895, 16368, 16853, 17305, 17782, 18303, 18835, 19339, 19867, 20447, 21031, 21585, 22161, 22795, 23441, 24051, 24694, 25392, 26109, 26778, 27482, 28241, 29025, 29766, 30535, 31376, 32235, 33055, 33896, 34812, 35750, 36651, 37581, 38578, 39614, 40598, 41621, 42707, 43835, 44914, 46030, 47228, 48452, 49641, 50856, 52170, 53503, 54801, 56133, 57560, 59027, 60434, 61894, 63443, 65049, 66585, 68174, 69865, 71604, 73290, 75005, 76852, 78741, 80589, 82465, 84468, 86529, 88530, 90578, 92737, 94987, 97162, 99397, 101749, 104180, 106551, 108963, 111524, 114146, 116735, 119360, 122146, 124997, 127792, 130643, 133641, 136742, 139761, 142864, 146119, 149482, 152762, 156106, 159629, 163250, 166821, 170432, 174255, 178180, 182046, 185960, 190071, 194315, 198484, 202729, 207163, 211756, 216269, 220852, 225644, 230580, 235465, 240408, 245594, 250916, 256195, 261537, 267123, 272865, 278544, 284316};

int main() {
    while(scanf("%d", &n)) {
        if(n == 0) break;
        printf("%d\n", ans[n]);
    }
    return 0;
}

Rockdu's Blog