# 平方和球柱的容量：Karatsuba 精确平方

## 最大数量的证明

记 $C(n)=\lfloor(n+1)^2/2\rfloor-1$ .

**上界。** 设已经放入了 $T=C(n)+1=\lfloor(n+1)^2/2\rfloor$ 个球。考察最大的 $n+1$ 个编号，即 $T-n,\ldots,T$ .其中任意两个不同编号之和严格大于 $n^2$ 且严格小于 $(n+1)^2$ ，所以不能相邻。每根柱子的编号从底到顶严格递增，这些大编号在该柱上必然构成连续的顶端部分；若某柱有两个，就会有两个相邻的大编号，产生矛盾。因此需要至少 $n+1$ 根柱子，上界成立。

**达到上界的构造。** 一根柱子只放球一。对于奇数 $n>1$ ，在当前 $n$ 根柱子上放两层，从顶到底描述如下，局部列编号为 $j=0,\ldots,n-1$ ：

$$\text{上层}_j=C(n)-n+1+j,\qquad \text{下层}_j=C(n)-n-j.$$

再在中间 $n-2$ 根柱子的下方递归放入规模 $n-2$ 的方案。上下两层相邻和为 $n^2$ ；第二层与递归部分第一层的相邻和为 $(n-1)^2$ .剩余相邻关系由归纳保证。两层使用最大的 $2n$ 个编号，因为 $C(n)-C(n-2)=2n$ ，所有编号不重不漏。

对于偶数 $n$ ，最上层从左到右为 $C(n),C(n)-1,\ldots,C(n)-n+1$ ，前 $n-1$ 根柱子的下方放规模 $n-1$ 的方案。相接两层的编号和为 $n^2$ ，并且 $C(n)-C(n-1)=n$ .故也合法且恰好用尽一到 $C(n)$ .

所有列从顶到底严格递减，因此逆向按编号从小到大放入，正好遵守原操作时序。构造与上界合起来证明最优数量就是 $C(n)$ .

## 三次递归平方

将 $N+1$ 写成低位在前的万进制数字多项式，补零到二次幂长度。分成低半部分 $A$ 与高半部分 $B$ ，设半长为 $h$ ：

$$\left(A+x^hB\right)^2=A^2+x^h\left((A+B)^2-A^2-B^2\right)+x^{2h}B^2.$$

只递归计算 $A^2,B^2,(A+B)^2$ 三个平方，再线性合并。长度不超过三十二时，用普通乘法，利用平方的对称性将非对角项乘二。递归期间暂不进位；完整卷积算出后统一万进制进位，再除以二、减一，输出 $\lfloor(N+1)^2/2\rfloor-1$ .

## 正确性与数值安全

分治恒等式准确给出平方的低、中、高三段；归纳可知每次递归返回精确的卷积系数。进位不改变数字值，除二取整与减一计算容量公式，因此答案正确。

最多有 $25001$ 个万进制位，原始数字和不超过 $25001\times9999$ .每次把高低半部相加都保持总和，因此任意递归子问题的所有非负卷积系数总和不超过 $(25001\times9999)^2<2^{63}$ .中间的两项减法得到非负交叉项；所有被减部分及累计结果也在这个界内，所以标准有符号 64 位整数足够，无须扩展整数或浮点数。

## 复杂度与适用范围

若规范化数字长度为 $d$ ，递推为 $T(d)=3T(d/2)+O(d)$ ，故时间为 $O(d^{\log_2 3})$ ，同时存活的向量总大小构成几何级数，额外空间为 $O(d)$ .另计读入原始字符串的线性时间与空间；多组数据的时间求和，空间取最大值。

[alternative.cpp](alternative.cpp) 支持完整范围，独立于模数和单位根，展示纯整数分治乘法。首选[NTT 平方](solution.zh.md)具有更低的渐进时间。Karatsuba 是经典算法；GPT-6 提供本题的应用、64 位数值界、程序和验证。容量公式与构造证明来自出题人解法。两种大整数程序均与 Python 精确整数比较，见[测量记录](../../../docs/benchmark-R24.json)。