P1586 solution to tetragonal theorem

P1586 The square theorem

The question ： The question is very simple .

solution ： It is said that this question can be repeated in four cycles + Pruned , The time complexity has to be card by card , The exact solution is dp,dp Dafa is good , Consider with recursion ,dp[j][k] Express j use k The number of schemes represented by the square number , The transfer equation is $dp[j][k]=\sum dp[j-i\ast i][k-1]$, Positive order is also useful to the idea of complete knapsack , Pack nine ( Manual funny ).

Code ：

#include<bits/stdc++.h>
using namespace std;
const int N = 32768;
const int M = 4e4+10;
const int Mod = 1e9+7;
int dp[M][5];
int main() {
    
	int t, n;
	dp[0][0] = 1;
	for(int i = 1; i*i <= N; ++i) {
     // Enumeration square  
		for(int j = i*i; j <= N; ++j) {
     // Recurrence !!! 
			for(int k = 1; k <= 4; ++k) {
      // Indicates how many squares are selected  
				dp[j][k] += dp[j-i*i][k-1]; 
			}
		}
	}
	scanf("%d", &t);
	while(t--) {
    
		scanf("%d", &n);
		int ans = 0;
		for(int i = 1; i <= 4; ++i) {
    
			ans += dp[n][i];
		}
		printf("%d\n", ans);
	}
	return 0;
}