| 记录编号 |
356755 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[東方] 蓬莱山·辉夜 壹 |
最终得分 |
100 |
| 用户昵称 |
 sxysxy |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.522 s |
| 提交时间 |
2016-12-06 13:48:47 |
内存使用 |
0.69 MiB |
显示代码纯文本
//requires c99 or c++
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <stdarg.h>
typedef long long LL;
//注，对于样例:
/*
T 0 1 2 3 4 5
init rotate derive multiply rotate derive
1 1 1 1 2 2
1 1 -> 1 1 -> 0 2 -> 0 2 -> 1 2 -> 0 3
1 1 1 2 0 0
↑
箭头指向0位置，逆时针方向0,1,2,3
最后T = 5时，按照顺时针方向从0开始，小魔法阵能量依次为0 3 2 0
*/
//
LL P;
void matrix_mul(LL *a, LL *b, int m, int n, int p, LL *c) //矩阵乘法，要求c为0矩阵
{
for(int i = 0; i < m; i++)
for(int j = 0; j < p; j++)
for(int k = 0; k < n; k++)
c[i*m+j] = (c[i*m+j]+a[i*m+k]*b[k*n+j])%P;
}
void matrix_pow(LL *a, int n, LL exp, LL *res) //要求res是一个单位矩阵
{
LL base[n*n];
LL tmp[n*n];
int size = sizeof(LL)*n*n;
memcpy(base, a, size);
for(; exp;memset(tmp, 0, size), matrix_mul(base, base, n, n, n, tmp), memcpy(base, tmp, size), exp>>=1)
if(exp&1)
{
memset(tmp, 0, size);
matrix_mul(res, base, n, n, n, tmp);
memcpy(res, tmp, size);
}
}
/*
void print_rect(LL *a, int n) //输出方阵，检查用
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
printf(j == n-1?"%lld\n":"%lld ", a[i*n+j]);
}
*/
LL ops[20][50*50]; //这是全局变量，一开始默认就全部是0，故init_data中不再清零
int N, M;
LL T;
void init_data()
{
//freopen("test_data.in", "r", stdin);
freopen("Houraisan_Kaguya.in", "r", stdin);
freopen("Houraisan_Kaguya.out", "w", stdout);
char buf[20];
scanf("%lld %d %d %lld", &T, &N, &M, &P);
for(int i = 0; i < M; i++)
{
int a, b;
scanf("%s %d %d", buf, &a, &b);
switch(buf[0])
{
case 'c': //clear
for(int j = 0; j < N; j++)
if(j != a)ops[i][j*N+j] = 1;
break;
case 'd': //derive
for(int j = 0; j < N; j++)
if(j != b)ops[i][j*N+j] = 1;
ops[i][b*N+a] = 1;
break;
case 's': //swap
for(int j = 0; j < N; j++)
if(j != a && j != b)ops[i][j*N+j] = 1;
ops[i][b*N+a] = ops[i][a*N+b] = 1;
break;
case 'm': //multiply
for(int j = 0; j < N; j++)
if(j != a)ops[i][j*N+j] = 1;
else ops[i][j*N+j] = b%P;
break;
case 'r': //rotate
ops[i][(N-1)*N] = 1;
for(int j = 1; j < N; j++)
ops[i][(j-1)*N+j] = 1;
break;
}
//print_rect(ops[i], N);
}
}
void Kaguya() //辉夜姬！
{
LL tmp[N*N];
LL acc[N*N]; //累乘
int size = sizeof(LL)*N*N;
memcpy(acc, ops[0], size);
for(int i = 1; i < M; i++)
{
memset(tmp, 0, size);
matrix_mul(acc, ops[i], N, N, N, tmp); //矩阵乘法不满足交换律，顺序一定不能弄错
memcpy(acc, tmp, size);
}
memset(tmp, 0, size);
for(int i = 0; i < N; i++)
tmp[i*N+i] = 1; //单位矩阵
matrix_pow(acc, N, T/(LL)M, tmp); // T/M...
memcpy(acc, tmp, size);
T %= (LL)M;
for(int i = 0; i < T; i++) //余下的操作
{
memset(tmp, 0, size);
matrix_mul(acc, ops[i], N, N, N, tmp);
memcpy(acc, tmp, size);
}
LL res[N]; //终于要出结果了...
memset(res, 0, size/N);
LL pre[N]; //最开始的向量
for(int i = 0; i < N; i++)pre[i] = 1;
matrix_mul(pre, acc, 1, N, N, res);
for(int i = 0; i < N; i++)
printf(i == N-1?"%lld\n":"%lld ", res[i]);
}
int main()
{
init_data();
Kaguya();
return 0;
}
/*
//calcs Fibonacci
//计算斐波那契数列，检验正确！//注意这里用的不是LL而是int...
void fibonacci()
{
P = 10000;
long long n;
while(~scanf("%lld", &n) && ~n)
{
int a[] = {0, 1};
int b[] = {0, 1, 1, 1};
int r[] = {1, 0, 0, 1};
int t[] = {0, 0};
matrix_pow(b, 2, n, r);
matrix_mul(a, r, 1, 2, 2, t);
printf("%d\n", t[0]);
}
}
*/