P1586 四方定理-完全背包(dp)

四方定理

题目描述

四方定理是众所周知的：任意一个正整数$n$，可以分解为不超过四个整数的平方和。例如：$25=1^2+2^2+2^2+4^2$，当然还有其他的分解方案，$25=4^2+3^2$和$25=5^2$。给定的正整数$n$，编程统计它能分解的方案总数。注意：$25=4^2+3^2$和$25=3^2+4^2$视为一种方案。

输入格式

第一行为正整数$t$($t\le 100$)，接下来$t$行，每行一个正整数$n$($n\le 32768$)。

输出格式

对于每个正整数$n$，输出方案总数。

样例 #1

样例输入 #1

1
2003
1
2

样例输出 #1

48
1

#include 
using namespace std;
#define sf(x) scanf("%d",&x);
#define de(x) cout<<x<<" ";
#define Pu puts("");
typedef long long ll;
const int N=4e4+10;
int n,m,ans;
// ll a[N];
int f[N][5];
void init(){
    // int t=x/2;
    // for(int i=1;i<=t;i++){
    //     if(i*i==x) a[x]+=a[i];
    //     else a[x]+=a[i]*a[x-i];
    // }
    for(int i=1;i<=N;i++){
        for(int j=i*i;j<=N;j++){
            for(int k=1;k<=4;k++){
                f[j][k]+=f[j-i*i][k-1];
            }
        }
    }

}
int main(){
    int T;cin>>T;
    // a[1]=a[2]=a[3]=1;
    // for(int i=4;i<=N;i++){
    //     init(i);
    // }
    f[0][0]=1;
    init();
    while(T--){
        sf(n)
        ans=0;
        for(int i=1;i<=4;i++){
            ans+=f[n][i];
        }
        printf("%d\n",ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42