QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#725834 | #5661. Multi-Ladders | asd7766zxc# | WA | 1ms | 3628kb | C++20 | 2.7kb | 2024-11-08 20:14:02 | 2024-11-08 20:14:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define masterspark ios::sync_with_stdio(0), cin.tie(0),cout.tie(0),cin.exceptions(cin.failbit);
template<class F, class S> ostream &operator<<(ostream &s, pair<F, S> v) { return s << "(" << v.first << ", " << v.second << ")";}
template<class F, class S> istream &operator>>(istream &s, pair<F, S> &v) { return s >> v.first >> v.second; }
template<class T> istream &operator>>(istream &s, vector<T> &a) { for (auto &x:a) s>>x; return s; }
template<class T> ostream &operator<<(ostream &s, vector<T> &a) { int n=a.size(); if (!n) return s; s<<a[0]; for (int i=1; i<n; i++) s<<' '<<a[i]; return s; }
#define int long long
#define pp pair<int, int>
#define ff first
#define ss second
#define forr(i,n) for(int i = 1; i <= n;++i)
#define rep(i,j,n) for(int i = j; i < n;++i)
#define PB push_back
#define PF push_front
#define EB emplace_back
#define all(v) (v).begin(), (v).end()
#define FZ(x) memset(x, 0, sizeof(x)) //fill zero
#define SZ(x) ((int)x.size())
bool chmin(auto &a, auto b) { return (b < a) and (a = b, true); }
bool chmax(auto &a, auto b) { return (a < b) and (a = b, true); }
using i128 = __int128_t;
using i64 = int64_t;
using i32 = int32_t;
const int mod = 1e9 + 7;
void solve(){
int n, k, l; cin >> n >> k >> l;
vector<vector<i64>> ans(2, vector<i64> (2, 0));
ans[0][0] = l - 2;
ans[0][1] = l - 1;
ans[1][0] = 1;
ans[1][1] = 0;
auto mul = [&](vector<vector<i64>> aaa, vector<vector<i64>> bbb) {
vector<vector<i64>> tmp(2, vector<i64> (2, 0));
for (i32 i = 0; i < 2; i++) for (i32 l = 0; l < 2; l++) for (i32 k = 0; k < 2; k++)
tmp[i][l] += (aaa[i][k] * bbb[k][l]) % mod, tmp[i][l] %= mod;
return tmp;
};
auto ksm = [&](vector<vector<i64>> aaa, int n) {
vector<vector<i64>> res(2, vector<i64> (2, 0));
res[0][0] = res[1][1] = 1;
for (; n; n >>= 1, aaa = mul(aaa, aaa)) if (n & 1) res = mul(res, aaa);
return res;
};
auto ksm2 = [&](int a, int n) {
int res = 1;
for (; n; n >>= 1, a = (a * a) % mod) if (n & 1) res = res * a % mod;
return res;
};
ans = ksm(ans, k-1);
// int aaaa = (ans[0][1] * l) % mod;
int aaaa = (ksm2((l-1),n) + ((n&1) ? -1 : 1) * (l-1)) + mod ;
aaaa %= mod;
int tmp = (((l * l) % mod - (3 * l) % mod + 3) + mod) % mod;
aaaa = (aaaa * ksm2(tmp, (n - 1) * k)) % mod;
cout << aaaa << '\n';
}
signed main()
{
masterspark
int t = 1;
// freopen("stdin","r",stdin);
// freopen("stdout","w",stdout);
cin >> t;
while(t--){
solve();
}
return 0;
}
/*
/\_/\
(= ._.)
/ > \>
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
1 2 3 3
output:
162
result:
ok single line: '162'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3604kb
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 0 0 2 0 0 619159556 44174210 103570820 415637863 304930780 218103365 294935167 29649047 0 0 0 0 0 311752813
result:
wrong answer 2nd lines differ - expected: '6', found: '0'