[算法]拳皇友谊赛

这两天看到的一道蛮好玩的题：
变态的比赛规则：为了促进各部门员工的交流，百度(baidu)举办了一场全公司范围内的"拳皇友谊赛"，负责组织这场比赛的是百度的超级"拳皇"迷W.Z. W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。

由于一些员工（比如同部门或者相临部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自己组成不同组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人则之间不会打任何比赛。

比如4个人，编号为1--4,如果分为两个组并且1,2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3,1 vs 4,2 vs 3,2 vs 4. 而如果是1,2,3一组，4单独一组，那么一共需要打三场比赛: 1 vs 4,2 vs 4,3 vs 4.

很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人,通过上面这种比赛规则，总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛,如果分为三组则需要3场比赛。但是无论怎么分都不可能只需要1场比赛。

相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。

输入
每行为一组数据，包含两个数字 N, K

输出
对输入的N,K 如果N个员工通过一定的分组方式可能会一共需要K场比赛，则输出"YES",否则
输出"NO",每组数据占一行。所有的输入输出均为标准输入输出。

SOL:这道题是一道潜伏很深的动态规划。先建一下模：N个人，如果分成m组，每组x_i人，那么需要打的比赛场数是

\sum_{i\neq j} x_ix_j

。所以本题就是给定N,看是否能找到一个组人数划分使得上式等于K。

做一下变化:

K=\sum_{i\neq j} x_ix_j = \frac{(x_1+\ldots+x_m)^2-\sum_ix_i^2}{2}=\frac{N^2-\sum_ix_i^2}{2}

所以这里我们把这道题变成了如何找到m个数使得这m个数的和等于N，平方和等于N^2-2K。

令T(s)为所有"平方和为s的一组数的和"的集合，即:

T(s)=\{x_1+\dots+x_m|\forall \sum_ix^2_i=s\}

所以T(5)={3,5}，也就是说5可以分解为1+1+1+1+1也可以分解为1+2^2。
关于T(s)的递推式为

T(s)=\left\{\begin{array}{ll}
(\bigcup_{i=1}^{s/2} (\{t\} \cup T(i))\odot T(s-i)) & i=t^2\\
\bigcup_{i=1}^{s/2} T(i)\odot T(s-i) & \textrm{otherwise}
\end{array}
\right.

这里定义

A\odot B = \{ a+b | \forall a\in A, b\in B\}

边界条件: T(1)={1}