矩阵的第i行是其上一行循环右移的结果
性质
循环矩阵的线性运算及乘积仍是循环矩阵循环矩阵的逆矩阵以及转置矩阵仍是循环矩阵循环矩阵乘法满足交换律
优势
由于两个循环矩阵的乘法的结果仍然是一个循环矩阵，所以可以$O(n^2)$求得结果的第一行，这样就可以得到其他各行的结果，将矩阵乘法的复杂度下降了一级若下标从0开始：$c[1][(i+j)$ % $n] += a[1][i] * b[1][j]$若下标从1开始：$c[1][(i+j-2)$ % $(n+1)] += a[1][i] * b[1][j]$
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
| struct cirmat
{
int mat[N];
cirmat() {}
cirmat(int _) : n(_) { memset(mat, 0, sizeof(mat)); }
cirmat() { memset(mat, 0, sizeof(mat)); }
void one() { mat[0] = 1; }
};
cirmat operator * (cirmat a, cirmat b)
{
cirmat res;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
(res.mat[(i+j-2)%n+1] += 1ll*a.mat[i]*b.mat[j]%mod) %= mod;
return res;
}
cirmat operator ^ (cirmat a, ll x)
{
cirmat res; res.one();
while(x)
{
if(x&1) res = res * a;
a = a * a;
x >>= 1;
}
return res;
}
|
bzoj2510 弱题
有m个带标号球，标号范围为1-n，每次操作等概率选择一个球，使得该球的标号加1（如果是n，就变成1）问k次操作后，各个标号球的个数的期望$n \leq 1000,m \leq 10^9,k \leq INT\_MAX$转移矩阵是一个循环矩阵
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n, m, k;
struct cirmat
{
double mat[N];
cirmat() { memset(mat, 0, sizeof(mat)); }
void one() { mat[0] = 1.0; }
}a, b;
cirmat operator * (cirmat a, cirmat b)
{
cirmat res;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
res.mat[(i+j)%n] += a.mat[i]*b.mat[j];
return res;
}
cirmat operator ^ (cirmat a, int x)
{
cirmat res; res.one();
while(x)
{
if(x&1) res = res * a;
a = a * a;
x >>= 1;
}
return res;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i=0; i<n; i++) scanf("%lf", &a.mat[i]);
b.mat[0] = 1.0 - 1.0/m, b.mat[1] = 1.0/m;
b = b ^ k;
a = a * b;
for(int i=0; i<n; i++) printf("%.3f\n", a.mat[i]);
return 0;
}
|
牛客14532 没有名字
转移是一个循环矩阵
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
| #include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int mod = 1e9 + 7, N = 205;
int n, k;
ll m;
struct cirmat
{
int mat[N];
cirmat() { memset(mat, 0, sizeof(mat)); }
void one() { mat[1] = 1; }
}a, b;
cirmat operator * (cirmat a, cirmat b)
{
cirmat res;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
(res.mat[(i+j-2)%n+1] += 1ll*a.mat[i]*b.mat[j]%mod) %= mod;
return res;
}
cirmat operator ^ (cirmat a, ll x)
{
cirmat res; res.one();
while(x)
{
if(x&1) res = res * a;
a = a * a;
x >>= 1;
}
return res;
}
void solve()
{
scanf("%d%lld%d", &n, &m, &k);
for(int i=1; i<=n; i++) scanf("%d", &a.mat[i]);
for(int i=1; i<=n; i++)
{
int dis = min(i-1, n+1-i);
if(i==1 || dis>=k) b.mat[i] = 0;
else b.mat[i] = k - dis;
}
b = b ^ m;
a = a * b;
for(int i=1; i<=n; i++) printf("%d%c", a.mat[i], " \n"[i==n]);
}
int main()
{
int _; scanf("%d", &_);
while(_--) solve();
return 0;
}
|
另外，利用FFT还可以将循环矩阵乘法优化到$O(n\log n)$，还不会，先咕