QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#184303 | #5661. Multi-Ladders | ucup-team1508# | AC ✓ | 0ms | 3700kb | C++14 | 1.5kb | 2023-09-20 16:38:16 | 2023-09-20 16:38:17 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int mod = 1e9+7;
struct mat {
int o[2][2];
mat(){}
void init() {
rep(i,0,1) rep(j,0,1) if(i==j) o[i][j]=1;
}
void zero() {
rep(i,0,1) rep(j,0,1) o[i][j]=0;
}
mat operator*(const mat&b) {
mat res;
res.zero();
rep(i,0,1) rep(j,0,1) rep(k,0,1) {
res.o[i][j]=(res.o[i][j]+1ll*o[i][k]*b.o[k][j]%mod)%mod;
}
return res;
}
};
mat qpow(mat a, int b) {
mat res;
res.zero();
res.init();
for (; b;b>>=1) {
if(b&1) res=res*a;
a=a*a;
}
return res;
}
int qpow(int a, int b) {
int res=1;
for(;b;b>>=1) {
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
}
return res;
}
mat a,b;
int n,k,p;
void solve() {
cin>>n>>k>>p;
b.o[0][0]=p-2;
b.o[0][1]=p-1;
b.o[1][0]=1;
b.o[1][1]=0;
a.o[0][0]=0;
a.o[1][0]=p;
// rep(i,0,1) rep(j,0,1) cout<<b.o[i][j]<<" \n"[j==1];
auto res = qpow(b,k-1)*a;
// rep(i,0,1) rep(j,0,1) cout<<res.o[i][j]<<" \n"[j==1];
// cout<<res.o[0][0]<<"\n";
int ans=res.o[0][0];
int tp=((1ll*p*(p-1)%mod-2ll*p+3)%mod+mod)%mod;
int mi=1ll*k*(n-1)%(mod-1);
ans=1ll*ans*qpow(tp,mi)%mod;
cout<<ans<<"\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--) solve();
}
/*
1
2 3 3
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
1 2 3 3
output:
162
result:
ok single line: '162'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
20 2 3 3 1 3 3 10 3 0 10 3 2 1 21 2 1 22 0 2000 15000 2000 12000 30000 200000 1000000000 3 3 2 1000000000 3 2 3 100000000 1000000000 1000000000 10 1000000000 3 100000000 2 1000000000 100000000 1 1000000000 10 1 1000000000 100000000 1 1000 100000000 1000000000 1000000000 0 1000000000 1000000000 1 100...
output:
162 6 0 0 0 0 349400141 243010659 52489881 53690844 176686901 218103365 558243892 991895211 693053429 883715672 80402569 0 0 311752813
result:
ok 20 lines