c# - 父亲，两个儿子，999幅画

Question

这是求职申请的问题: “一位父亲有两个儿子，999幅画，每幅画的值(value)都不一样，第一幅1，第二幅2，以此类推，直到最后一幅画999。他想把所有的画都分给他的两幅儿子，这样每个儿子都得到同等的值(value)。用 999 幅画有多少种方法可以做到这一点？ 示例:如果父亲有 7 幅画，他可以通过给第一个儿子画 1、6 和 7 来公平分配它们。第二个儿子将得到 2、3、4 和 5。两者的值(value)总和为 14。如果有7幅画，爸爸可以公平地分成4种(另外3种不在这里列出)，所以解是4。 提示:数字可能很大，所以请将最后 10 位数字和您的解决方案草图发送给我们。”

我所做的是尝试使用蛮力方法，通过编写一个 c# 程序来添加所有可能的组合，该程序编写自己的 c# 程序，循环中循环，如下所示:

StringBuilder sb = new StringBuilder();
for (short i = 2; i <= 999; i++) //starts from 2 because 1 is always added to the total for one side
{
    sb.AppendLine("for (byte i" + i.ToString() + " = 0; i" + i.ToString() + " < 2; i" + i.ToString() + "++)");
    sb.AppendLine("{");
}

for (int i = 2; i <= 999; i++)
{
    sb.Append("if (i" + i.ToString() + " == 1) { total += " + i.ToString() + "; }\n");
}

for (short i = 2; i <= 999; i++)
{
    sb.AppendLine("}");
}

然后在结果中的 if block 之后添加:

if (total == 249750)
{
    count++; //count is a BigInteger
}
total = 1;

这种方法在技术上应该可行(在较少数量的绘画上进行了测试)，但问题是它是一个巨大的数字，以这种方式在我的计算机上计算结果需要大约一百万年......是否有一些数学技巧可以在合理的时间内完成此操作？

Answer 1

确定第一个儿子可以获得值 k 的方法有多少种，这更容易解决更一般的问题，其中 k 是一个参数。找出适当的概括是一门艺术；它在名为动态规划的算法类(class)中教授。

让x 成为一个变量。所需的数学洞察力是，对于 n 幅画，x^k 在多项式乘积中的系数

x (1 + x^2) (1 + x^3) ... (1 + x^n)

x中的

是第一个儿子可以得到值k的方式数(包括值1的绘制)。这是因为此产品分发给

(sum for i_2 = 0 to 1) (sum for i_3 = 0 to 1) ... (sum for i_n = 0 to 1)
    x^(1 + 2 i_2 + 3 i_3 + ... + n i_n),

这实际上是您的蛮力解决方案评估该产品的方式。这里的动态规划相当于一个一个地分配因素，而不是一次全部分配，例如，

x (1 + x^2) = x + x^3
x (1 + x^2) (1 + x^3) = (x + x^3) (1 + x^3)
                      = x + x^3 + x^4 + x^6.
x (1 + x^2) (1 + x^3) (1 + x^4) = (x + x^3 + x^4 + x^6) (1 + x^3)
                                = x + x^3 + x^4 + x^6 + x^4 + x^6 + x^7 + x^9
                                = x + x^3 + 2 x^4 + 2 x^6 + x^7 + x^9.

节省的时间来自于重复的条款。我们已经只有​​六个项需要应对，而不是八个(二的三次方)。

只保留最后十位数字意味着我们可以在整数环中对 10^10 求这个乘积。因此，我们可以减少中间系数模数以避免求助于 bignums。这个技巧在竞争激烈的编程社区中广为人知，在抽象代数或数论类(class)中有正式介绍。

在Mathematica :

In[1]:= Coefficient[x Product[1+x^i,{i,2,7}],x^(Sum[i,{i,1,7}]/2)]

Out[1]= 4

In[2]:= Coefficient[x Product[1+x^i,{i,2,8}],x^(Sum[i,{i,1,8}]/2)]

Out[2]= 7

在 Java 中:

public class PartitionPaintings {
    public static void main(String[] args) {
        long[] p = new long[] {0, 1};
        for (int i = 2; i <= Integer.parseInt(args[0]); i++) {
            long[] q = new long[p.length + i];
            for (int k = 0; k <= p.length - 1; k++) {
                for (int j = 0; j <= 1; j++) {
                    q[k + i * j] = (q[k + i * j] + p[k]) % 10000000000L;
                }
            }
            p = q;
        }
        System.out.println(p[(p.length - 1) / 2]);
    }
}