首页 > ACM题库 > HDU-杭电 > HDU 4304-Let’s Hit Our Head!-数论-[解题报告]HOJ
2015
05-23

HDU 4304-Let’s Hit Our Head!-数论-[解题报告]HOJ

Let’s Hit Our Head!

问题描述 :

Kingdom LHOH is celebrating its annual carnival again!This time another crazy game is now on show.N*N piles of brick here lying on the ground in a straight line, and N brave fellows have attended.
First they should each choose a distinct piles brick to stand behind, forming a line parrelling to the brick, and facing the same side, watching at his piles of brick.
Then their captain can yelled out 3 commands, described below:
A "LEFT!" Every one should move so that he is behind the left piles of the original one.
B "RIGHT!" Every one should move so that he is behind the right piles of the original one.
C "HIT!" Every one should break all the piles of brick before him with only his head slamming them.

A little constraints are showed below:
In every step, when command A or B have been yelled out, no one should move outside, that is, for everyone after his moving, brick(even breaked up) is there before him,and when command C is to be yelled out, intact piles of brick must be there before every one, so that he cannot slamming brick that it already breaked up, and only that is fair to everyone.
Not until all piles of brick have been successfully breaked up with the brave fellows’ heads, this game is successfully finished.
Now the question is,the crazy captain wants to know how many initial options are there,satisfying for each initial option he always chooses the first piles, other members choose their own distinct ones,and the game can be finished successfully at the same time?
We assume the other members except the captain cannot be told out.

输入:

First there’s an integer T(T<=15000) indicating the scenary numbers.
Then there’s T lines represented for the scenaries, with an integer N(1<=N<=10^12) in each line.

输出:

First there’s an integer T(T<=15000) indicating the scenary numbers.
Then there’s T lines represented for the scenaries, with an integer N(1<=N<=10^12) in each line.

样例输入:

10
1
2
3
4
8
16
6469693228
6469693229
6469693230
1024

样例输出:

1
2
2
6
20
70
84
14
8787513806478134
184756

题意我觉得还是好理解的。 我感觉就是有n*n堆石头,有n个人,每人挑个石堆站在后面。

三种操作:http://acm.hdu.edu.cn/showproblem.php?pid=4304

     1. 人全部右移(石头不动)。

     2. 人全部左移。

     3. 将自己面前的石头全部用脑袋砸碎。

满足条件:

    1.左右移的时候不能移出去,就是每人面前都得有一堆石头,无论是坏的还是好的。

    2.砸的时候只能砸未砸过的石头。

最后将全部石头砸碎就行。 问第一堆石头必须有人站在后面的能成功的开始状态有几种。

然后题解就Orz,真不会了。莫名奇妙就转化成因数分解和排列了。

以下是多校解题报告:

这个问题等价于把N因数分解,不能有1
然后将序列交替组合的方案数算出来就可以了

比如6=2*3
我们有[6],[2,3],[3,2]
交替组合有
A6B6 B6A6
A2B6A3 A3B6A2 B2A6B3 B3A6B2
A2B2A3B3 A2B3A3B2 A3B3A2B2 A3B2A2B3
B2A2B3A3 B2A3B3A2 B3A3B2A2 B3A2B2A3
共14种

再比如8=2*2*2=2*4
我们有[8],[2,4],[4,2],[2,2,2]
交替组合有
A8B8 B8A8
A2B8A4 A4B8A2 B2A8B4 B4A8B2
A2B2A4B4 A2B4A4B2 A4B2A2B4 A4B4A2B2
B2A2B4A4 B2A4B4A2 B4A2B2A4 B4A4B2A2
A2B2A2B4A2 A2B4A2B2A2 B2A2B2A4B2 B2A4B2A2B2
A2B2A2B2A2B2 B2A2B2A2B2A2
共20种

#include <cstdio>
#include <cstring>

int coef[20],delt[20],inx[20],base[20];
int mark[1000010],pri[1000010],priN;
__int64 dp[2000][20];

void init()
{
    int i,j;
    for(i=2; i<=1000000; i++) mark[i]=i;
    for(i=2; i<=1000000; i++)
    {
        if(mark[i]==i) pri[priN++]=i;
        for(j=0; j<priN&&i*pri[j]<=1000000; j++)
        {
            mark[i*pri[j]]=pri[j];
            if(i%pri[j]==0) break;
        }
    }
}

void deal()
{
    __int64 u,ans,num,t,tmpv;
    int cnt,i,j,k,l,prod,tot,amn,m;
    scanf("%I64d", &u);
    for(cnt=0,num=u; num-1;)
    {
        if(num>1000000)
        {
            t=num;
            for(j=0; j<priN; j++)
            {
                if(num%pri[j]==0)
                {
                    t=pri[j];
                    break;
                }
            }
        }
        else t=mark[num];
        inx[cnt]=0;
        while(num%t==0) num/=t,inx[cnt]++;
        cnt++;
    }
    for(tot=0,prod=1,i=cnt-1; i>=0; i--)
    {
        tot+=inx[i],base[i]=prod,prod*=(inx[i]+1);
    }
    for(i=0; i<=tot; i++) for(j=0; j<prod; j++) dp[j][i]=0;
    dp[0][0]=1;
    for(i=1; i<prod; i++)
    {
        for(j=0; j<cnt; j++) delt[j]=i/base[j]%(inx[j]+1);
        for(j=prod-1; j>=0; j--)
        {
            amn=0x3fffffff;
            for(k=0; k<cnt; k++)
            {
                coef[k]=j/base[k]%(inx[k]+1);
                if(delt[k])
                {
                    tmpv=(inx[k]-coef[k])/delt[k];
                    if(tmpv<amn) amn=tmpv;
                }
            }
            for(l=1; l<=amn; l++)
            {
                for(k=0; k+l<=tot; k++)
                {
                    tmpv=dp[j][k];
                    for(m=1; m<=l; m++) tmpv*=m+k,tmpv/=m;
                    dp[j+i*l][k+l]+=tmpv;
                }
            }
        }
    }
    for(ans=dp[prod-1][tot]*dp[prod-1][tot],i=0; i<tot; i++)
    {
        ans+=(dp[prod-1][i]+dp[prod-1][i+1])*(dp[prod-1][i]+dp[prod-1][i+1]);
    }
    printf("%I64d\n", ans);
}

int main()
{
    init();
    int t;
    scanf("%d", &t);
    while(t--) deal();
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/julyana_lin/article/details/8066893