1956年Robert Abbott发明了一个全新的纸牌游戏叫做Eleusis，后来Martin Gardner在1959年6月的Scientific American杂志上介绍了这个游戏。77年10月这个游戏又进一步得到完善，并发展出一些其它的玩法。最近，John Golden提出了这个游戏的第三个版本Eleusis Express，他比Eleusis更简单，更完备，平均游戏时间也更短。Robert Abbott对这个游戏非常满意，这种简单而有趣的推理游戏很可能会像杀人游戏一样流行起来。下面我简单介绍一下这个游戏的规则，你将会看到一种集策略和推理于一体的全新的纸牌游戏。

    这个游戏的规则极其简单，但变化也异常丰富，因为这个游戏的出牌方式是不固定的，游戏开始时玩家甚至不知道出牌的规则是什么。玩家的主要任务就是在游戏过程中探索出牌的规则。游戏需要两副牌，玩家以3到8人为宜。每轮游戏前，玩家需要推选出一位主持人，主持人在这个游戏里扮演最重要的角色。游戏开始前，主持人自己在心里默想一个出牌规则(Secret Rule)，但不能告诉玩家。规则的内容应该只考虑扑克牌的花色与点数，与出牌人、牌的摆放方式等无关。这个规则必须简单、明确，通常以“如果上一张牌是什么什么，那么下一张牌就该接什么什么”一类的形式给出，比如“如果上一张牌是红色，下一张牌就是黑色；如果上一张牌是黑色，下一张牌就该是红色”，或者是“要么与前一张牌同花色，要么与前一张牌同点数”。然后主持人洗牌，给每个人发12张牌，然后再翻出一张放在桌面上作为第一张牌打出。这张牌及后面正确的跟牌都摆成一行，叫做主线(Mainline)；主线下方可能会有若干边线(Sideline)，表示错误的跟牌。游戏正式开始前，主持人可以对秘密规则进行一些提示，之后玩家轮流打牌，主持人判断玩家打出的牌是否符合他的规则：

    
如果打出的牌符合规则
    此时主持人把这张牌加在主线的右边，该玩家手中的牌就少了一张。如果此时该玩家手中的牌打完了，则游戏结束，否则游戏继续进行。
    另外，该玩家还可以获得一次猜测出牌规则的机会，同时每个玩家都必须听他说的答案。如果该玩家猜对了，主持人也宣布游戏结束，否则游戏继续。
如果打出的牌不符合规则
    此时主持人把这张牌放在的相应的边线位置上，告诉大家这张牌不能接在这个位置。这名玩家需要再摸一张牌，手中的牌的张数不变。

    轮到某位玩家出牌时，该玩家可以选择不出牌，即宣称自己无牌可打。此时他应该把手中的牌摊出来给所有人看，同时主持人判定该玩家是否确实无牌可打：
如果该玩家确实无牌可打
    如果此时玩家手中只有一张牌，游戏结束。否则，主持人清点该玩家手中牌的数目N，把它们放回还没发完的牌摞的最底下，再发给他N-1张牌。同时，该玩家获得一次猜测出牌规则的机会，猜对了同样可以直接获胜。
如果该玩家有可以打的牌
    此时主持人从中选出一张可以打的牌接在主线后面，该玩家收起自己其余的牌并再摸一张，保持手中的牌数不变。

    游戏结束后，每个人的得分就是自己打出去的牌的张数。打完所有牌而获胜的玩家再获3分的加分，猜对规则而获胜则得到6分的加分。主持人的得分与本轮最高分相同。然后大家重新推选主持人，继续下一轮游戏。
    如果牌抓完了但游戏还没结束，可以再洗一副牌继续进行，或宣布游戏结束，本轮不计分。然后，主持人阴笑几下，故弄玄虚地说出自己所想的规则，等待玩家们恍然大悟并集体发出“哎呀~~~”的叹息声（或者等待玩家大骂这规则太他妈BT了谁能想到啊）。
    若干轮游戏后，最终的胜者就是累积得分最高的人。我们可以适当给赢家一些奖励，比如让他亲一下最漂亮的MM玩家，或者传几个小A给他。得分最低的人也应当受到惩罚，比如叫他把MM共享出来让大家玩弄，或者贡献一个XX论坛的账号。

    能想到一个简单明了而又富有新意的规则是非常重要的，因此游戏的主持人是整个游戏的灵魂，一个思维活跃又爱捉弄人的主持人可以让游戏变得非常精彩。这里写一些自己想到的规则，大家有什么好的想法也可以在下面说一说。

• 按黑红梅方的顺序出牌
  
• 按三张红色，三张黑色，又三张红色，又三张黑色的顺序出牌
  
• 如果上一张牌的点数是1到7，则应该接8到K；如果上一张牌是8到K，则应该接1-7
  
• 相邻两张牌的点数之和大于10
  
• 相邻两张牌的点数的差的绝对值不超过3
  
• 相邻两张牌的点数加起来能被3整除
  
• 下一张牌的点数比上一张牌大1点、2点、3点或4点；数字大小关系是“循环的”
  
• 如果上一张牌的点数是奇数，则出红色牌；如果上一张牌的点数是偶数，则出黑色牌
  
• 如果上一张牌是红色，则出牌的点数小于等于上张牌的点数；否则，出牌的点数大于等于上张牌的点数
  
• 如果上一张牌的点数为平方数，则出牌的点数是非完全平方数；否则出牌的点数应该是一个平方数
  
• 牌的点数一大一小交替排列（即奇数位置上的牌比前面的点数小，偶数位置上的牌比前面点数大）
  
• 如果花色与前面一张相同，则点数必须比它大；如果花色与前面一张不同，则点数必须比它小

做人要厚道 转贴请注明出处
查看更多：http://www.logicmazes.com/games/eleusis/index.html

    定义f(n)的值为将n拆分成若干个2的幂的和，且其中每个数字出现的次数不会超过两次的方案数。规定f(0)=1。
    例如，有5种合法的方案可以拆分数字10：1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 和 2+8。因此，f(10)=5。
    请用一句最简单的话来描述集合{ f(n)/f(n-1) }。证明你的结论。

    注意：答案远比一个递归公式来得精辟，来得巧妙。如果你发现了我们的结论，你会一眼认定它为正确答案。














































    答案：数列{ f(n)/f(n-1) }以最简形式包含了所有的正有理数。

    如果n是奇数（等于2m+1），那么数字1（即2^0）必须出现且只能出现一次。现在的问题就是，2m的拆分方案中有多少个方案不含数字1呢？稍作思考你会立即发现，它就等于f(m)，因为m的所有拆分方案的所有数都乘以2后正好与不含1的2m拆分方案一一对应。因此，f(2m+1) = f(m)
    如果n是偶数（等于2m），那么数字1要么没有出现，要么恰好出现两次。对于前一种情况，我们有f(m)种可能的方案；第二种情况则有f(m-1)种方案。因此，f(2m) = f(m) + f(m-1)
    另外，显然f(k)都是正数。于是，f(2k-1) = f(k-1) < f(k-1)+f(k) = f(2k)
    这样，我们可以得到以下三个结论：

    结论1：gcd( f(n),f(n-1) ) = 1
    证明：对n进行数学归纳。显然gcd( f(1),f(0) ) = gcd(1,1) = 1
    假设对于所有小于n的数结论都成立。根据n的奇偶性，下面两式中必有一个成立：
    gcd( f(n),f(n-1) ) = gcd( f(2m+1),f(2m) ) = gcd( f(m), f(m)+f(m-1) ) = gcd( f(m),f(m-1) ) = 1
    gcd( f(n),f(n-1) ) = gcd( f(2m),f(2m-1) ) = gcd( f(m)+f(m-1), f(m-1) ) = gcd( f(m),f(m-1) ) = 1

    结论2：如果f(n+1)/f(n) = f(n'+1)/f(n')，那么n=n'
    证明：还是数学归纳法。当max(n,n')=0时结论显然成立，因为此时n=n'=0。
    假如对于所有小于n的数结论都成立。由于f(2k-1)<f(2k)，那么要想f(n)/f(n-1) = f(n')/f(n'-1)，n与n'的奇偶性必须相同，于是可以推出f(m)/f(m-1) = f(m')/f(m'-1)，根据归纳我们有m=m'，这就告诉我们n=n'。

    结论3：对于任何一个有理数r，总存在一个正整数n使得r=f(n)/f(n-1)。
    证明：把r写成两个互素的数p和q的比。我们对max(p,q)施归纳。
    显然，当p=q=1时结论成立，此时n=1。
    不妨设p<q，那么定义r'为p/(q-p)。根据归纳假设，总存在一个数m满足r'=f(m)/f(m-1)。于是r=f(2m+1)/f(2m)。当p>q时同理可证明。

做人要厚道
转贴请注明出处

    好像目前还没有这方面题目的总结。这几天连续看到四个问这类题目的人，今天在这里简单写一下。这里我们不介绍其它有关矩阵的知识，只介绍矩阵乘法和相关性质。
    不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中，一个矩阵说穿了就是一个二维数组。一个n行m列的矩阵可以乘以一个m行p列的矩阵，得到的结果是一个n行p列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。其中，结果的那个4等于2*2+0*1：
    
    下面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵，得到一个1 x 2的矩阵：
    

    矩阵乘法的两个重要性质：一，矩阵乘法不满足交换律；二，矩阵乘法满足结合律。为什么矩阵乘法不满足交换律呢？废话，交换过来后两个矩阵有可能根本不能相乘。为什么它又满足结合律呢？仔细想想你会发现这也是废话。假设你有三个矩阵A、B、C，那么(AB)C和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和（枚举所有的k和l）。

经典题目1 给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转
    这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。
    

经典题目2 给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每个数都mod p。
    由于矩阵乘法具有结合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论：当n为偶数时，A^n = A^(n/2) * A^(n/2)；当n为奇数时，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。这就告诉我们，计算A^n也可以使用二分快速求幂的方法。例如，为了算出A^25的值，我们只需要递归地计算出A^12、A^6、A^3的值即可。根据这里的一些结果，我们可以在计算过程中不断取模，避免高精度运算。

经典题目3 POJ3233 (感谢rmq)
    题目大意：给定矩阵A，求A + A^2 + A^3 + ... + A^k的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k<=10^9。
    这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如，当k=6时，有：
    A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)
    应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。

经典题目4 VOJ1049
    题目大意：顺次给出m个置换，反复使用这m个置换对初始序列进行操作，问k次置换后的序列。m<=10, k<2^31。
    首先将这m个置换“合并”起来（算出这m个置换的乘积），然后接下来我们需要执行这个置换k/m次（取整，若有余数则剩下几步模拟即可）。注意任意一个置换都可以表示成矩阵的形式。例如，将1 2 3 4置换为3 1 2 4，相当于下面的矩阵乘法：
    
    置换k/m次就相当于在前面乘以k/m个这样的矩阵。我们可以二分计算出该矩阵的k/m次方，再乘以初始序列即可。做出来了别忙着高兴，得意之时就是你灭亡之日，别忘了最后可能还有几个置换需要模拟。

经典题目5 《算法艺术与信息学竞赛》207页（2.1代数方法和模型，[例题5]细菌，版次不同可能页码有偏差）
    大家自己去看看吧，书上讲得很详细。解题方法和上一题类似，都是用矩阵来表示操作，然后二分求最终状态。

经典题目6 给定n和p，求第n个Fibonacci数mod p的值，n不超过2^31
    根据前面的一些思路，现在我们需要构造一个2 x 2的矩阵，使得它乘以(a,b)得到的结果是(b,a+b)。每多乘一次这个矩阵，这两个数就会多迭代一次。那么，我们把这个2 x 2的矩阵自乘n次，再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想，这个2 x 2的矩阵很容易构造出来：
    

经典题目7 VOJ1067
    我们可以用上面的方法二分求出任何一个线性递推式的第n项，其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：
    
    利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。

经典题目8 给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
    把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。

经典题目9 用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果
    
    我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
    后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。

经典题目10 POJ2778
    题目大意是，检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段，每个片段长度不超过10。数据规模n<=2 000 000 000。
    下面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例，说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀，把n位DNA分为以下7类：以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”，它可以是任一字母，只要这个字母不会让它所在的串成为某个病毒的前缀。显然，这些分类是全集的一个划分（交集为空，并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到??有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G或C），从GG到??有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。
    题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是100^3 * log(n)，AC了。

    最后给出第9题的代码供大家参考（今天写的，熟悉了一下C++的类和运算符重载）。为了避免大家看代码看着看着就忘了，我把这句话放在前面来说：
    Matrix67原创，转贴请注明出处。

#include <cstdio>
#define SIZE (1<<m)
#define MAX_SIZE 32
using namespace std;

class CMatrix
{
    public:
        long element[MAX_SIZE][MAX_SIZE];
        void setSize(int);
        void setModulo(int);
        CMatrix operator* (CMatrix);
        CMatrix power(int);
    private:
        int size;
        long modulo;
};

void CMatrix::setSize(int a)
{
    for (int i=0; i<a; i++)
        for (int j=0; j<a; j++)
            element[i][j]=0;
    size = a;
}

void CMatrix::setModulo(int a)
{
    modulo = a;
}

CMatrix CMatrix::operator* (CMatrix param)
{
    CMatrix product;
    product.setSize(size);
    product.setModulo(modulo);
    for (int i=0; i<size; i++)
        for (int j=0; j<size; j++)
            for (int k=0; k<size; k++)
            {
                product.element[i][j]+=element[i][k]*param.element[k][j];
                product.element[i][j]%=modulo;
            }

    return product;
}

CMatrix CMatrix::power(int exp)
{
    CMatrix tmp = (*this) * (*this);
    if (exp==1) return *this;
    else if (exp & 1) return tmp.power(exp/2) * (*this);
    else return tmp.power(exp/2);
}


int main()
{
    const int validSet[]={0,3,6,12,15,24,27,30};
    long n, m, p;
    CMatrix unit;
    
    scanf("%d%d%d", &n, &m, &p);
    unit.setSize(SIZE);
    for(int i=0; i<SIZE; i++)
        for(int j=0; j<SIZE; j++)
            if( ((~i)&j) == ((~i)&(SIZE-1)) )
            {
                bool isValid=false;
                for (int k=0; k<8; k++)isValid=isValid||(i&j)==validSet[k];
                unit.element[i][j]=isValid;
            }

    unit.setModulo(p);
    printf("%d", unit.power(n).element[SIZE-1][SIZE-1] );
    return 0;
}

    不少人可能为找不到非传统题型的练习题而头疼。这几天我专门发出一些用于省选集训的题目供大家参考。

Problem 1: cell 手机
题目来源：USACO Contest FEB06 Gold (Translated by Matrix67)

问题描述
    奶牛们已经开始使用手机交流了，但它们发现手机的按键设计不适合它们的蹄子。它们想设计一个新的手机，让它的按键更少，但是更大。
    它们喜欢普通手机的一个功能：词语联想。每个按键都有一些字母和它对应，打出一个单词只需要按对应的按键。因为一个按键可能对应多个字母，因此某些单词可能会发生“歧意”。不过，大多数时候这种歧意可以通过用字典判断的方法来消除。
    考虑到奶牛们在自定义一款新的手机，它们还需要用奶牛字母表替换英文字母表。神奇的是，奶牛字母表中的字母恰好是英语字母表中的前L个字母，即使顺序也一样。它们想知道如何把这些字母分配给B个按键(1<=B<=L)使得在字典中不会产生歧意的单词最多。就像普通的手机一样，他们希望每个按钮上的字母都是字母表中一段连续的字母。

    这是一个答案提交类的题目。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件cell.3.in相对应的输出文件应该为cell.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入数据
    第一行：一个整数N，表示这是第N个输入文件。
    第二行：两个用空格隔开的整数：B和L
    第三行：D，字典中的单词数(1<=D<=1000)
    第四行到第D+3行：每一行包含一个字典中的单词，用1到10个大写字母表示。这些单词按照字典序给出，并且保证没有重复。

输出数据
    第一行：字典中具有唯一的按钮序列的单词数。
    第二行到第B+1行：其中的第n行包含有第n个按钮上的字母，用大写的字母按照字典的顺序表示。所有行必须按照字典序排列，每个字母出现恰好一次。如果有多个最优解，选用第一个按键上字母最多的解。如果最优解仍然不唯一，考虑第二个按键上字母最多，依此类推。

样例输入(cell.1.in)
1
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK

样例输出(cell.1.out)
7
AB
CDEFGHIJK
LM

样例说明
    第一个按键上只有AB两个字母，第二个按键上含有C到K，第三个按键上为LM。单词CELL、DILL、FILL和FILM的输入都是2233，其它7个单词的输入都是唯一的。

题解(Ctrl+A)：
    这道题目……搜索，乱搞。



Problem 2: selfstr 自描述序列
题目来源：Matrix67根据经典问题改编

问题描述
    “这句话里有1个数字零，2个数字一，1个数字二，0个数字三”。

    在N(N>=2)进制中只允许0到N-1这N个数字出现。一个N位的N进制数（允许有前导0）可以由另一个同样多位的数来描述。我们定义一个N位N进制数的描述序列为：左起第i个数字为原数中数字i-1出现的次数。
    例如，在4进制中，0023的描述序列为2011，因为0023中有2个0，0个1，1个2和1个3。
    我们惊奇地发现，4进制数1210的描述序列是它本身！我们称这样的数叫做“自描述序列”。

    你需要编写程序计算出在某个进制下的自描述序列。一个进制下的自描述序列可能有很多个，你只需要给出其中一个即可。
    这是一个答案提交类的问题。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件selfstr.3.in相对应的输出文件应该为selfstr.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入格式
    输入数据只有一个正整数N

输出格式
    输出N个字符，它表示N进制下的自描述序列。在高于10的进位制下，大于9的数字请用大写字母表示。
    如果有多种可能的解，你只需要输出其中一个。
    如果该进制下无解，请输出“NONE”。

样例输入(selfstr.1.in)
4

样例输出(selfstr.1.out)
1210

题解：
    这道题太有意思了！首先，你需要先算几个小数据。你会发现，算到N>=6后，渐渐有规律了：


   N   N进制下的自描述序列
   4    1210 or 2020
   5    21200
   6    NONE
   7    3211000
   8    42101000
   9    521001000

    事实上，这道题目就是考你当搜索到一些解后能不能找到规律得到所有解。这里我们发现，对所有N>6，至少存在一个解为R21(0...0)1000，其中R=N-4，中间0的个数为N-7。结论显然正确。
    有可能除了这个之外存在其它的解，因此我们仍然需要写一个check来核对答案。



Problem 3: relation 大小关系
题目来源：Matrix67根据经典问题改编

问题描述
    用关系“ < ”和“ = ”将3个数a、b、c依次序排列时，有13种不同的序列关系：
      a=b=c, a=b<c, a<b=c, a<b<c, a<c<b
      a=c<b, b<a=c, b<a<c, b<c<a, b=c<a
      c<a=b, c<a<b, c<b<a

    用这两种关系连接N个数有多少种不同的方案？

    这是一个答案提交类的问题。所有选手将得到10个输入数据，你只需要在你自己的计算机上计算出你的答案，然后把你的答案提交上来。与输入文件relation.x.in相对应的输出文件应该为relation.x.out，这里x表示一个1到10之间的数。

输入格式
    输入一个整数，表示N。

输出格式
    输出用小于和等于符号将N个数进行有序排列的方案数。

样例输入(relation.1.in)
3

样例输出(relation.1.out)
13

题解：
    组合数学+高精度。由于数据规模很小，我就直接搞成了答案提交类的题目。
    下面给出两种递推方法：
    Solution 1: N个数中必然存在一个最大的“等价类”，如果这个等价类里有k个数，那么剩下的数就有F(N-k)种排列方案。别忘了我们需要枚举这k个数是哪k个数。于是，F(N)=C(N,1)F(N-1)+C(N,2)F(N-2)+C(N,3)F(N-3)+ ... +C(N,N)F(0)
    Solution 2: 用F[ i, j]表示 i个数中有j 个等价类的排列方案（就是说有j-1个小于符号）。第 i个数有可能并入了F[i-1, j]中的 j个等价类中的一个，也有可能不与任何一个已有的数相等，独自成为一个等价类插入F[i-1, j-1]里产生的 j个空位中。于是，F[ i,j ]=F[i-1, j]*j + F[i-1,j-1]*j。


其它问题：
    如何用Cena评测答案提交类问题？
        见http://www.matrix67.com/blog/article.asp?id=176
    这些题的数据哪里有？
        第一题：http://ace.delos.com/FEB06，GOLD DIVISION里面的第三个
        第二题：自己写check，不需要数据
        第三题：http://www.research.att.com/~njas/sequences/b000670.txt，吓死你

Matrix67原创
转贴请注明出处

    我们年级有许多漂亮的MM。一班有7个左右吧，二班大概有4个，三班最多，16个，四班最可怜，一个漂亮的MM都没有，五班据说有1个。如果用一个函数“f(班级)=漂亮MM的个数”，那么我们可以把上述信息表示成：f(1)=7,f(2)=4,f(3)=16,f(4)=0,f(5)=1,等等。
    生成函数（也有叫做“母函数”的，但是我觉得母函数不太好听）是说，构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)。于是，上面的f函数的生成函数g(x)=7x+4x^2+16x^3+x^5+...。这就是传说中的生成函数了。关键是，这个有什么用呢？一会儿要慢慢说。我敢打赌这绝对会是我写过的最长的一篇文章。

    生成函数最绝妙的是，某些生成函数可以化简为一个很简单的函数。也就是说，不一定每个生成函数都是用一长串多项式来表示的。比如，这个函数f(n)=1 （n当然是属于自然数的），它的生成函数就应该是g(x)=1+x+x^2+x^3+x^4+...（每一项都是一，即使n=0时也有x^0系数为1，所以有常数项）。再仔细一看，这就是一个有无穷多项的等比数列求和嘛。如果-1<x<1，那么g(x)就等于1/(1-x)了。在研究生成函数时，我们都假设级数收敛，因为生成函数的x没有实际意义，我们可以任意取值。于是，我们就说，f(n)=1的生成函数是g(x)=1/(1-x)。

    我们举一个例子说明，一些具有实际意义的组合问题也可以用像这样简单的一个函数全部表示出来。
    考虑这个问题：从二班选n个MM出来有多少种选法。学过简单的排列与组合的同学都知道，答案就是C(4,n)。也就是说。从n=0开始，问题的答案分别是1,4,6,4,1,0,0,0,...（从4个MM中选出4个以上的人来方案数当然为0喽）。那么它的生成函数g(x)就应该是g(x)=1+4x+6x^2+4x^3+x^4。这不就是……二项式展开吗？于是，g(x)=(1+x)^4。
    你或许应该知道，(1+x)^k=C(k,0)x^0+C(k,1)x^1+...+C(k,k)x^k；但你或许不知道，即使k为负数和小数的时候，也有类似的结论：(1+x)^k=C(k,0)x^0+C(k,1)x^1+...+C(k,k)x^k+C(k,k+1)x^(k+1)+C(k,k+2)x^(k+2)+...（一直加到无穷；式子看着很别扭，自己写到草稿纸上吧，毕竟这里输入数学式子很麻烦）。其中，广义的组合数C(k,i)就等于k(k-1)(k-2)...(k-i+1)/i!，比如C(4,6)=4*3*2*1*0*(-1)/6!=0，再比如C(-1.4,2)=(-1.4)*(-2.4)/2!=1.68。后面这个就叫做牛顿二项式定理。当k为整数时，所有i>k时的C(k,i)中分子都要“越过”0这一项，因此后面C(k,k+1),C(k,k+2)之类的都为0了，与我们的经典二项式定理结论相同；不同的是，牛顿二项式定理中的指数k可以是任意实数。

    我们再举一个例子说明一些更复杂的生成函数。n=x1+x2+x3+...+xk有多少个非负整数解？这道题是学排列与组合的经典例题了。把每组解的每个数都加1，就变成n+k=x1+x2+x3+...+xk的正整数解的个数了。教材上或许会出现这么一个难听的名字叫“隔板法”：把n+k个东西排成一排，在n+k-1个空格中插入k-1个“隔板”。答案我们总是知道的，就是C(n+k-1,k-1)。它就等于C(n+k-1,n)。它关于n的生成函数是g(x)=1/(1-x)^k。这个生成函数是怎么来的呢？其实，它就是(1-x)的-k次方。把(1-x)^(-k)按照刚才的牛顿二项式展开，我们就得到了x^n的系数恰好是C(n+k-1,n)，因为C(-k,n)*(-x)^n=[(-1)^n*C(n+k-1,n)]*[(-1)^n*x^n]=C(n+k-1,n)x^n。这里看晕了不要紧，后文有另一种方法可以推导出一模一样的公式。事实上，我们有一个纯组合数学的更简单的解释方法。因为我们刚才的几何级数1+x+x^2+x^3+x^4+...=1/(1-x)，那么(1+x+x^2+x^3+x^4+...)^k就等于1/(1-x)^k。仔细想想k个(1+x+x^2+x^3+x^4+...)相乘是什么意思。(1+x+x^2+x^3+x^4+...)^k的展开式中，n次项的系数就是我们的答案，因为它的这个系数是由原式完全展开后k个指数加起来恰好等于n的项合并起来得到的。

    现在我们引用《组合数学》上暴经典的一个例题。很多书上都会有这类题。
    我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿n个水果的方案数。
    结合刚才的k个(1+x+x^2+x^3+x^4+...)相乘，我们也可以算出这个问题的生成函数。

g(x)=(1+x^2+x^4+...)(1+x^5+x^10+..)(1+x+x^2+x^3+x^4)(1+x)
    =[1/(1-x^2)]*[1/(1-x^5)]*[(1-x^5)/(1-x)]*(1+x) （前两个分别是公比为2和5的几何级数，
                                                     第三个嘛，(1+x+x^2+x^3+x^4)*(1-x)不就是1-x^5了吗）
    =1/(1-x)^2   （约分，把一大半都约掉了）
    =(1-x)^(-2)=C(1,0)+C(2,1)x+C(3,2)x^2+C(4,3)x^3...   （参见刚才对1/(1-x)^k的展开）
    =1+2x+3x^2+4x^3+5x^4+....

    于是，拿n个水果有n+1种方法。我们利用生成函数，完全使用代数手段得到了答案！
    如果你对1/(1-x)^k的展开还不熟悉，我们这里再介绍一个更加简单和精妙的手段来解释1/(1-x)^2=1+2x+3x^2+4x^3+5x^4+....。
    1/(1-x)=1+x+x^2+x^3+x^4+...是前面说过的。我们对这个式子等号两边同时求导数。于是，1/(1-x)^2=1+2x+3x^2+4x^3+5x^4+....。一步就得到了我们所需要的东西！不断地再求导数，我们同样可以得到刚才用复杂的牛顿二项式定理得到的那个结论（自己试试吧）。生成函数还有很多其它的处理手段，比如等式两边同时乘以、除以常数（相当于等式右边每一项乘以、除以常数），等式两边同时乘以、除以一个x（相当于等式右边的系数“移一位”），以及求微分积分等。神奇的生成函数啊。
    我们用两种方法得到了这样一个公式：1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+k-1,k)x^k+...。这个公式非常有用，是把一个生成函数还原为数列的武器。而且还是核武器。


    接下来我们要演示如何使用生成函数求出Fibonacci数列的通项公式。
    Fibonacci数列是这样一个递推数列：f(n)=f(n-1)+f(n-2)。现在我们需要求出它的生成函数g(x)。g(x)应该是一个这样的函数：
    g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+...
    等式两边同时乘以x，我们得到：
    x*g(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+...
    就像我们前面说过的一样，这相当于等式右边的所有系数向右移动了一位。
    现在我们把前面的式子和后面的式子相加，我们得到：
    g(x)+x*g(x)=x+2x^2+3x^3+5x^4+8x^5+...
    把这最后一个式子和第一个式子好好对比一下。如果第一个式子的系数往左边移动一位，然后把多余的“1”去掉，就变成了最后一个式子了。由于递推函数的性质，我们神奇地得到了：g(x)+x*g(x)=g(x)/x-1。也就是说，g(x)*x^2+g(x)*x-g(x)=-x。把左边的g(x)提出来，我们有：g(x)(x^2+x-1)=-x。于是，我们得到了g(x)=x/(1-x-x^2)。
    现在的任务是要把x/(1-x-x^2)还原成通项公式。这不是我们刚才的1/(1-x)^n的形式，我们要把它变成这种形式。我们发现，1-x-x^2=[1-(1-√5)x/2]*[1-(1+√5)x/2] （(1-√5)/2和(1+√5)/2是怎么算出来的？显然它们应该是x^2-x-1=0的两个根）。那么x/(1-x-x^2)一定能表示成?/[1-(1-√5)x/2]+?/[1-(1+√5)x/2]的形式（再次抱歉，输入数学公式很麻烦，将就看吧）。这是一定可以的，因为适当的?的取值可以让两个分式通分以后分子加起来恰好为一个x。?取值应该是多少呢？假设前面一个?是c1，后面那个是c2，那么通分以后分子为c1*[1-(1+√5)x/2]+c2*[1-(1-√5)x/2]，它恰好等于x。我们得到这样两个式子：常数项c1+c2=0，以及一次项-c1*(1+√5)/2-c2*(1-√5)/2=1。这两个式子足够我们解出c1和c2的准确值。你就不用解了，我用的Mathematica 5.0。解出来c1=-1/√5，c2=1/√5。你不信的话你去解吧。现在，我们把x/(1-x-x^2)变成了-(1/√5)/[1-(1-√5)x/2] + (1/√5)/[1-(1+√5)x/2]。我们已经知道了1/[1-(1-√5)x/2]的背后是以(1-√5)/2为公比的等比数列，1/[1-(1+√5)x/2]所表示的数列公比为(1+√5)/2。那么，各乘以一个常数，再相加，我们就得到了Fibonacci数列的通项公式：f(n)=-(1/√5)*[(1-√5)/2]^n + (1/√5)*[(1+√5)/2]^n。或许你会问，这么复杂的式子啊，还有根号，Fibonacci数列不都是整数吗？神奇的是，这个充满根号的式子对于任何一个自然数n得到的都是整数。熟悉用特征方程解线性递推方程的同学应该知道，以上过程实质上和找特征根求解没有区别。事实上，用上面所说的方法，我们可以求出任何一个线性齐次递推方程的通项公式。什么叫做线性齐次递推呢？就是这样的递推方程：f(n)等于多少个f(n-1)加上多少个f(n-2)加上多少个f(n-3)等等。Fibonacci数列的递推关系就是线性齐次递推关系。

    我们最后看一个例子。我们介绍硬币兑换问题：我有1分、2分和5分面值的硬币。请问凑出n分钱有多少种方法。想一下刚才的水果，我们不难得到这个问题的生成函数：g(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+...)(1+x^5+x^10+..)=1/[(1-x)(1-x^2)(1-x^5)]。现在，我们需要把它变成通项公式。我们的步骤同刚才的步骤完全相同。我们把(1-x)(1-x^2)(1-x^5)展开，得到1-x-x^2+x^3-x^5+x^6+x^7-x^8。我们求出-1+x+x^2-x^3+x^5-x^6-x^7+x^8=0的解，得到了以下8个解：-1,1,1,1,-(-1)^(1/5),(-1)^(2/5),-(-1)^(3/5),(-1)^(4/5)。这个不是我解出来的，我还是用的Mathematica 5.0。不是我不想解，而是我根本不会解这个8次方程。这也是为什么信息学会涉及这些东西的原因：次数稍微一高，只好交给计算机解决了。于是，(1-x)(1-x^2)(1-x^5)=(1+x)(1-x)^3(1+(-1)^(1/5) x)()()() （省略不写了）。注意那个(1-x)^3。由于等根的出现，我们不得不把(1-x)^3所包含的(1-x)和(1-x)^2因子写进一会儿的分母里，不然会导致解不出合适的c来。你可以看到很多虚数。不过没关系，这些虚数同样参与运算，就像刚才的根式一样不会影响到最后结果的有理性。然后，我们像刚才一样求出常数满足1/(1-x)(1-x^2)(1-x^5)=c1/()+c2/(1-x)+c3/(1-x)^2+c4/(1-x)^3...+c8/()。这个解太复杂了，我用Mathematica解了几分钟，打印出了起码几十KB的式子。虽然复杂，但我确实是得到了通项公式。你有兴趣的话可以尝试用Mathematica解决一下1/[(1-x)(1-x^3)] （只有1分和3分的硬币）。解c的值时可以用SolveAlways[]函数。你可以亲眼见到，一个四五行的充满虚数的式子最后总是得到正确的整数答案。

    生成函数还有很多东西，推导Catalan数列啊，指数生成函数啊，之类的。我有空再说吧，已经5000多个字了。

    huyichen一直在问那道题。很显然，那道题目和上面的兑换硬币有些联系。事实上，很多与它类似的题目都和生成函数有关。但那个题却没有什么可以利用生成函数的地方（或许我没想到吧）。或许每个max的值有什么方法用生成函数解出来，但整个题目是不大可能用生成函数解决的。
    近来有个帖子问一道“DP天牛”题目的。那个题目也是这样，很多与它类似的题目都和DP有关，但那道题却不大可能动规。我总觉得它可以归约到装箱问题（考虑体积关系，最少要几个箱子才能把物品放完），而后者貌似属于NPC。或许我错了吧，现在没事就在研究理论的东西，很久没有想过OI题了，这方面的能力已经开始退化了。

Matrix67原创
做人要厚道，转贴请注明出处

Aronson's sequence:
1, 4, 11, 16, 24, 29, 33, 35, 39, 45, 47, 51, 56, 58, 62, 64, ...
whose definition is:
T is the first, fourth, eleventh, ... letter of this sentence

0, 0, 0, 0, 4, 9, 5, 1, 1, 0, 55, 55, 1, 0, 1, 9, 5, 1, 1, 0, ...
这个比较强：把1,2,3,4,5, ...写成英文
one, two, three, four, five, six, seven, eigth, nine, ten
然后删掉除c,d,i,l,m,v,x以外的字母，变成罗马数字。

Golomb's sequence:
1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,9,10,10,10,10,10 ...
定义：a(1)=1, a(n)表示n在这个数列里出现的次数

Emirps:
13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199, ...
就是一个Prime（质数）倒过来写也是质数

'Eban' numbers (the letter 'e' is banned!).
2, 4, 6, 30, 32, 34, 36, 40, 42, 44, 46, 50, 52, 54, 56, 60, 62, 64, 66, 2000, 2002, 2004, 2006, 2030, 2032, 2034, 2036, 2040, ...

考大家一道题。
这是一个比较著名的数列：

2,
271,
2718281,
2718281828459045235360287471352662497757247093699959574966967627724076630353547594571,
......

能看出这个数列是个什么东西的人高考加20分。
事实上，这个规律是可以用不到一秒的时间一眼看出的（如果你对那个够熟悉）。

The On-Line Encyclopedia of Integer Sequences:
http://www.research.att.com/~njas/sequences/

    输入数列的若干数字，查找有关的数列。
    什么鬼数列都有。
    居然连1,11,21,1211,111221,312211,13112221……也有，并起了名字叫做Look and Say sequence
    以后不愁做找数字规律的题了。