[2016湘潭邀请赛 A. 2016] 大数取模+循环节
发布时间:2020-12-14 01:26:28 所属栏目:大数据 来源:网络整理
导读:[2016湘潭邀请赛 A. 2016] 大数取模+循环节 1. 题目链接 XTU OnlineJudge : [2016湘潭邀请赛 A. 2016] 2. 题意描述 【图片看不清可以放大。】 给定一个 2 ? 2 的矩阵 A 和一个大整数 n ,求 A n 。矩阵每个元素对 7 取模数。 1 ≤ n 10 100000 , 0 ≤ A i j
[2016湘潭邀请赛 A. 2016] 大数取模+循环节1. 题目链接XTU OnlineJudge : [2016湘潭邀请赛 A. 2016] 2. 题意描述【图片看不清可以放大。】 给定一个 3. 解题思路看起来这个是一到矩阵快速幂的题目。但是,指数巨大。但是模数很小,而且题目提示了找循环节,显然的可以去考虑找循环节【不会找也没有关系,其实叉姐提示了循环节周期就是2016…】。 4. 实现代码/** * 找循环节代码 */
PII getInfo() {
vector<Mat> buf;
vector<int> used(MOD * MOD * MOD * MOD,-1);
B = A;
int val,offset,T;
for(int i = 0; ; i++) {
val = B.H();
if(used[val] != -1) {
T = i - used[val];
offset = used[val];
break;
}
used[val] = i;
buf.push_back(B);
B = A * B;
}
return make_pair(offset,T);
}
void presolve() {
int lcm = 1;
for(int i = 0; i < MOD; i ++) {
A.a[0][0] = i;
for(int j = 0; j < MOD; j++) {
A.a[0][1] = j;
for(int k = 0; k < MOD; k++) {
A.a[1][0] = k;
for(int t = 0; t < MOD; t++) {
A.a[1][1] = t;
PII ret = getInfo();
lcm = lcm * ret.second / __gcd(lcm,ret.second);
}
}
}
}
cout << lcm << endl;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int MX = 2;
const int MOD = 7;
struct Mat {
int a[MX][MX];
void I() { memset(a,0,sizeof(a)); }
void E() {
I();
for(int i = 0; i < MX; i++) a[i][i] = 1;
}
int H() {
int ret = 0;
for(int i = 0; i < MX; i++) {
for(int j = 0; j < MX; j++) {
ret *= MOD;
ret += a[i][j];
}
}
return ret;
}
Mat operator * (const Mat& e) const {
Mat ret; ret.I();
for(int k = 0; k < MX; k++) {
for(int i = 0; i < MX; i++) {
if(a[i][k] == 0) continue;
for(int j = 0; j < MX; j++) {
ret.a[i][j] += a[i][k] * e.a[k][j];
ret.a[i][j] %= MOD;
}
}
}
return ret;
}
Mat operator ^ (int b) const {
Mat x(*this),ret; ret.E();
while(b > 0) {
if(b & 1) ret = ret * x;
x = x * x;
b >>= 1;
}
return ret;
}
} A,B;
const int ML = 100000 + 4;
char s[ML];
/** * 大整数取模模板。 */
int mod(char str[],int num) {
int remainder = 0;
for(int i = 0; str[i]; i++) {
remainder = ((LL)remainder * 10 + str[i] - '0') % num;
}
return remainder;
}
int main() {
while(~scanf("%s",s)) {
int N = mod(s,336);
scanf("%d %d",&A.a[0][0],&A.a[0][1]);
scanf("%d %d",&A.a[1][0],&A.a[1][1]);
A = A ^ N;
printf("%d %dn",A.a[0][0],A.a[0][1]);
printf("%d %dn",A.a[1][0],A.a[1][1]);
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |