感觉还是好多东西记不得了,gg。
感觉还是好多东西记不得了,gg。
这道题还没写,是一道数位 DP,推荐记忆化搜索。
这道题是一道相当好的题目。
首先对于\(m = n – 1\)的情况,也就是树的形态下,可以考虑自下向上推,也就是从叶子节点开始推起,参考代码中 Toposort 的写法。然后,对于\(m > n\)的情况可以直接输出\(0\),因为这个方程组并不存在唯一的解:\(m\)个未知数仅提供\(n\)个条件,这样是不成立的。
最后考虑\(m = n\)的情况。这种情况就是基环树了。首先,Toposort 会把支链上的答案全部统计完毕,并且合并到环上的点。最后,我们唯一要多做的事情,就是处理环上的方程组。考虑一个这样的环:
这道题算是一道矩阵递推的模板题吧。不是很了解矩阵乘法或者是矩阵递推加速原理的可以移步这篇 Wiki:矩阵 – OI Wiki.我们很快可以推出一个 DP 方程出来,其中\(i\)代表位数,\(j\)代表第一位所填的数:
\[dp[i][j] = \sum^{j+2}_{k=j-2}dp[i-1][k]\]
然后,我们可以根据这个来推出一个递推矩阵:
\[\left[ \begin{array}{ccc}
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\
\end{array} \right]\]
初始矩阵是这样的:
\[\left[ \begin{array}{ccc}
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
\end{array} \right]\]
代码如下:
// P2106.cpp #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #define ll long long using namespace std; const ll mod = 1000000007; struct matrix { ll mat[10][10]; matrix() { memset(mat, 0, sizeof(mat)); } matrix operator*(const matrix &ma) const { matrix empt; for (ll i = 0; i < 10; i++) for (ll j = 0; j < 10; j++) for (ll k = 0; k < 10; k++) empt.mat[i][j] = (empt.mat[i][j] + mat[i][k] * ma.mat[k][j] % mod) % mod; return empt; } matrix operator^(const ll &num) const { ll tim = num; matrix pre = *(this); matrix tmp; for (ll i = 0; i < 10; i++) tmp.mat[i][i] = 1; while (tim) { if (tim & 1) tmp = tmp * pre; pre = pre * pre; tim >>= 1; } return tmp; } } premat, Dmat; int main() { ll k; scanf("%lld", &k); if (k == 1) { printf("%lld", 10); return 0; } for (ll i = 1; i < 10; i++) premat.mat[0][i] = 1; for (ll i = 0; i < 10; i++) for (ll j = i - 2; j <= i + 2; j++) { if (j < 0) continue; if (j > 9) break; Dmat.mat[j][i] = 1; } Dmat = Dmat ^ (k - 1); premat = premat * Dmat; ll ans = 0; for (ll i = 0; i < 10; i++) ans += premat.mat[0][i], ans %= mod; printf("%lld", ans); return 0; }