今天我們來看看CF691E 題目連結
題目描述
給定 $n$ 個整數 $a_1, a_2, \dots, a_n$，求長度為 $k$ 的序列 $(x_1, x_2, \dots, x_k)$ 的數量，其中每個 $x_i$ 都從給定的數字中選取（相同數字若出現多次視為不同）。序列必須滿足：
$$
\forall, 1 \le i < k,\quad \mathrm{popcount}(x_i \oplus x_{i+1}) \equiv 0 \pmod{3},
$$
其中 $\oplus$ 表示位元異或（XOR）運算，$\mathrm{popcount}(y)$ 表示 $y$ 的二進制表示中 1 的個數。
輸入格式
- 第一行：兩個整數 $n$ 和 $k$ ($1 \le n \le 100$, $1 \le k \le 10^{18}$)。
- 第二行：$n$ 個整數 $a_i$ ($0 \le a_i \le 10^{18}$)。
輸出格式
- 輸出一個整數，代表滿足條件的序列數量模 $10^9+7$ 的結果。
前言
我真的以為這題是要先建一張圖，$a_i\oplus a_j\equiv0\pmod3$的話就連起來，然後問你說有幾種方式可以在這張圖走$k$步，但是完全想不出來怎麼做，看解答才發現是矩陣快速冪，太神奇了
想法
我也不知道這怎麼想到的，但是如果你想到說，令一個$z[i][j]$代表目前考慮到長度為$j$的XOR-sequence，並且結尾是$a[i]$的可能性的數量。
那麼如果$a[k]$是可以接在$a[i]$後面的數字，$z[k][j+1]$就可以從$z[i][j]$推出來。
具體來說：
$$
z[k][j+1] = \sum_{\text{avaliable }i}z[i][j]
$$
進一步說，如果不要限制$i$一定可以在$k$前面，公式會變成這樣：
$$
z[k][j+1] = \sum_{i}G_{i,k}z[i][j]
$$
where $G_{ik}=1$ for $a[i]$可以接在$a[k]$前面
$G_{ik}=0$ otherwise
現在你就有可能看出來，這個操作是把$z[][j]$更新成$z[][j+1]$，所以我們可以不用存每一個長度$j$的$z[][j]$，而可以只保留一個$z[]$，代表目前考慮到的XOR-sequence長度的，每一個$a[i]$結尾的可能數量。
也就是說：
$$
z’[k] = \sum_{i}G_{i,k}z[i]
$$
然後因為$G$是symmetric的($G_{ij} = G_{ji}$)所以
$$
z’k = \sum{i}G_{k,i}z_i
$$
不過因為題目的$k$超大，所以如果你想說，這種方法只能sequential地更新而放棄這種做法，就失敗了。
這就是矩陣$G$乘上一個vector $z$的形式。所以對於更新$k$次$z$，可以用矩陣快速冪，只要$\lg(k)$次矩陣乘法就可以了(矩陣乘法$M_{n\times n}\cdot M_{n\times n}$的複雜度是$n^3$)
實作上要注意，記得計算的時候要$\pmod{10^9+7}$，還有__builtin_popcount是對int，要對long long用，要改用__builtin_popcountll
程式碼:
const int _n = 100 + 10;
ll n, k, a[_n];
struct Mat {
public:
int rlen, clen;
vector<vector<int>> _a;
Mat(int rlen, int clen) : rlen(rlen), clen(clen) {
_a = vector<vector<int>>(rlen, vector<int>(clen, 0));
}
Mat operator*(const Mat& rhs) const {
Mat res(this->rlen, rhs.clen);
rep(i, 0, res.rlen) rep(j, 0, res.clen) {
res._a[i][j] = 0;
rep(k, 0, this->clen) res._a[i][j] = (1ll * res._a[i][j] + 1ll * (_a[i][k] % mod) * (rhs._a[k][j] % mod)) % mod;
}
return res;
}
Mat operator^(ll b) {
Mat res(rlen, clen), tmp = *this;
assert(rlen == clen);
rep(i, 0, rlen) {
res._a[i][i] = 1;
}
while (b) {
if (b & 1ll) res = res * tmp;
b >>= 1ll;
tmp = tmp * tmp;
}
return res;
}
};
main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
Mat G(n, n);
Mat z(n, 1);
rep(i, 0, n) {
cin >> a[i];
z._a[i][0] = 1;
}
rep(i, 0, n) {
rep(j, 0, n) {
if (__builtin_popcountll(a[i] ^ a[j]) % 3 == 0) {
G._a[i][j] = 1;
}
}
}
z = (G ^ (k - 1)) * z;
ll ans = 0;
rep(i, 0, n) {
ans = (1ll * ans + 1ll * z._a[i][0]) % mod;
}
cout << ans << '\n';
return 0;
}
標頭、模板請點Submission看 Submission