EOJ 1031 传球问题

EOJ 1031 http://acm.cs.ecnu.edu.cn/problem.php?problemid=1031

题意：

　　传球问题，按题意我们得到编号从1~2~..~ i ~..~n~1的环，那么去掉末尾的1（将环从n后剪开），

　　我们得到：1~2~..~ i ~..~n，多了首尾不同的限制，于是问题完全等价 HDU　2045 —— 染色问题（做过这题的话，很容易想到）。

　　HDU　2045　　http://acm.hdu.edu.cn/showproblem.php?pid=2045

　　具体分析：

　　n为传球总次数，i 一个空位， 待填入接到第 i-1 次传球的人；

　　又有p个人，记为x1,x2...,xp;按题意：编号1处只有一种选择，不妨填x1，而2~n可以有多种填法， 但须有相邻（包括首尾）的不同。

　　以下用填格子指代传球。

　　记f[n]为填到第 n 个格子时的总填法。那么分为两种：(n>=3)

　　按照　　第n-1个格子与首位　　的关系；

　　1.相同：第n-1个格子——1种填法=>第n个格子——p-1种；剩下前n-2个格子为子问题f[n-2]。

　　2.不同：第n-1个格子——p-1种填法=>第n个格子——p-2种；

　　　　　　（由于第n-1个格子与首位不同）这时，前n-1个格子本身即为子问题f[n-1]。

　　这样容易写出递推关系：

　　f[n] = (p-1)*f[n-2] + (p-2)*f[n-1];　　　

　　题意要求结果对2005取模：那么只需：

　　f[n] = ( ((p-1)%M) * f[n-2]  + ((p-2)%M) * f[n-1] )%M;　　//M为2005

　　此题的另一个要注意的是：n, p 都很大，不能暴力求解。　　

　　注意到　f[n] = (p-1)*f[n-2] + (p-2)*f[n-1];　<=>　　f[n] = A*x^n + B*y^n; (A,B,x,y∈N）。

　　由抽屉原理：设a[n] = （A*x^n）%M;　M为某常数，　则a[n]一定循环(n>M 时)，循环节最大为M;

　　B*y^n同理,　所以f[n]循环节最大为M^2;

　　代码如下：

　　

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#define INF 0x3f3f3f 
#define MAX 2010
#define M 2005
using namespace std;
short f[MAX*MAX];
void print(int *f)
{
    for(int i=1; i<=10; i++)
        cout << i << ". " << f[i] << endl;
}
int main()
{
    //freopen("testin.txt", "r", stdin);
    //freopen("testout.txt", "w", stdout);
    
    int p, n;
    while(cin >> p >> n, p&&n)
    {
        int i;
        f[1] = 0;
        f[2] = (p-1)%M;
        for(i=3; i<=n; i++)
        {            
            f[i] = (((p-1)%M)*f[i-2] + ((p-2)%M)*f[i-1])%M;
            if(f[i-1] == f[1] && f[i] == f[2])
                break;    //当循环时即可跳出。 
        }
        //print(f);
        if(i<n)        //循环 
        {
            int loop = i-2; 
            int ans = n%loop;
            if(n%loop == 0)
                ans = loop;
            cout << f[ans] << endl;
        }
        else    //n较小，未循环  
            cout << f[n] << endl;
    } 
    
    
    return 0;
}