首页 技术 正文
技术 2022年11月11日
0 收藏 439 点赞 4,832 浏览 1283 个字

1597: 薛XX后代的IQ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 228  Solved: 55
[Submit][Status][Web Board]

Description


XX的低IQ是个令人头疼的问题,他的队友深受其害。幸运的是,薛XX非常有钱,所以他买了一些可以提高他的后代的IQ的药。这种药有三个属性,A,B和
P。当薛XX使用这种药的时候,他的基因会发生变化,所以他的儿子的IQ也会跟着变化。假设薛XX的父亲的IQ为X,薛XX自己的IQ为Y,那么薛XX的
儿子的IQ为(A*X+B*Y) mod P。薛XX的孙子的IQ依次类推。
现在给定X和Y,还有药的属性A、B和P,现在他想知道他的N代子孙的IQ(儿子是第一代,孙子是第二代)。

Input

第一行包含一个整数T(T<=100),表示数据组数
每组数据只有一行,包含六个整数X,Y,A,B,P,N(1 ≤ X, Y ≤ 300,1 ≤ A, B ≤ 30, 1≤ P ≤ 300 , 1 ≤ N < 1000000000),含义如题目所述

Output

对于每组数据,输出答案

Sample Input

4
180 80 1 1 190 1
189 83 2 2 190 1
189 83 1 1 190 2
172 73 23 19 273 9999

Sample Output

70
164
165
233矩阵快速幂,构造矩阵 f[i+1] = a*f[i-1]+b*f[i] . 特征矩阵为 {{b,a},{1,0}}.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <queue>
#include <string.h>
using namespace std;
typedef long long LL;
struct Maxtri{
int v[][];
};
int X,Y,a,b,p,n;
Maxtri mult(Maxtri a,Maxtri b){
Maxtri c;
for(int i=;i<;i++){
for(int j=;j<;j++){
c.v[i][j] = ;
for(int k=;k<;k++){
c.v[i][j] = (a.v[i][k]*b.v[k][j]%p+c.v[i][j])%p;
}
}
}
return c;
}
Maxtri pow_mod(Maxtri ma,int n){
Maxtri ans;
ans.v[][] = ans.v[][] = ;
ans.v[][] = ans.v[][] = ;
while(n){
if(n&) ans = mult(ans,ma);
ma = mult(ma,ma);
n>>=;
}
return ans;
}
int main()
{
int tcase;
scanf("%d",&tcase); while(tcase--)
{
scanf("%d%d%d%d%d%d",&X,&Y,&a,&b,&p,&n);
Maxtri ori ;
ori.v[][] = b,ori.v[][] = a;
ori.v[][] = ,ori.v[][] = ;
Maxtri ans = pow_mod(ori,n);
printf("%d\n",(ans.v[][]*Y+ans.v[][]*X)%p);
}
return ;
}
上一篇: oracle 一个网站
下一篇: EF – 1.模式
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,083
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,558
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,407
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,180
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,817
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,900