2016.09.15noi模拟考

Problem A

题意

定义矩阵中元素是鞍点仅当它是行和列中严格最大的元素.现在你有一个列的的矩阵,其中的元素都是中的整数.求出至少有一个鞍点的矩阵数对的值.

感想

根本不会做,写个暴力都还要打表才能拿分,果断弃疗.

思路

如果直接一行一行的确定鞍点来递推的话,是根本不好转移的.
看到题目中鞍点的定义,可知一个鞍点,它所在行和列中的其它元素都小于它.那么如果我们将鞍点从小的往大的放,就不必考虑之前的鞍点的限制了,并且肯定是可以不重不漏的.那我们已经知道怎么去考虑了,现在的任务就是求出只有个鞍点,个鞍点,个鞍点...个鞍点的矩阵数量.
设状态表示目前有个鞍点,其中最大的鞍点值为的方案数.则转移方程为:

但是这是的,不能接受.但是发现其实我们只要改变一下状态,令表示目前有个鞍点,其中最大的鞍点值的方案数,每次考虑从转移到就行了,依然是不重不漏的,复杂度为.

但是怎么统计答案呢?不能直接将加起来,因为我们转移是相当于慢慢地去将矩阵填满,而我们状态仅仅只填了和当前所填的鞍点有关联的行和列,也就是说还有一些格子没有填.直接填的话,可能又会和其它的状态有所重复.
表示鞍点数正好为的方案数.要大于.设.它们之间的关系是:

我们要求,变化一下式子可得:

发现是可以由大的往小的递推出来的,那么已经可以算出答案了.
但其实是可以算出答案的.数学中有一个恒等式:

我们想要的答案是,那么: