> http://acm.tdzl.net:83/JudgeOnline/showcontest?contest_id=1016
> 
> A Gardon's box I
> 1-n按顺序入栈，要求列出所有可能的出栈序列。
> n<=10，DFS即可。每次有入栈和出栈两种选择。优先选择出栈可以得到字典序的排列。
> 也可n!生成排列再每次O(n)进行判断。
> 
> B Gardon's box II
> 问题同上，求所有可能性的总数。
> 我的解法是将这个问题等同于如下问题：
> 若干人买票，有些人手持50元的钱，有的人手持100元的钱，售票员一开始没有零钱找，问有多少种排列方法。
> 这个问题首先由C(2n,n)种排列中，有若干不合法的排列，将任一不合法的排列第一个不合法位置之后的所有拿50元的换成100元，拿100元的换成50元，即得到一个n-1个50元和n+1个100元的排列。并且任一这种排列也可以用相同方法得到之前问题的不合法排列。
> 所以，原问题的所有合法排列数为：C(2n,n)-C(2n,n-1)或者C(2n,n)/(n+1)
> 
> C Gardon's box III
> 给任一入栈顺序，要求出栈顺序按照字典序第k大的排列。
> 解法是从第一个元素开始直接计算出每个位置应该的值。
> 设函数B(i,j)表示栈中有i个元素，并且还有j个元素没有入栈的所有排列数，则对于每一个位置可以轻易计算出选择某一个数时所有的排列总数c。此时将k不断减去c直至k小于等于c，就可以确定出这一位置的数字。
> 
> D Gardon's box IV
> 三维空间的九宫问题，问是否有解。
> 方法是判断逆序数和0的三个坐标之和的奇偶性。任意一次移动（相当于交换两个元素）必然带来逆序数奇偶的改变，同时0的三个坐标之和的奇偶性也会改变。并且可以构造证明当有两个以上边长大于等于2时，一定有解。
> 要考虑的特殊情形就是两个方向的边长都是1的时候，譬如
> 1 1 4
> 1 2 3 0
> 3 1 2 0
> 不能根据逆序数来判断，而应该将0去掉以后比较剩下所有元素，依次相等才有解。
> 
> E Clean the house
> 三分图匹配，DFS可以过，也可以模仿二分图匹配用增广法求解。
> 
> F Apple
> 概率题，两个人玩游戏，B每轮赢得几率为p，A持有a个苹果，b持有b个苹果，每轮败者给胜者1个苹果，直至其中一人手里没有苹果。问游戏平均要经过多少轮才能结束。
> 可列出如下等式，设f(i)为B持有i个苹果时的期望值，则有
> f(i)=(1-p)f(i-1)+pf(i+1)+1
> 并且f(0)=f(a+b)=0
> 可二分搜索f(1)并确认f(a+b)的值，不过实践证明精度很低。我的解法如下：
> 设f(i)=k(i)f(1)+t(i)
> 则有
> k(0)=0 t(0)=0
> 和
> k(1)=1 t(1)=0
> 最后解出k(a+b)和t(a+b)，则直接可得出f(1)=-t(a+b)/k(a+b)
> 然后直接将k(b)和t(b)带入求出f(b)即可。
> 
> G Garra Fibonacci
> F(0)=a F(1)=b F(i)=N，并且对于0<=i F(i)都是非负整数，给出i和N，问有多少组可能的a。
> 设f(i)为fibonacci序列，并且设f(-1)=1 则有
> F(i)=f(i-1)a+f(i)b
> 首先用扩展欧几里德求出一组ax+by=1（其实x和y的绝对值就是f(i-1)和f(i-2)），然后将它乘上N，再通过取余得到a最小的非负解（每当a增加f(i)，b就要减少f(i-1)）
> 此时如果b是负数，则无解，否则b/f(i-1)取整+1即为最终解。
> 
> H Gauss Pascal Number
> 对所有的j<n and (i+j)=0 mod m求C(i,j)
> 首先看对某一行第k行（也就是C(k-1,j)行，先假设k%m==0）
> 设i^m=1，则(1+i)^n的常数系数即为所有对应项之和。该乘法可以表示成如下矩阵A的幂：
> 1 1 0 ... 0 0
> 0 1 1 ... 0 0
> 0 0 1 ... 0 0
> .     ... . .
> .     ... . .
> 0 0 0 ... 1 0
> 0 0 0 ... 1 1
> 1 0 0 ... 0 1
> 其实若k%m==0，该行所有对应项之和就是该矩阵乘积左上角元素。若k%m!=0，其实取出第一行第((m-k)%m)项即可。
> 所以，对于不同行的偏移情况，构造轮换矩阵C
> 0 0 0 ... 0 1
> 1 0 0 ... 0 0
> 0 1 0 ... 0 0
> .     ... .
> .     ... .
> .     ... .
> 0 0 0 ... 1 0
> 左乘即可。
> 因此构造矩阵：
> A I
> O C
> 求n次幂，将右上角矩阵取出，补上C的(m-(n%m))%m次方（或者直接取出对应项）即可。
> 这样就避免了复杂度里出现N，总复杂度m^3*log n

• 汗 不小心点错了 (0) mmdcat 2006-10-16 13:29:59