非传递性骰

考虑如下几种非标准骰： 骰子A：1 4 4 4 4 4 骰子B：2 2 2 5 5 5 骰子C：3 3 3 3 3 6 两名玩家先轮流选择一枚骰子，然后一起掷出，点数高者获胜。 例如若先手玩家选择骰子A，后手玩家选择骰子B，则后手玩家获胜的概率为$P= 7/12 > 1/2$。 若先手玩家选择骰子B，后手玩家选择骰子C，则后手玩家获胜的概率也为$P = 7/12 > 1/2$。 若先手玩家选择骰子C，后手玩家选择骰子A，则后手玩家获胜的概率为$P = 25/36 > 1/2$。 因此无论先手玩家选择哪个骰子，后手玩家总能找到一枚骰子，从而使自己获胜的概率超过一半。拥有这一性质的骰子组合称为非传递性骰集。 给定以下条件： 共有三枚六面骰，每一面上的点数在1至N之间（包括1和N）。 只要两个骰子上的点数均相同，无论点数标在哪个面上，这两个骰子都视作相同。 三个骰子应当不同，但同一点数允许出现在不同的骰子上。 最后，骰集中的骰子没有顺序之分。 $N=7$时共有9780种非传递性骰集。 $N=30$时共有多少种这样的集合？

本题难度:

解答

设$g(n)$是所欲求的数量，$f(n)$是1到n每一种点数都用到（或者说恰有n种不同骰面时）非传递性骰集的数量，则有 $$g(n)=\sum_{k=1}^{n+1}\binom{n+1}{k}f(k-1).$$ 因而本题可以用动态规划递推计算。不过可以看出上式是关于$n$的多项式，由对称性可以降低其阶数，再枚举一些n较小时的情况就可以用插值法找出对应的系数。 以下闭合形式由官网论坛整理给出： $$g(30)=10705\binom{30}{18}+98092\binom{30}{17}+409596\binom{30}{16}+1030705\binom{30}{15}+1741403\binom{30}{14}+2082342\binom{30}{13}+1808978\binom{30}{12}+1152344\binom{30}{11}+535887\binom{30}{10}+178508\binom{30}{9}+40974\binom{30}{8}+6028\binom{30}{7}+491\binom{30}{6}+15\binom{30}{5}.$$ 本题无需编程（枚举的程序可以暴力实现，较为简单，因而此处略）。