[NOIP][dp矩陣解] 2008 3.传球游戏＠Morris' Blog

2012-09-05 08:32:47| 人氣511| 回應0 | 上一篇 | 下一篇

[NOIP][dp矩陣解] 2008 3.传球游戏

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师在此吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。
聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有 1->2->3->1和1->3->2->1，共2种。

輸入說明：

输入共一行，有两个用空格隔开的整数n，m（3<=n<=30，1<=m<=30）。

輸出說明：

输出文件共一行，有一个整数，表示符合题意的方法数。

範例輸入：

3 3

範例輸出：

提示：

背景知識： DP

DP

出處：

NOIP 2008 普及组复赛 (管理：danta)

將題目構成一個無向圖, 就只是詢問 i->i 走幾步, 將矩陣乘法得 m 次即可

#include <stdio.h>
#include <string.h>
typedef struct {
    int v[30][30];
} matrix;
matrix In;
matrix multiply(matrix a, matrix b, int n) {
    static matrix c;
    static int i, j, k;
    memset(&c, 0, sizeof(matrix));
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            for(k = 0; k < n; k++)
                c.v[i][j] += a.v[i][k]*b.v[k][j];
    return c;
}
void solve(int n, int m, matrix A) {
    matrix x = In, y = A;
    while(m) {
        if(m&1)
            x = multiply(x, y, n);
        m /= 2;
        y = multiply(y, y, n);
    }
    printf("%d\n", x.v[0][0]);
}
int main() {
    int n, m, i;
    memset(&In, 0, sizeof(matrix));
    for(i = 0; i < 30; i++)
        In.v[i][i] = 1;
    matrix A;
    while(scanf("%d %d", &n, &m) == 2) {
        memset(&A, 0, sizeof(matrix));
        for(i = 0; i < n; i++) {
            A.v[i][(i+1)%n] = 1;
            A.v[i][(i-1+n)%n] = 1;
        }
        solve(n, m, A);
    }
    return 0;
}

我要檢舉

#d105#NOIP#2008#3.传球游戏

台長： Morris

您可能對以下文章有興趣

d907. 3. 城市走法計數

d780. NOIP2009 4.靶形数独

[ZJ][DP] a365. 3. 新井字遊戲

[ZJ][Math] a348. 1. 貪食蛇

人氣(511) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][模擬、旋轉] b125. 積木的拼疊問題（Bricks）
此分類上一篇:[NOIP][dfs爛解] 2004 4.火星人

回應(0)