Codechef OJ上一道题目没有思路，请高手提示一下解题思路

Question

是昨天Codechef上的题，链接是http://www.codechef.com/CONI2015/problems/CN02。
我理解题目大概的意思是（仅做参考，为保证准确最好看一下链接）：
有6对箱子和一个单独的箱子，表示如（（A1 A2） （B1 B2） （C1 C2） （D1 D2）（E1 E2） （F1 F2） G）,有N个物品要放入这7个箱子里，N<=10^6，并且保证每个箱子至少有一个物品，而且成对的两个箱子里的物品数量要相等，问分配N个物品的方式有多少种，答案要模上大质数10^9+7.
请高手给予解题思路，先谢谢了。

Answer 1

嘛， 你这个问题嘛， 可以这样考虑嘛：

• N为偶数的时候, 由于前面6个箱子都是成对出现的且至少为一个，所以对于G来说他的个数必定是偶数个吧，也就是 G 的分配数为 N/2 种，

  • 对于其中一个特例，比如 G 分配为2来说吧, 剩下的就是 N-2, 也就是把 $\frac{N-2}{2}$ = tmp 的物品分配到 6个箱子里面， 且保证每个箱子都有物品，就是 使用插板法 肯定是 C[tmp-1][5] 这么算吧
  • 这么转化一下就是: $\sum_{i=2}{N-12} C[$\frac{N-2}{2}$-1][5]$ 这么算的吧
  • 考虑一下 N<=12 的边界情况很容易的吧, 为什么是 N<=12 呢？ 你想啊，6个成对的箱子都要有物品不是就是这个结果了嘛。 N<=12 都可以判定为不合法的啦吧
  • 然后就是，先 O(N) dp就算出 10^6 以内所有的组合 C[m][n]%(10^9+7) 吧， 结果随便怎么取模一下就可以啦

• N为奇数的时候， 和上面考虑的一样的吧， 就是边界情况不一样吧