P1586 四方定理

Powered by:NEFU AB-IN

Link

P1586 四方定理

• 题意

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

• 思路

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

  由于所有数都可以使用无数次，所以采用完全背包的思想，可以理解为有1,2,3…等物品，体积为各自的平方，每个的价值都是一样的，背包体积为n，目的是问塞满背包的方案数
  得出dp方程 $dp[i][j]+=dp[i-k\ast 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 
  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;
  }
  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
  43
  44
  45