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
*/