hdu 2604 Queuing£¨¾ØÕóÓÅ»¯µÝÍƹ«Ê½£©

Queuing

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2842 Accepted Submission(s): 1305


Problem Description Queues and Priority Queues are data structures which are known to most computer scientists. The Queue occurs often in our daily life. There are many people lined up at the lunch time.

Now we define that ¡®f¡¯ is shZ†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcnQgZm9yIGZlbWFsZSBhbmQgoa5toa8gaXMgc2hvcnQgZm9yIG1hbGUuIElmIHRoZSBxdWV1ZaGvcyBsZW5ndGggaXMgTCwgdGhlbiB0aGVyZSBhcmUgMjxzdXA+TDwvc3VwPiBudW1iZXJzIG9mIHF1ZXVlcy4gRm9yIGV4YW1wbGUsIGlmIEwgPSAyLCB0aGVuIHRoZXkgYXJlIGZmLCBtbSwgZm0sIG1mIC4gSWYgdGhlcmUgZXhpc3RzIGEgc3VicXVldWUgYXMgZm1mIG9yIGZmZiwgd2UgY2FsbCBpdCBPLXF1ZXVlCiBlbHNlIGl0IGlzIGEgRS1xdWV1ZS48YnI+CllvdXIgdGFzayBpcyB0byBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBFLXF1ZXVlcyBtb2QgTSB3aXRoIGxlbmd0aCBMIGJ5IHdyaXRpbmcgYSBwcm9ncmFtLjxicj4KCgogCjxicj4KCklucHV0CgpJbnB1dCBhIGxlbmd0aCBMICgwIDw9IEwgPD0gMTAgPHN1cD42PC9zdXA+KSBhbmQgTS4KCiAKPGJyPgoKT3V0cHV0CgpPdXRwdXQgSyBtb2QgTSgxIDw9IE0gPD0gMzApIHdoZXJlIEsgaXMgdGhlIG51bWJlciBvZiBFLXF1ZXVlcyB3aXRoIGxlbmd0aCBMLgoKIAo8YnI+CgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"brush:java;">3 8 4 7 4 8
Sample Output

6
2
1

Author WhereIsHeroFrom
µÝÍƹ«Ê½f(n)=f(n-1)+f(n-3)+f(n-4) µÝÍƹý³Ì£º ÏÖÔÚÉ賤¶ÈΪn 1£¬ÔÚ×îºóһλ¼Ómʱ£¬Ç°ÃæÎÞÂÛÊÇʲô¶¼Âú×㣬µÃf(n-1); 2£¬ÔÚ×îºóһλ¼Ófʱ£¬µ¹Êýºó2λÎÞÂÛ¼Óʲô¶¼²»ÄÜÂú×㣬ÓÚÊÇÌÖÂÛµ¹Êýºó3룬ºó3λ¿ÉÒÔ¼Ómmf,ÏÖÔÚ»¹ÓÐÒ»ÖÖÇé ¿öû¿¼Âǵ½£¬ÄǾÍÊÇmff£¬¿ÉÄÜÇ°ÃæÊÇÒÔf½á⣬ÓÚÊÇÌÖÂÛµ¹Êýºó4룬ÔÚºó4λÉϼÓmmff¡£ µÃµ½µÝÍƹ«Ê½¾Í¿ÉÒÔ¹¹Ôì¾ØÕóÁË¡£

´úÂ룺

#include 
#include 
#include 
#include 
using namespace std;
struct matrix
{
    int ma[10][10];
};
int mod;
matrix multi(matrix x,matrix y)
{
    matrix ans;
    memset(ans.ma,0,sizeof(ans.ma));
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            if(x.ma[i][j])
            {
                for(int k=1;k<=4;k++)
                {
                    ans.ma[i][k]=(ans.ma[i][k]+(x.ma[i][j]*y.ma[j][k])%mod)%mod;
                }
            }
        }
    }
    return ans;
}
matrix pow(matrix a,int k)
{
    matrix ans;
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            if(i==j)
            ans.ma[i][j]=1;
            else
            ans.ma[i][j]=0;
        }
    }
    while(k)
    {
        if(k&1)
        ans=multi(ans,a);
        a=multi(a,a);
        k=k>>1;
    }
    return ans;
}
int main()
{
    int n;
    while(~scanf("%d%d",&n,&mod))
    {
        matrix a,b;
        memset(a.ma,0,sizeof(a.ma));
        memset(b.ma,0,sizeof(b.ma));
        a.ma[1][1]=a.ma[1][3]=a.ma[1][4]=1;
        a.ma[2][1]=a.ma[3][2]=a.ma[4][3]=1;
        b.ma[1][1]=6;
        b.ma[2][1]=4;
        b.ma[3][1]=2;
        b.ma[4][1]=1;
        if(n==0)
        {
            printf("%d\n",1%mod);
            continue;
        }
        if(n==1)
        {
            printf("%d\n",2%mod);
            continue;
        }
        if(n==2)
        {
            printf("%d\n",4%mod);
            continue;
        }
        if(n==3)
        {
            printf("%d\n",6%mod);
            continue;
        }
        a=pow(a,n-3);
        b=multi(a,b);
        printf("%d\n",b.ma[1][1]);
    }
    return 0;
}