2015
04-13

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

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.

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!

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

1004
……

，没有注意到负数的取余，表示遗憾。

#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;
}



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;
}