首页 > ACM题库 > HDU-杭电 > HDU 3802-Ipad,IPhone-最小生成树-[解题报告]HOJ
2015
04-13

HDU 3802-Ipad,IPhone-最小生成树-[解题报告]HOJ

Ipad,IPhone

问题描述 :

In ACM_DIY, there is one master called “Lost”. As we know he is a “-2Dai”, which means he has a lot of money.
  

Well, Lost use Ipad and IPhone to reward the ones who solve the following problem.
  

In this problem, we define F( n ) as :
  

Then Lost denote a function G(a,b,n,p) as

Here a, b, n, p are all positive integer!
If you could tell Lost the value of G(a,b,n,p) , then you will get one Ipad and one IPhone!

输入:

The first line is one integer T indicates the number of the test cases. (T <= 100)
Then for every case, only one line containing 4 positive integers a, b, n and p.
(1 ≤a, b, n, p≤2*109 , p is an odd prime number and a,b < p.)

输出:

The first line is one integer T indicates the number of the test cases. (T <= 100)
Then for every case, only one line containing 4 positive integers a, b, n and p.
(1 ≤a, b, n, p≤2*109 , p is an odd prime number and a,b < p.)

样例输入:

4
2 3 1 10007
2 3 2 10007
2 3 3 10007
2 3 4 10007

样例输出:

40
392
3880
9941

< [if gte mso 9]>MicrosoftInternetExplorer402DocumentNotSpecified7.8Normal0

Ipad,IPhone

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)


Total Submission(s): 0    Accepted Submission(s): 0



Problem Description

In ACM_DIY, there is one master called “Lost”. As we know he is a “-2Dai”, which means he has a lot of money.

Ipad,IPhone

 



Well, Lost use Ipad and IPhone to reward the ones who solve the following problem.

Ipad,IPhone

 



In this problem, we define F( n ) as :

Ipad,IPhone

 



Then Lost denote a function G(a,b,n,p) as

Ipad,IPhone

 



Here a, b, n, p are all positive integer!


If you could tell Lost the value of G(a,b,n,p) , then you will get one Ipad and one IPhone!

Input

The first line is one integer T indicates the number of the test cases. (T <= 100)


Then for every case, only one line containing 4 positive integers a, b, n and p.


(1 ≤a, b, n, p≤2*10
9
 , p is an odd prime number and a,b < p.)

Output

Output one line,the value of the G(a,b,n,p) .

Sample Input

2 3 1 10007 

2 3 2 10007 

2 3 3 10007 

2 3 4 10007

Sample Output

40 

392 

3880 

9941

Author

AekdyCoin

Source

ACM-DIY Group Contest 2011 Spring

Recommend

notonlysuccess

先膜拜下AC

1004
……

这题错了好多次……orz
,没有注意到负数的取余,表示遗憾。

首先应该知道这么个公式

Ipad,IPhone

感谢zsasuke提出的错误,后来查了一下,这个公式的使用是有前提条件的:“c>phi(p)”,所以需要加个判断,如果c<=phi(p),说明c次方在O(logc)的范围内可以得出结果,因此可以直接暴力求解,大于的话才使用这个公式,对于这个公式的正确性我这几天试着证明下,是在别人的解题报告里看的这个公式,做FOJ1759的时候记下来的,并没有证明……

还有p是质数(题目给定的,没发现,感谢bstw111提出)所以phi(p)=p-1。

 

所以Fib(n)
次方就可以处理了。

对于后面那坨……

Ipad,IPhone


注意对于zn
的矩阵可能系数为负的,不能直接取模……

代码如下,表示写的很丑- -|||

#include <stdio.h>
#include <math.h>
#include <string.h>
typedef struct
{
__int64 m[2][2];
}Matrix;
bool check[200005];
__int64 prime[100000];
__int64 up;
__int64 a,b,n,p,ok;
__int64 Fumod(__int64 t,__int64 mod)
{
while(t<0)
{
t=t+mod*1000000;
}
t=t%mod;
return t;
}
Matrix Mul(Matrix x,Matrix y,__int64 mod)
{
__int64 i,j,k;
Matrix ret;
for (i=0;i<2;i++)
{
for (j=0;j<2;j++)
{
ret.m[i][j]=0;
for (k=0;k<2;k++)
{
ret.m[i][j]=(ret.m[i][j]+x.m[i][k]*y.m[k][j]);
if (ret.m[i][j]>=mod) ok=1;
}
if (ret.m[i][j]>=0) ret.m[i][j]%=mod;
else
{
ret.m[i][j]=Fumod(ret.m[i][j],mod);
}
}
}
return ret;
}
__int64 Fib(__int64 t,__int64 mod)
{
Matrix x,ans;
x.m[0][0]=x.m[0][1]=x.m[1][0]=1;
x.m[1][1]=0;
ans.m[0][0]=1;
ans.m[0][1]=ans.m[1][0]=ans.m[1][1]=0;
while(t!=0)
{
if (t & 1)
{
ans=Mul(x,ans,mod);
}
t>>=1;
x=Mul(x,x,mod);
}
return ans.m[0][0];
}
void Pri()
{
__int64 i,k,j;
up=0;
memset(check,true,sizeof(check));
for (i=2;i<=200000;i++)
{
if (check[i]==false) continue;
for (j=i;i*j<=200000;j++)
{
check[i*j]=false;
}
prime[up++]=i;
}
}
__int64 CountZ(__int64 t,__int64 mod)
{
Matrix x,ans;
x.m[0][0]=2*(a+b)%mod;
x.m[0][1]=Fumod(-(a-b)*(a-b),mod);
x.m[1][0]=1;
x.m[1][1]=0;
ans.m[0][0]=2*(a+b)%mod;
ans.m[1][0]=2;
ans.m[0][1]=ans.m[1][1]=0;
while(t!=0)
{
if (t & 1)
{
ans=Mul(x,ans,mod);
}
t>>=1;
x=Mul(x,x,mod);
}
return ans.m[0][0];
}
__int64 FMul(__int64 x,__int64 t,__int64 mod)
{
__int64 ans=1;
while(t!=0)
{
if (t & 1)
{
ans=ans*x%mod;
}
t>>=1;
x=(x*x)%mod;
}
return ans;
}
int main()
{
__int64 i,j,T,f,z,amul,bmul,php;
scanf("%I64d",&T);
Pri();
while(T--)
{
scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&p);
ok=0;
php=p-1;
f=Fib(n,php);
if (ok==1) f+=php;
z=CountZ(f-1,p);
amul=(FMul(a,(p-1)/2,p)+1);
bmul=(FMul(b,(p-1)/2,p)+1);
printf("%I64d/n",(amul*bmul%p)*z%p);
}
return 0;
}
 

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

参考:http://blog.csdn.net/magicnumber/article/details/6280257


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  3. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }