简单的传球游戏
Time Limit: 1000ms Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main
K(3<=K<=10^9)个人互相传球，某人接球后立即传给别人。假定初始状态球在甲手中，并将甲发球作为第一次传球过程。求经过N(N<=10^9)次传球后，球又回到甲手中的传球方案数，输出这个数模10^9+7后的结果。
Input
第一行是一个整数T(T<=20000)，表示测试数据的组数。
接下来T行，每行输入两个数N,K(3<=K<=10^9,1<= N<=10^9)。
Output
输出T行，每行输出一组N,K对应方案数模10^9+7后的结果。
Sample Input
23 33 4
Sample Output
26
Hint
第一组样例，N=3,K=3，三个人传三次的传球方式是：
1. A->B->C->A
2. A->C->B->A
Source
Author
sqy
题目链接：
转载请注明出处：
题目意思：有K个人相互传球，从甲开始到甲结束，传N次球。（注，自己不能传给自己）
分析与解答：设第n次传球后，球又回到甲手中的传球方法有a[n]种，可以想象前n-1次传球，如果每一次传球都任选其他K-1人中的一人进行传球，也就是每次传球都有K-1种可能，由乘法原理，共有(K-1)^(n-1)种 。这些传球方式并不完全符合条件，分为两类：一类是第n-1次恰好传到甲手中，有a[n-1]种，不符合条件，因为这样第n次就不能再传给甲了；另一类是第n-1次没在甲手里，第n次持球人再将球传给甲有a[n]种方法,根据加法原理有a[n-1]+a[n]=(K-1)^(n-1)由于甲是发球者，所以a[1]=0;利用递推关系可得
思路：an(n表示传n次球,回到甲手中的次数);
a1=0;
a2=(K-1)^1-a1;
a3=(K-1)^2-a2;
a4=(K-1)^3-a3;
......
这里特别注意，取余的时候，存在越界的情况，我也WA了好几次 T^T .
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define LL long long 7 #define mod 1000000007 8 struct matrix 9 {10 LL mat[2][2];11 };12 13 matrix multiply(matrix a,matrix b)14 {15 matrix c;16 memset(c.mat,0,sizeof(c.mat));17 for(int i=0;i<2;i++)18 {19 for(int j=0;j<2;j++)20 {21 if(a.mat[i][j]==0)continue;22 for(int k=0;k<2;k++)23 {24 if(b.mat[j][k]==0)continue;25 c.mat[i][k]+=a.mat[i][j]*b.mat[j][k]%mod;26 // c.mat[i][k]%=mod;27 if(c.mat[i][k]>mod) c.mat[i][k]-=mod;//果然这里超了。。。28 else if(c.mat[i][k]<0) c.mat[i][k]+=mod;29 }30 }31 }32 return c;33 }34 35 matrix quicklymod(matrix a,LL n)36 {37 matrix res;38 memset(res.mat,0,sizeof(res.mat));39 for(int i=0;i<2;i++) res.mat[i][i]=1;40 while(n)41 {42 if(n&1)43 res=multiply(a,res);44 a=multiply(a,a);45 n>>=1;46 }47 return res;48 }49 50 int main()51 {52 LL N,K;53 int T;54 scanf("%d",&T);55 while(T--)56 {57 scanf("%lld%lld",&N,&K);58 if(N==1){printf("0\n");continue;}59 //if(N==2){printf("%lld\n",K-1);continue;}60 61 matrix ans;62 ans.mat[0][0]=K-1;63 ans.mat[0][1]=0;64 ans.mat[1][0]=K-1;65 ans.mat[1][1]=-1;66 67 // ans=quicklymod(ans,N-2);68 // LL res=(((K-1)%mod)*(ans.mat[1][0]+ans.mat[1][1])%mod)%mod;69 // printf("%lld\n",res);70 ans=quicklymod(ans,N-1);71 printf("%lld\n",ans.mat[1][0]);72 }73 return 0;74 }
其他代码
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define LL long long 7 #define mod 1000000007 8 struct matrix 9 {10 LL mat[2][2];11 };12 13 matrix multiply(matrix a,matrix b)14 {15 matrix c;16 memset(c.mat,0,sizeof(c.mat));17 for(int i=0;i<2;i++)18 {19 for(int j=0;j<2;j++)20 {21 if(a.mat[i][j]==0)continue;22 for(int k=0;k<2;k++)23 {24 if(b.mat[j][k]==0)continue;25 c.mat[i][k]=(c.mat[i][k]+a.mat[i][j]*b.mat[j][k])%mod;26 }27 }28 }29 return c;30 }31 32 matrix quicklymod(matrix a,LL n)33 {34 matrix res;35 memset(res.mat,0,sizeof(res.mat));36 for(int i=0;i<2;i++) res.mat[i][i]=1;37 while(n)38 {39 if(n&1)40 res=multiply(a,res);41 a=multiply(a,a);42 n>>=1;43 }44 return res;45 }46 47 int main()48 {49 LL N,K;50 int T;51 scanf("%d",&T);52 while(T--)53 {54 scanf("%lld%lld",&N,&K);55 if(N==1){printf("0\n");continue;}56 // if(N==2){printf("%lld\n",K-1);continue;}57 58 matrix ans;59 ans.mat[0][0]=0;60 ans.mat[0][1]=K-1;61 ans.mat[1][0]=1;62 ans.mat[1][1]=K-2;63 64 ans=quicklymod(ans,N-1);65 // LL res=((K-1)*(ans.mat[1][0]+ans.mat[1][1])%mod)%mod;66 // printf("%lld\n",res);67 printf("%lld\n",ans.mat[0][1]);68 }69 return 0;70 }
1 #include2 #include 3 using namespace std; 4 long long pow(long long n,long long k) 5 { 6 long long res = 1; 7 while (k) 8 { 9 if (k&1) res = res*n%1000000007;10 n = n*n%1000000007;11 k >>= 1;12 }13 return res;14 }15 long long cal(long long n,long long k)16 {17 long long res = pow(k-1,n);18 if(res && n & 1)19 res = 1000000007 - res;20 res += (k-1);21 if (res >= 1000000007) res -= 1000000007;22 res = res * pow(k,1000000005)%1000000007;23 if(res && n & 1)24 res = 1000000007 - res;25 return res;26 }27 int main()28 {29 int _;30 long long N,K;31 scanf("%d",&_);32 while (_--)33 {34 scanf("%lld %lld",&N,&K);35 printf("%lld\n",cal(N,K));36 }37 return 0;38 }