20220327-线性代数

0.5h	矩阵乘法	[TJOI2017]可乐	图上路径数	提高	https://www.luogu.com.cn/problem/P3758
1h	矩阵乘法	Recurrences,UVa10870	伴随矩阵	提高+	https://www.luogu.com.cn/problem/UVA10870
1h	矩阵乘法	USACO2007 Nov G. Cow Relays	Floyd 加速	提高+	https://www.luogu.com.cn/problem/P2886
1h	矩阵乘法	[2020-NOI Online #3 提高组] 魔法值	DP 加速	提高+	https://www.luogu.com.cn/problem/P6569
0.5h	矩阵乘法	CF691E Xor-sequences	DP 加速	提高	https://codeforces.com/contest/691/problem/E
0.5h	高斯消元	[JSOI2008]球形空间产生器	方程转换	提高+	https://www.luogu.com.cn/problem/P4035
0.5h	矩阵乘法	[TJOI2019]甲苯先生的字符串	路径统计	提高+	https://www.luogu.com.cn/problem/P5337
0.75h	高斯消元	乘积是平方数(Square, UVa11542)	异或方程	NOI-	https://www.luogu.com.cn/problem/UVA11542
2h	矩阵线段树	CF718C. Sasha and Array	斐波那契	NOI-	https://codeforces.com/problemset/problem/718/C
1h	矩阵乘法	Balkan OI 2009 - Reading	分层图	NOI-	https://www.luogu.com.cn/problem/P6841
0.25h	高斯消元	[JSOI2008]球形空间产生器	方程转换	提高+	https://www.luogu.com.cn/problem/P4035
1h	高斯消元	[SDOI2010] 外星千足虫	异或方程	提高+	https://www.luogu.com.cn/problem/P2447
1h	矩阵乘法	Recurrences,UVa10870	伴随矩阵	提高+	https://www.luogu.com.cn/problem/UVA10870

可乐

#include <bits/stdc++.h>
using namespace std;
const int MOD = 2017;
typedef long long ll;
typedef vector<int> vi;
struct Mat {
  int r, c;
  vector<vi> f;
  Mat(int _r, int _c) : r(_r), c(_c), f(r + 1, vi(c + 1)) {}
  Mat operator*(const Mat &b) const {
    Mat m(r, b.c);
    for (int i = 1; i <= m.r; ++i)
      for (int j = 1; j <= m.c; ++j)
        for (int k = 1; k <= m.c; ++k)
          (m.f[i][j] += f[i][k] * b.f[k][j] % MOD) %= MOD;
    return m;
  }
  Mat operator^(ll x) const {
    assert(r == c);
    Mat m = *this, p = *this;
    for (--x; x; x >>= 1, p = p * p)
      if (x & 1) m = m * p;
    return m;
  }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m, t;
  cin >> n >> m;
  ++n;
  Mat G(n, n), A(1, n);
  for (int u, v, i = 1; i <= m; ++i) cin >> u >> v, G.f[u][v] = G.f[v][u] = 1;

  for (int i = 1; i <= n; ++i) G.f[i][i] = 1;
  for (int i = 1; i < n; ++i) G.f[i][n] = 1;
  cin >> t;
  A.f[1][1] = 1, A = A * (G ^ t);
  int ans = 0;
  for (int i = 1; i <= n; ++i) (ans += A.f[1][i]) %= MOD;
  cout << ans << endl;
  return 0;
}

Recurrences(未完成)

Cow Relays

很容易想到 N 次矩阵乘法的思路，不同的是这次的是长度而不是方案数（所以是加法而不是乘法）、是最小值而不是总数，所以把*换成+，把+换成min。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (int)b; ++i)
const int MV = 205, INF = 0x7f7f7f7f;
typedef int Mat[MV][MV];
int sz;
void matmul(Mat A, Mat B, Mat C) {
  static Mat m;
  memset(m, 0x7f, sizeof(Mat));
  rep(i, 0, sz) rep(j, 0, sz) rep(k, 0, sz) {
    if (A[i][k] != INF && B[k][j] != INF)
      m[i][j] = min(m[i][j], A[i][k] + B[k][j]);
  }
  memcpy(C, m, sizeof(Mat));
}
void matpow(Mat A, int n, Mat r) {
  Mat a;
  memcpy(a, A, sizeof(a));
  memcpy(r, A, sizeof(Mat));
  --n;
  for (int i = 0; (1 << i) <= n; ++i) {
    if (n & (1 << i)) matmul(r, a, r);
    matmul(a, a, a);
  }
}
map<int, int> ID;
int getId(int u) {
  if (!ID.count(u)) ID[u] = sz++;
  return ID[u];
}
Mat G, Ans;
int main() {
  int N, T, S, E;
  cin >> N >> T >> S >> E;
  sz = 0, memset(G, 0x7f, sizeof(G));
  for (int i = 1, u, v, w; i <= T; ++i) {
    cin >> w >> u >> v;
    u = getId(u), v = getId(v);
    G[u][v] = G[v][u] = min(G[u][v], w);
  }
  matpow(G, N, Ans);
  cout << Ans[getId(S)][getId(E)] << endl;
}

魔法值

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
struct Mat {
  int r, c;
  vector<vl> f;
  Mat(int r, int c) : r(r), c(c), f(r, vl(c)) {}
  Mat operator*(const Mat &b) {
    Mat m(r, b.c);
    rep(i, 0, m.r) rep(j, 0, m.c) rep(k, 0, c) m.f[i][j] ^= f[i][k] * b.f[k][j];
    return m;
  }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  const int BT = 32;
  int n, m, q;
  cin >> n >> m >> q;
  Mat f0(1, n);
  vector<Mat> E(BT, Mat(n, n));
  rep(i, 0, n) cin >> f0.f[0][i];
  for (int i = 0, u, v; i < m; ++i) {
    cin >> u >> v;
    --u, --v;
    E[0].f[u][v] = E[0].f[v][u] = 1;
  }
  rep(i, 1, BT) E[i] = E[i - 1] * E[i - 1];
  Mat f(1, n);
  for (ll a = 0; q; --q) {
    Mat f = f0;
    cin >> a;
    for (int i = 0; (1LL << i) <= a; ++i) {
      if (a & (1LL << i)) f = f * E[i];
    }
    cout << f.f[0][0] << endl;
  }
}

球形空间产生器

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
// b: 系数矩阵，c: 常数
double a[20][20], b[20], c[20][20];
int n;
int main() {
  cin >> n;
  for (int i = 1; i <= n + 1; ++i)
    for (int j = 1; j <= n; ++j) scanf("%lf", &a[i][j]);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      c[i][j] = 2 * (a[i][j] - a[i + 1][j]);
      b[i] += a[i][j] * a[i][j] - a[i + 1][j] * a[i + 1][j];
    }
  // 高斯消元
  for (int i = 1; i <= n; ++i) {
    // 找到 x[i] 的系数不为 0 的一个方程
    for (int j = i; j <= n; ++j) {
      if (fabs(c[j][i]) > eps) {
        for (int k = 1; k <= n; ++k) swap(c[i][k], c[j][k]);
        swap(b[i], b[j]);
      }
    }
    // 消去其它方程 x[i] 的系数
    for (int j = 1; j <= n; ++j) {
      if (i == j) continue;
      double rate = c[j][i] / c[i][i];
      for (int k = i; k <= n; ++k) c[j][k] -= c[i][k] * rate;
      b[j] -= b[i] * rate;
    }
  }
  for (int i = 1; i <= n; ++i) printf("%.3f ", b[i] / c[i][i]);
  printf("\n");
}

甲苯先生的字符串

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7, SG = 26;
typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)

struct Mat {
  ll f[SG][SG];
  Mat() { memset(f, 0, sizeof(f)); }
  Mat operator*(const Mat &b) const {
    Mat m;
    rep(i, 0, SG) rep(j, 0, SG) rep(k, 0, SG) {
      (m.f[i][j] += f[i][k] * b.f[k][j] % MOD) %= MOD;
    }
    return m;
  }
};
Mat matpow(Mat a, ll b) {
  Mat m;
  rep(i, 0, SG) m.f[i][i] = 1;
  for (; b; a = a * a, b >>= 1) {
    if (b & 1) m = m * a;
  }
  return m;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  Mat G, A, SumG;
  rep(i, 0, SG) {
    A.f[0][i] = SumG.f[i][0] = 1;
    rep(j, 0, SG) G.f[i][j] = 1;
  }
  ll n;
  string s;
  cin >> n >> s;
  rep(i, 1, s.size()) G.f[s[i - 1] - 'a'][s[i] - 'a'] = 0;
  cout << (A * matpow(G, n - 1) * SumG).f[0][0] << endl;
}

Square

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110, maxp = 510;
int vis[maxn], prime[maxp];
int get_primes(int n) {
  int m = (int)sqrt(n + 0.5);
  memset(vis, 0, sizeof(vis));
  for (int i = 2; i <= m; ++i)
    if (!vis[i])
      for (int j = i * i; j <= n; j += i) vis[j] = 1;
  int c = 0;
  for (int i = 2; i <= n; ++i)
    if (!vis[i]) prime[c++] = i;
  return c;
}
typedef int Mat[maxn][maxn];
int rank_(Mat A, int m, int n) {
  int i = 0, j = 0, k, r, u;
  while (i < m && j < n) {
    r = i;
    for (k = i; k < m; ++k)
      if (A[k][j]) {
        r = k;
        break;
      }
    if (A[r][j]) {
      if (r != i)
        for (k = 0; k <= n; ++k) swap(A[r][k], A[i][k]);
      for (int u = i + 1; u < m; ++u)
        if (A[u][j])
          for (k = i; k <= n; ++k) A[u][k] ^= A[i][k];
      i++;
    }
    j++;
  }
  return i;
}
Mat A;
int main() {
  int m = get_primes(500);
  int T;
  cin >> T;
  while (T--) {
    int n, maxp = 0;
    long long x;
    cin >> n;
    memset(A, 0, sizeof(A));
    for (int i = 0; i < n; ++i) {
      cin >> x;
      for (int j = 0; j < m; ++j)
        while (x % prime[j] == 0) {
          maxp = max(maxp, j);
          x /= prime[j];
          A[j][i] ^= 1;
        }
    }
    int r = rank_(A, maxp + 1, n);
    cout << (1LL << (n - r)) - 1 << endl;
  }
}

Sasha and Array(未完成)

Reading

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < (int)(b); ++i)
const int MOD = 1e9 + 7, SIG = 26, FF = 5, SZ = SIG * FF + 1;
typedef vector<ll> vl;
struct Mat {
  int r, c;
  vector<vl> f;
  Mat(int r, int c) : r(r), c(c), f(r, vl(c)){};
  Mat operator*(const Mat& b) const {
    Mat m(r, b.c);
    rep(i, 0, m.r) rep(j, 0, m.c) rep(k, 0, m.c) {
      (m.f[i][j] += f[i][k] * b.f[k][j] % MOD) %= MOD;
    }
    return m;
  }
  Mat pow(ll b) const {
    Mat m = *this, p = *this;
    for (--b; b; p = p * p, b >>= 1) {
      if (b & 1) m = m * p;
    }
    return m;
  }
};
int main() {
  Mat G(SZ, SZ);
  rep(i, 0, SIG) {
    rep(j, 0, SIG) G.f[i * FF][j * FF] = 1;
    rep(f, 0, FF - 1) G.f[i * FF + f + 1][i * FF + f] = 1;
  }
  int s = SIG;
  rep(i, 0, SIG) G.f[s * FF][i * FF] = 1;
  G.f[s * FF][s * FF] = 1;
  int n, m, ans = 0;
  cin >> n >> m;
  for (int i = 0, f; i < m; ++i) {
    char a, b;
    cin >> a >> b >> f;
    int i1 = (a - 'a') * FF, i2 = (b - 'a') * FF;
    G.f[i1][i2] = 0, G.f[i1][i2 + f - 1] = 1;
    G.f[i2][i1] = 0, G.f[i2][i1 + f - 1] = 1;
  }
  G = G.pow(n + 1);
  rep(i, 0, SIG)(ans += G.f[SIG * FF][i * FF]) %= MOD;
  cout << ans << endl;
}

球形空间产生器

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
// b: 系数矩阵，c: 常数
double a[20][20], b[20], c[20][20];
int n;
int main() {
  cin >> n;
  for (int i = 1; i <= n + 1; ++i)
    for (int j = 1; j <= n; ++j) scanf("%lf", &a[i][j]);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      c[i][j] = 2 * (a[i][j] - a[i + 1][j]);
      b[i] += a[i][j] * a[i][j] - a[i + 1][j] * a[i + 1][j];
    }
  // 高斯消元
  for (int i = 1; i <= n; ++i) {
    // 找到 x[i] 的系数不为 0 的一个方程
    for (int j = i; j <= n; ++j) {
      if (fabs(c[j][i]) > eps) {
        for (int k = 1; k <= n; ++k) swap(c[i][k], c[j][k]);
        swap(b[i], b[j]);
      }
    }
    // 消去其它方程 x[i] 的系数
    for (int j = 1; j <= n; ++j) {
      if (i == j) continue;
      double rate = c[j][i] / c[i][i];
      for (int k = i; k <= n; ++k) c[j][k] -= c[i][k] * rate;
      b[j] -= b[i] * rate;
    }
  }
  for (int i = 1; i <= n; ++i) printf("%.3f ", b[i] / c[i][i]);
  printf("\n");
}

外星千足虫

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (int)(b); ++i)

using namespace std;
const int N = 1004;
bitset<N> Mat[2 * N];
int gauss(int n, int m) {
  int k = -1;
  rep(i, 1, n) {
    int cur = i;
    while (cur <= m && !Mat[cur][i]) cur++;
    if (cur > m) return 0;
    k = max(k, cur);
    if (cur != i) swap(Mat[cur], Mat[i]);
    rep(j, 1, m) if (i != j && Mat[j].test(i)) Mat[j] ^= Mat[i];
  }
  return k;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  string s;
  for (int i = 1, b; i <= m; ++i) {
    cin >> s >> b;
    rep(j, 1, n) Mat[i].set(j, s[j - 1] == '1');
    Mat[i].set(0, b);
  }
  int k = gauss(n, m);
  if (k) {
    cout << k << endl;
    rep(i, 1, n) cout << (Mat[i][0] ? "?y7M#" : "Earth") << endl;

  } else {
    cout << "Cannot Determine\n";
  }
}