县建设局 协会网站,建设电影网站的目的,济南市莱芜区招聘信息,wordpress 主题漏洞一、题目大意
我们有N只猫#xff0c;每次循环进行K次操作#xff08;N100#xff0c;K100#xff09;#xff0c;每次操作可有以下三种选择#xff1a;
1、g i 给第i只猫1个食物
2、e i 让第i只猫吃完它所有的食物
3、s i j 交换第i和j只猫的食物。
求出M次…一、题目大意
我们有N只猫每次循环进行K次操作N100K100每次操作可有以下三种选择
1、g i 给第i只猫1个食物
2、e i 让第i只猫吃完它所有的食物
3、s i j 交换第i和j只猫的食物。
求出M次循环后每只猫有多少个食物M1000000000
二、解题思路
假设已经循环过 w 次设第i只猫的食物数量为 ai
设循环过 w1 次第 i 只猫的食物数量为 bi。
不难1次循环的k个操作后bi a1 * m1 a2 * m2 a3 * m3 ... an * mn C
所以可推出以下的矩阵成立
同时当 ai 和 bi 之间相差M次循环时也有如下表达式成立。 考虑下初始的情况一开始每只猫都没有食物设 Si 为 M次循环后第 i 只猫的数量把初值代入 a1 .. an有如下表达式成立。 但是这样我们需要使用 101 * 101大小的矩阵进行相乘而且本题目需要开long long。
但经过思考发现可以把矩阵降低一维成为100。 我们可以发现矩阵M次方的规律。
1、 对于矩阵中 1 1 N我们发现 这些值不管成多少次都与第M1行和N1列无关。
2、最后一行始终不变。
3、对于最后一列我们发现它可以通过如下表
达式。在100 * 100的复杂性内计算。
设进行经过i次循环的最后一列为Ci。对于最后一列的第 j 行则有如下表达式。 维护4个滑动数组计算每一次更新内圈的后再更新最后一列的值M次操作后最后一列的值就是答案因为M次次幂即可求解答案。初始时每只小鼠没有食物最一列开long long中间开int即可。
三、代码
#include iostream
#include vector
using namespace std;
typedef long long ll;
int P[2][107][107], B[107][107];
ll _P[2][107], _B[107];
int N, M, K;
void pow(int _N)
{int cnt 0;while (_N 0){int crt cnt 1, nxt !(cnt 1);if (_N 1){for (int i 0; i N; i){_P[nxt][i] _B[i];for (int j 0; j N; j){_P[nxt][i] _P[nxt][i] ((ll)B[i][j]) * _P[crt][j];P[nxt][i][j] 0;for (int k 0; k N; k){P[nxt][i][j] P[nxt][i][j] B[i][k] * P[crt][k][j];}}}for (int i 0; i N; i){_B[i] _P[nxt][i];for (int j 0; j N; j){B[i][j] P[nxt][i][j];}}}for (int i 0; i N; i){_P[nxt][i] _P[crt][i];for (int j 0; j N; j){_P[nxt][i] _P[nxt][i] ((ll)P[crt][i][j]) * _P[crt][j];P[nxt][i][j] 0;for (int k 0; k N; k){P[nxt][i][j] P[nxt][i][j] P[crt][i][k] * P[crt][k][j];}}}cnt;_N 1;}
}
void solve()
{for (int i 0; i 101; i){for (int j 0; j 101; j){B[i][j] P[0][i][j] P[1][i][j] 0;}B[i][i] 1;P[0][i][i] 1;_P[0][i] 0;_B[i] 0;}char c;int a, b;for (int i 0; i K; i){scanf(\n%c, c);if (c g){scanf(%d, a);_P[0][a - 1];}else if (c s){scanf(%d%d, a, b);for (int j 0; j N; j){int tmp P[0][a - 1][j];P[0][a - 1][j] P[0][b - 1][j];P[0][b - 1][j] tmp;}ll tmpL _P[0][a - 1];_P[0][a - 1] _P[0][b - 1];_P[0][b - 1] tmpL;}else if (c e){scanf(%d, a);for (int j 0; j N; j){P[0][a - 1][j] 0;}_P[0][a - 1] 0;}}pow(M);for (int i 0; i N; i){printf(%lld%c, _B[i], i 1 N ? \n : );}
}
int main()
{while (true){scanf(%d%d%d, N, M, K);if (N 0 M 0 K 0){break;}solve();}return 0;
}
