这是一个工作申请的问题：
“一位父亲有两个儿子和999幅画.每幅画都有不同的价值：第一幅值1,第二幅值2,依此类推,直到最后的画作价值999.他想将他的所有画作分成两部分.儿子们,每个儿子都有同等的价值.有999幅画有多少种方式可以做到这一点？
例如：如果父亲有7幅画作,他可以通过给第一个儿子绘画1,6和7来公平地划分它们.第二个儿子将得到2,3,4和5.两者的总和相等,14.有7幅画,父亲可以用4种方式对它们进行相当划分(其他3种不在此列出),所以解决方案是4.
提示：数字可能很大,请将最后10位数字和解决方案草图发送给我们.“
“一位父亲有两个儿子和999幅画.每幅画都有不同的价值：第一幅值1,第二幅值2,依此类推,直到最后的画作价值999.他想将他的所有画作分成两部分.儿子们,每个儿子都有同等的价值.有999幅画有多少种方式可以做到这一点？
例如：如果父亲有7幅画作,他可以通过给第一个儿子绘画1,6和7来公平地划分它们.第二个儿子将得到2,3,4和5.两者的总和相等,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块之后添加：
if (total == 249750)
{
count++; //count is a BigInteger
}
total = 1;
这种方法在技术上应该起作用(在较少数量的绘画上进行测试),但问题是它是一个HUUUGE数字,用这种方式在我的计算机上计算结果需要一百万年左右…是否有一些在合理的时间内做这个的数学技巧？
解决方法
更容易接近确定第一个儿子可以获得值k的方式的更一般的问题,其中k是参数.找出适当的概括是一门艺术;它以动态编程的名义在算法课程中讲授.
设x是变量.所需的数学见解是,对于n个绘画,多项式乘积中x ^ k的系数
x (1 + x^2) (1 + x^3) ... (1 + x^n)
in 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.这个技巧是竞争性编程社区所熟知的,在抽象代数或数论的课程中正式涵盖.
In[1]:= Coefficient[x Product[1+x^i,{i,2,7}],x^(Sum[i,1,7}]/2)]
Out[1]= 4
In[2]:= Coefficient[x Product[1+x^i,8}],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]);
}
}
