QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#184303#5661. Multi-Laddersucup-team1508#AC ✓0ms3700kbC++141.5kb2023-09-20 16:38:162023-09-20 16:38:17

Judging History

你现在查看的是最新测评结果

  • [2023-09-20 16:38:17]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3700kb
  • [2023-09-20 16:38:16]
  • 提交

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