簡單的傳球游戲（矩陣），傳球游戲矩陣
簡單的傳球游戲
1000ms 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
2
3 3
3 4
Sample Output
2
6
Hint
第一組樣例，N=3,K=3，三個人傳三次的傳球方式是：
1. A->B->C->A
2. A->C->B->A
Source
第十三屆北京師范大學程序設計競賽決賽
Author
sqy
題目鏈接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=49104
轉載請注明出處：http://blog.csdn.net/u010579068
題目意思：有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 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
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 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
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 }
View Code
![]()
1 #include<stdio.h>
2 #include<algorithm>
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 }
View Code
