感谢大牛们，我这种水人只能踩在巨人的肩膀上走。

对于求诸如x个东西中选y个满足...的方案数，一般的思路是这样的：
设f(i,j,k)表示前i个里取j个使得状态为k的方案数，
计算的时候枚举第i个是否取。
一个简单的例子：组合数C(i,j)
C(i,j)=C(i-1,j-1)+C(i-1,j)
因为没有特殊要求，所以k就省了

回到这题，一开始思路是这样的：
把所有的三元组排序，然后f(i,j,k)表示前i个三元组中取
j个使得它的状态为k的个数（k用二进制压缩）

不过，这个从时间、空间复杂度上都是不可取的。

怎么办呢？

一个通用的优化方法：合并状态
设f(a,b,k)为选k个三元组，使改变a个奇偶性，不改变b个奇偶性的方案数
但事实证明...它还是tle的

当这种山穷水尽的时候，往往需要另辟蹊径。

先考虑一个简单的情况：如果不要求三元组都不同，且记次序，那么如何做？
设f(m,k)为取m个三元组，使得改变k个巧克力的奇偶性的方案数
f(m,k)=
f(m-1,k-3)*c(k,3)*c(n-k,0)+
f(m-1,k+3)*c(k,0)*c(n-k,3)+
f(m-1,k+1)*c(k,1)*c(n-k,2)+
f(m-1,k-1)*c(k,2)*c(n-k,1)
这将是一个水题了
不过这题并不是那么水——记次序，且不许重复。
怎么办！
┌　┐┐┌　　┐　┐┌　
╰─├╯├┘┌──┴─┐
└┬┼┘╯│　┌──┐　
└╯┘┘││　　　┌╯　
└┼┬┘┌╯───┼─　
└┴╯┘╯┘└──╯　　
对，数学中的容斥原理
我们只要排除掉重复的，再除以同一个方案不同顺序产生的个数，不就可以了吗？

O(∩_∩)O哈哈~，解决了！
设f(m,k)为取m个三元组，使得改变k个巧克力的奇偶性的方案数
f(m,k)=(
f(m-1,k-3)*c(k,3)*c(n-k,0)+
f(m-1,k+3)*c(k,0)*c(n-k,3)+
f(m-1,k+1)*c(k,1)*c(n-k,2)+
f(m-1,k-1)*c(k,2)*c(n-k,1)-
f(m-2,k)*(c(n,3)-m+2))/m
这，就是答案。

有几个细节需要注意：
需要余数除法，于是要写一个扩展gcd
不过，有一个偷懒的办法：
对i计算一个inv[i]，使得i*inv[i]模10007余1
这个怎么算呢？
继续偷懒，对每一个i计算
i同余w的power[i]次方（w是一个常数），
inv[i]=w的10007-1-power[i]次方
选择w是有技巧的，不是每一个跟10007互质的数都行
（10007其实是个质数）
我的方案：一个一个的试哪个w可以...
实验证明w=5正好

此题给我一个启示：它很可能蕴含这一个类型的题，
他们都是求若干个不记次序、不相同的元素组成的序列的个数，
但是计次序、可以相同的序列个数比较好算，
这时，用数学，刨除掉重复的，除以本质一样的，就可以得答案。
至于这个类型的题...其实挺难构造的，不过我相信，
这里面一定还有一座花园。

• Re:雁过留声——排列组合和dp (46) 0803enjoy 2010-07-13 11:38:27
• Re:雁过留声——排列组合和dp (294) 0803enjoy 2010-07-13 11:41:28
• Re:雁过留声——排列组合和dp (336) zzsx65zdf 2012-03-30 19:36:32