P1586 四方定理

Powered by:NEFU AB-IN

Link

P1586 四方定理

• 题意

  四方定理是众所周知的：任意一个正整数n，可以分解为不超过四个整数的平方和
  给定的正整数n，编程统计它能分解的方案总数。

• 思路

  d p [ i ] [ j ] dp[i][j] dp[i][j]代表i可用j个平方数组成的方案数，所以最后输出 d p [ n ] [ 1 − 4 ] dp[n][1-4] dp[n][1−4]的和即可

  由于所有数都可以使用无数次，所以采用完全背包的思想，可以理解为有1,2,3…等物品，体积为各自的平方，每个的价值都是一样的，背包体积为n，目的是问塞满背包的方案数
  得出dp方程 d p [ i ] [ j ] + = d p [ i − k ∗ k ] [ j − 1 ] dp[i][j] += dp[i - k*k][j-1] dp[i][j]+=dp[i−k∗k][j−1]

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-09-10 12:05:40
  * @FilePath: \Contest\C\C.cpp
  * @LastEditTime: 2023-09-16 09:18:51
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int
  
  #define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int N = 1e5 + 10, INF = 0x3f3f3f3f;
  
  int dp[N][5];
  
  signed main()
  {
      // freopen("Tests/input_1.txt", "r", stdin);
      IOS;
      int n = 32768, t;
      dp[0][0] = 1;
      for (int i = 1; i * i <= n; i++)
          for (int j = i * i; j <= n; j++)
              for (int k = 1; k <= 4; k++)
                  dp[j][k] += dp[j - i * i][k - 1];
      cin >> t;
      while (t--)
      {
          int ans = 0;
          cin >> n;
          for (int i = 1; i <= 4; i++)
              ans += dp[n][i];
          cout << ans << '\n';
      }
      return 0;
  }