解題區/解題區 - UVa

UVa 12761 - Blue Chips

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

N 個人圍繞一圈，每一個回合自身的分數為相鄰距離小於 D (不包含自己) 的權重總和 mod N。

請問在 K 個回合後，最大分數和擁有最大分數的人分別為何？

Sample Input

1
2
3
1
3 3 1
1 2 2

Sample Output

1
2
1
2 3

Solution

由於 K 很大，明顯地是一道矩陣 D&C。

把遞迴公式建造出來，可以在 O(N^3 log K) 時間內完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int mod = 10000;
struct Matrix {
    int v[64][64];
    int row, col; // row x col
    Matrix(int n, int m, int a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++) {
            for(int k = 0; k < col; k++) {
                if (v[i][k])
                    for(int j = 0; j < x.col; j++) {
                        ret.v[i][j] += v[i][k] * x.v[k][j],
                        ret.v[i][j] %= mod;
                    }
            }
        }
        return ret;
    }
    Matrix operator+(const Matrix& x) const {
        Matrix ret(row, col);
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                ret.v[i][j] = v[i][j] + x.v[i][j];
            }
        }
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
    Matrix powsum(int k) {
        if (k == 0) return Matrix(row, col, 0);
        Matrix vv = powsum(k/2);
        if (k&1) {
            return vv * (Matrix(row, col, 1) + vv) + vv;
        } else {
            return vv * (Matrix(row, col, 1) + vv);
        }
    }
};
int main() {	
    freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout); 
    int testcase, N, K, D;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &D);
        mod = N;
        Matrix m(N, N), a(N, 1);
        for (int i = 0; i < N; i++)
            scanf("%d", &a.v[i][0]), a.v[i][0] %= N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if ((abs(i - j) <= D || N - abs(i - j) <= D) && i != j)
                    m.v[i][j] = 1;
            }
        }
        Matrix ret = (m ^ K);
        ret = ret * a;
        int mn = 0x3f3f3f3f;
        for (int i = 0; i < N; i++) {
            mn = min(mn, ret.v[i][0]);
        }
        printf("%d\n", mn);
        int f = 0;
        for (int i = 0; i < N; i++) {
            if (ret.v[i][0] == mn) {
                if (f)  putchar(' ');
                f = 1;
                printf("%d", i + 1);
            }
        }
        puts("");
    }
    return 0;
}
/*
 1
 3 3 1
 1 2 2
 */