Question

一道算法题，C语言或C++

Description
正逢佳节来临，学校组织了一个趣味智力比赛，小W想：“我这么聪明的人怎么能不去参加智力挑战呢？”于是小W就去参加比赛了。到达场地后，小W看了比赛的规则，规则是这样的：

（1）.每个人会发12张不同的卡片。
（2）.首先每个人要将这些卡片平均分成3组。
（3）.接下来要求把这些卡片平均分成4组，但是每个卡片不能与先前同组的卡片分到一组。

这个比赛其实是很简单的，小W很快就解决了，但是他又想到一个更加深入的问题，假如有12n个不同的卡片，按照步骤先分为3n组后，有多少种不同的方法可以按照要求（3）把这些卡片分成4n组。（同一组中的卡片不分顺序，各组之间也不分顺序）

Input
输入一个n（n<=40）

Output
输出有多少种不同的方法可以按照要求（3）把这些卡片分成4n组。输出结果对1000000007取余。

Sample Input
1

Sample Output
576

Answer 1

这不是算法题，是数学那一块的
设m=3n
答案应该是（4^(m-1)）*（3^(m-1)）*（2^(m-1)）
证明：乘法原理，12n分到3n组中意味着每组4个，对第一组匹配剩下的所有组，则第一张卡共有4^(m-1)种选法，第二张3^(m-1)，第三张2^(m-1)
代码你应该写得出来，应该不用快速幂

追问

错了，我之前用的就是24^(3*n-1)。

Answer 2

const int a[41]={0,576,509089824,54579765,43930481,393903744,379980588,534904842,430392966,274953764,500402773,588651425,706368571,399211230,122866475,976622134,793659787,692287546,750004016,732180689,496320621,510721200,354822069,491641749,11105979,478268076,217242980,781108636,665643107,917492958,69734184,396478206,32874346,88745878,621502960,430208166,542735267,837519575,103787627,491050573,273385431};
//题目有点难啊，不知道这个答案对不对？

追问

答案对了。你的表是怎么打的？

追答

用了一个时间复杂度O(n^4)，常数还特别大的动态规划，n=40的时候要跑10+s
代码太长这里写不开，私信发给你了。
这个问题蛮有意思，题目哪来的？你要是知道了正解记得告诉我一声。

追问

十分感谢！

题目来源：网页链接

知道正解了我会告诉你的。