# 传球游戏

2021-07-18 07:53:55 mrclr

【问题描述】

【输入】

【输出】

【输入输出样例】
ball.in ball.out
3 3 2
【限制】
40%的数据满足：3<=n<=30，1<=m<=20
100%的数据满足：3<=n<=30，1<=m<=30

``` 1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 typedef long long ll;
7 int n ,m;
8 ll f[35][35];
9 int main()
10 {
11     freopen("ball1.in", "r", stdin);
12     freopen("ball1.out", "w", stdout);
13     scanf("%d%d", &n, &m);　　//n人，m次
14     f[0][0] = 1;　　//这种情况方案数1
15     for(int i = 1; i <= m; ++i)
16     {
17         for(int j = 0;j < n; ++j)
18         {
19             f[i][j] = f[i - 1][(j + n - 1) % n] + f[i - 1][(j + 1) % n];
20         }
21     }
22     printf("%lld\n", f[m][0]);
23     return 0;
24 }```

``` 1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 using namespace std;
6 const int maxn = 35;
7 const int mod = 10000;            //对10000取模
8 int n, m;
9 struct Mat{
10     int a[maxn][maxn];
11     Mat operator * (const Mat& other)const{        //改一下乘号，使两个矩阵能相乘
12         Mat ans; memset(ans.a, 0, sizeof(ans.a));
13         for(int i = 0; i < n; ++i)
14             for(int j = 0; j < n; ++j)
15                 for(int k = 0; k < n; ++k)
16                 {
17                     ans.a[i][j] += a[i][k] * other.a[k][j];
18                     ans.a[i][j] %= mod;
19                 }
20         return ans;
21     }
22 };
23 Mat quickpow(Mat A, int num)
24 {
25     Mat ret; memset(ret.a, 0, sizeof(ret.a));
26     for(int i = 0; i < n; ++i) ret.a[i][i] = 1;
27     while(num)
28     {
29         if(num % 2 == 1) ret = ret * A;
30         A = A * A;
31         num >>= 1;
32     }
33     return ret;
34 }
35 void init(Mat &X)        //初始化矩阵
36 {
37     memset(X.a, 0, sizeof(X.a));
38     X.a[0][1] = 1;X.a[0][n - 1] = 1;　　　　//第一行和最后一行手动初始化
39     X.a[n - 1][0] = 1;X.a[n - 1][n - 2] = 1;
40     for(int i = 1; i < n - 1; ++i)　　　　//中间的用for循环初始化
41     {
42         X.a[i][i - 1] = X.a[i][i + 1] = 1;
43     }
44     return;
45 }
46 int main()
47 {
48     scanf("%d%d", &n ,&m);
49     Mat A;
50     init(A);
51     Mat B = quickpow(A, m);
52     int ans = B.a[0][0];
53     printf("%d\n", ans);
54     return 0;
55 }```

https://blog.51cto.com/u_15234622/2830679