灵犀科技网站建设,erp网站代做,新乡市建设路小学网站,如何进网站HH去散步
题目限制
内存限制#xff1a;125.00MB时间限制#xff1a;1.00s标准输入标准输出
题目知识点
动态规划 dpdpdp矩阵 矩阵乘法矩阵加速矩阵快速幂 思维 构造
题目来源
「SDOI2009」HH去散步
题目
题目背景
HH 有个一成不变的习惯#xff0c;喜欢在饭后散步…HH去散步
题目限制
内存限制125.00MB时间限制1.00s标准输入标准输出
题目知识点
动态规划 dpdpdp矩阵 矩阵乘法矩阵加速矩阵快速幂 思维 构造
题目来源
「SDOI2009」HH去散步
题目
题目背景
HH 有个一成不变的习惯喜欢在饭后散步就是在一定的时间内走一定的距离 同时 HH 是一个喜欢变化的人她不会立刻沿着刚刚走过来的路走回去她也希望每天走过的路径都不完全一样她想知道每一天他究竟有多少种散步的方法
题目描述
现在 HH 送给你一张学校的地图请你帮助她求出从地点 AAA 走到地点 BBB 一共有多少条长度为 TTT 的散步路径答案对 459894598945989 取模
格式
输入格式
输入共 M1M 1M1 行 第 111 行输入 555 个整数 N,M,T,A,BN, \ M, \ T, \ A, \ BN, M, T, A, BNNN 表示 学校里的路口的个数编号为 0∼N−10 \sim N - 10∼N−1MMM 表示 学校里的道路的条数TTT 表示 HH 想要散步的距离AAA 表示 散步的出发点 BBB 表示 散步的终点 接下来 MMM 行每行 222 个用空格隔开的整数 ui,viu_i, \ v_iui, vi表示 长度为 111 的第 iii 条路 连接 路口 uiu_iui 和 路口 viv_ivi
输出格式
输出共一行表示你所求出的答案对 459894598945989 取模
样例
样例输入
4 5 3 0 0
0 1
0 2
0 3
2 1
3 2样例输出
4提示
数据范围
对于 30%30 \%30% 的数据满足 N≤4,M≤10,T≤10N \leq 4, \ M \leq 10, \ T \leq 10N≤4, M≤10, T≤10 对于 100%100 \%100% 的数据满足 N≤50,M≤60,T≤230,ui≠viN \leq 50, \ M \leq 60, \ T \leq 2 ^ {30}, \ u_i \neq v_iN≤50, M≤60, T≤230, uivi 思路
这道题如果没有 她不会立刻沿着刚刚走过来的路走回去 的限制就可以根据点与点的关系先构造出一个 n∗nn * nn∗n 的矩阵 x\mathrm{x}xx[i][j]\mathrm{x}[i][j]x[i][j] 表示从 iii 走 111 步到 jjj 的方案数累乘 TTT 次就是走了 TTT 步就用矩阵快速幂优化既可以通过了 现在就考虑加上这句话的限制后如何构造矩阵了 分析
考虑矩阵定义大致不变即 x[i][j]\mathrm{x}[i][j]x[i][j] 表示从 iii 走 111 步到 jjj 的方案数 由于有限制就要记录刚刚走过来的路是哪一条 不妨把每条边对应的 uiu_iui 和 viv_ivi 拆成两个二元组 (node,id)\mathrm{(node, id)}(node,id)表示刚刚从第 id\mathrm{id}id 条路走到 node\mathrm{node}node也就是每条无向边 (ui↔,vi)(u_i \leftrightarrow, v_i)(ui↔,vi) 分成两条有向边 (ui→vi)(u_i \to v_i)(ui→vi) 和 (vi→ui)(v_i \to u_i)(vi→ui)其中 node\mathrm{node}node 表示当前这条有向边的终点id\mathrm{id}id 表示与之对应的无向边的编号 那么 x[i][j]1\mathrm{x}[i][j] 1x[i][j]1 定义就是 第 iii 个二元组 走 111 步到 第 jjj 个二元组 的方案数 其值只可能为 000 或 111因为只走了 111 步其中值为 111 的条件就是 idi≠idj\mathrm{id}_i \neq \mathrm{id}_jidiidj 且 nodei\mathrm{node}_inodei 与 nodej\mathrm{node}_jnodej 有一条边 推出了矩阵但是还有一个细节就是第一步的方案数 起始点是没有上一条边的所以需要预处理一下这里相当于先走了一次 预处理矩阵 ×\times× 矩阵快速幂T−1T - 1T−1 次预处理走了一次就可以得到最终的矩阵了 最后把 起始点超级源点 到 终点可能有多个因为分了边 的路径加起来取模就可以了 代码
#include cstdio
#include cstringint rint()
{int x 0, fx 1; char c getchar();while (c 0 || c 9) { fx ^ ((c -) ? 1 : 0); c getchar(); }while (0 c c 9) { x (x 3) (x 1) (c ^ 48); c getchar(); }if (!fx) return -x;return x;
}const int MOD 45989;const int MAX_N 20;
const int MAX_M 60;int N, M, T, A, B, node;
int e[MAX_M * 2 5][3];struct Matrix
{int mx[MAX_M * 2 5][MAX_M * 2 5];Matrix () { memset(mx, 0, sizeof(mx)); }void init() { for (int i 0; i node; i) mx[i][i] 1; }Matrix operator * (const Matrix rhs) const{Matrix res;for (int i 0; i node; i)for (int j 0; j node; j)for (int k 0; k node; k)res.mx[i][j] (res.mx[i][j] mx[i][k] * rhs.mx[k][j]) % MOD;return res;}
} dp, quick;Matrix qpow(Matrix mx, int k)
{Matrix res; res.init();while (k 0){if (k 1) res res * mx;mx mx * mx; k 1;}return res;
}int main()
{N rint(), M rint(), T rint();A rint() 1, B rint() 1;for (int i 1; i M; i){e[i][0] rint() 1, e[i][1] rint() 1;e[i M][0] e[i][1], e[i M][1] e[i][0];if (e[i][0] A) dp.mx[0][i];if (e[i M][0] A) dp.mx[0][i M];}node M 1;for (int i 1; i node; i)for (int j 1; j node; j)if (i M ! j i - M ! j e[i][1] e[j][0]) quick.mx[i][j];int ans 0;Matrix res dp * qpow(quick, T - 1);for (int i 1; i node; i)if (e[i][1] B) ans (ans res.mx[0][i]) % MOD;printf(%d\n, ans);return 0;
}
