P1586 四方定理【洛谷算法习题】

P1586 四方定理

网页链接

P1586 四方定理

题目描述

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

1 2003

输出 #1

48

解题思路

本题是完全背包求组合数的经典模型，需要统计正整数n nn分解为不超过四个平方数之和的方案数（顺序不同视为同一种）。采用二维 DP，预处理所有n nn的答案后O ( 1 ) O(1)O(1)查询。

1. 问题等价转化

• 平方数集合：1 2 , 2 2 , 3 2 , … 1^2,2^2,3^2,\ldots12,22,32,…每个平方数可重复使用。
• 目标：对于每个n nn，求用1 ∼ 4 1\sim41∼4个平方数（可以相同）组成n nn的不同组合数，顺序无关。
• 顺序无关的组合计数适合用完全背包的升序物品遍历方式实现。

2. DP 状态设计

• dp[j][s]表示用恰好s ss个平方数（允许重复）组成和为j jj的方案数。
• 初始化：dp[0][0] = 1，表示空选组成0 00。
• 转移：枚举平方数i 2 i^2i2，按i ii从1 11到M X \sqrt{MX}MX​依次作为物品，内层枚举容量j jj从i 2 i^2i2到M X MXMX，再用层数s = 1 ∼ 4 s=1\sim4s=1∼4更新：
  d p [ j ] [ s ] + = d p [ j − i 2 ] [ s − 1 ] dp[j][s] \mathrel{+}= dp[j-i^2][s-1]dp[j][s]+=dp[j−i2][s−1]
  由于外层固定物品顺序，内层正序更新容量，天然保证组合中平方数按非递减顺序选择，从而避免重复计数。

3. 答案计算

• 预处理后，对于每个询问n nn，答案为∑ s = 1 4 d p [ n ] [ s ] \sum_{s=1}^{4} dp[n][s]∑s=14​dp[n][s]。
• 注意题目要求“不超过四个”，所以包含 1 个、2 个、3 个、4 个平方数的情况。

4. 复杂度分析

• 预处理：外层O ( M X ) ≈ 181 O(\sqrt{MX}) \approx 181O(MX​)≈181，每个物品遍历O ( M X ) O(MX)O(MX)，再乘层数O ( 4 ) O(4)O(4)，总操作量约181 × 32768 × 4 ≈ 2.4 × 10 7 181 \times 32768 \times 4 \approx 2.4\times 10^7181×32768×4≈2.4×107，在 1 秒内可行。
• 空间：O ( M X × 5 ) O(MX \times 5)O(MX×5)，极小。

总结

利用完全背包的组合计数思想，外层固定平方数大小，内层正序更新容量和数量，即可得到无序分解方案数。预处理好后，每组询问直接求和即可。

代码简要说明

1. DP 数组：dp[33000][5]初始化为{1}，即dp[0][0]=1。
2. 三重循环：先枚举平方数i*i，再枚举容量j，最后枚举数量s=1..4，进行方案累加。
3. 查询：读入n nn，累加dp[n][1]到dp[n][4]输出。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll SZ=33000;ll dp[SZ][5]={1};intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cin>>t;constll MX=32768;for(ll i=1;i*i<=MX;i++)for(ll j=i*i;j<=MX;j++)for(ll s=1;s<=4;s++)dp[j][s]+=dp[j-i*i][s-1];while(t--){ll n,ans=0;cin>>n;for(ll i=1;i<=4;i++)ans+=dp[n][i];cout<<ans<<'\n';}return0;}