舰队 collection 2019 年秋季活动 E1,第八驱逐队正在讨论要怎么迫害 DJ.
大潮表示,她左手的内火艇能对 DJ 造成 \(g_0 = a\) 点伤害,右手的战车能对 DJ 造成 \(g_1 = b\) 点伤害。
满潮表示,司令部研发的若干新式对陆武器,第 \(i\) 件可以对 DJ 造成 \(g_i = 3 ? g_{i?1} ? g_{i?2}\) 点伤害。
荒潮表示,司令部已经发现了 DJ 的弱点,可以对 DJ 造成巨大倍率的伤害,具体公式为:
朝潮现在已经知道了 \(a, b, n, k\) 的值,汇报给了提督你,现在请你算出可以对 DJ 造成多大的伤害。
请你把 \(f_{n,k}\) 对 \(p\) 取模的结果告诉在前线的第八驱逐队。
\(0\le a,b < p, 1\le T\le 1000, 1\le n,p\le 10^9,1\le k\le 100\) 。
其实就是斐波那契数列嵌套\(k\)次。显然我们需要找斐波那契数列模\(p\)的循环节。
斐波那契数列循环节是经典找规律问题,用BSGS打表:
signed main(){
freopen("table.out","w",stdout);
int n=1e5;
for(int P=1;P<=n;++P){
if(P%10000==0) cerr<<P<<endl;
function<matrix(CO matrix&,CO matrix&)> mul=[&](CO matrix&a,CO matrix&b)->matrix{
matrix ans={};
for(int k=0;k<2;++k)
for(int i=0;i<2;++i)for(int j=0;j<2;++j)
ans[i][j]=(ans[i][j]+a[i][k]*b[k][j])%P;
return ans;
};
function<matrix(matrix,int)> pow=[&](matrix a,int b)->matrix{
matrix ans={1,0,0,1};
for(;b;b>>=1,a=mul(a,a))
if(b&1) ans=mul(ans,a);
return ans;
};
int S=ceil(sqrt(10*P));
matrix a={3,P-1,1,0},b={1,0,0,1};
map<matrix,int> H={{b,0}};
for(int i=1;i<S;++i) H[b=mul(a,b)]=i;
a=mul(a,b),b={1,0,0,1};
int ans=-1;
for(int i=1;i<=S;++i)
if(H.count(b=mul(a,b))) {ans=i*S-H[b]; break;}
printf("%lld %lld\n",P,ans);
// int u=1%P,v=1%P;
// cerr<<" "<<v;
// for(int i=1;i<=ans+1;++i){
// cerr<<" "<<u;
// int t=u;u=(3*u+P-v)%P,v=t;
// }
// cerr<<endl;
}
return 0;
}
1 1
2 3
3 4
4 3
5 10
6 12
7 8
8 6
9 12
10 30
11 5
12 12
13 14
14 24
15 20
16 12
17 18
18 12
19 9
20 30
21 8
22 15
23 24
24 12
25 50
26 42
27 36
28 24
29 7
30 60
注意到我们不需要求最短循环节,所以可以对最短循环节进行放大,使得它与模数比较接近。
先看质数的情况:
\(5\rightarrow 10\),比较特殊。
\(+1:2,3,7,13,17,23\),它们\(\equiv 2,3\pmod 5\)。
\(-1:11,19,29\),它们\(\equiv 1,4\pmod 5\)。
记质数的变化为\(F(x)\),然后看合数的情况。容易得到
注意到我们要做\(10^5\)次质因数分解。能够不写Pollard-Rho吗?
事实上,这个循环节是有不动点的,比如\(60\rightarrow 60\)。
那么用unorderd_map
记录循环节的结果就行了。
int mod;
matrix operator*(CO matrix&a,CO matrix&b){
matrix ans={};
for(int k=0;k<2;++k)
for(int i=0;i<2;++i)for(int j=0;j<2;++j)
ans[i][j]=(ans[i][j]+a[i][k]*b[k][j])%mod;
return ans;
}
matrix pow(matrix a,int b){
matrix ans={1,0,0,1};
for(;b;b>>=1,a=a*a)
if(b&1) ans=ans*a;
return ans;
}
int pri[100000],tot;
unordered_map<int,int> H; // edit 1
int calc(int P){
if(H.count(P)) return H[P];
int&ans=H[P]=1;
for(int i=1;i<=tot and pri[i]*pri[i]<=P;++i)if(P%pri[i]==0){
int sum=pri[i]==5?10:(pri[i]%5==2 or pri[i]%5==3?pri[i]+1:pri[i]-1);
for(P/=pri[i];P%pri[i]==0;P/=pri[i]) sum*=pri[i];
ans=lcm(ans,sum);
}
if(P>1){
int sum=P==5?10:(P%5==2 or P%5==3?P+1:P-1);
ans=lcm(ans,sum);
}
return ans;
}
int P[101];
void real_main(){
int a=read<int>(),b=read<int>();
int n=read<int>(),K=read<int>();
read(P[1]);
for(int i=2;i<=K;++i) P[i]=calc(P[i-1]);
for(int i=K;i>=1;--i){
mod=P[i];
if(n==0) {n=a; continue;}
n=(pow((matrix){3,mod-1,1,0},n-1)*(matrix){b,0,a,0})[0][0];
}
printf("%lld\n",n);
}
signed main(){
int n=ceil(sqrt(1e9));
for(int i=2;i<=n;++i){
if(!pri[i]) pri[++tot]=i;
for(int j=1;j<=tot and i*pri[j]<=n;++j){
pri[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
for(int T=read<int>();T--;) real_main();
return 0;
}
原文:https://www.cnblogs.com/autoint/p/12774436.html