P1586 四方定理网页链接P1586 四方定理题目描述四方定理是众所周知的任意一个正整数n nn可以分解为不超过四个整数的平方和。例如25 1 2 2 2 2 2 4 2 251^{2}2^{2}2^{2}4^{2}2512222242当然还有其他的分解方案25 4 2 3 2 254^{2}3^{2}254232和25 5 2 255^{2}2552。给定的正整数n nn编程统计它能分解的方案总数。注意25 4 2 3 2 254^{2}3^{2}254232和25 3 2 4 2 253^{2}4^{2}253242视为一种方案。输入格式第一行为正整数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输入 #11 2003输出 #148解题思路本题是完全背包求组合数的经典模型需要统计正整数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 s1\sim4s1∼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_{s1}^{4} dp[n][s]∑s14​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)极小。总结利用完全背包的组合计数思想外层固定平方数大小内层正序更新容量和数量即可得到无序分解方案数。预处理好后每组询问直接求和即可。代码简要说明DP 数组dp[33000][5]初始化为{1}即dp[0][0]1。三重循环先枚举平方数i*i再枚举容量j最后枚举数量s1..4进行方案累加。查询读入n nn累加dp[n][1]到dp[n][4]输出。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll SZ33000;ll dp[SZ][5]{1};intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cint;constll MX32768;for(ll i1;i*iMX;i)for(ll ji*i;jMX;j)for(ll s1;s4;s)dp[j][s]dp[j-i*i][s-1];while(t--){ll n,ans0;cinn;for(ll i1;i4;i)ansdp[n][i];coutans\n;}return0;}