QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#638719#5661. Multi-Ladderswmw#AC ✓0ms3648kbC++201.3kb2024-10-13 16:43:042024-10-13 16:43:08

Judging History

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

  • [2024-10-13 16:43:08]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3648kb
  • [2024-10-13 16:43:04]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define all(v) v.begin(), v.end()
#define prs(v) sort(all(v)); v.erase(unique(all(v)), v.end())
using namespace std;

constexpr int mod = 1'000'000'007;

auto modpow(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

auto sum_of_ratio(int a, int n, int r) {
    return a * (modpow(r, n) - 1 + mod) % mod * modpow(r - 1, mod - 2) % mod;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;

    while (t--) {
        int n, k, l;
        cin >> n >> k >> l;

        if (l < 2) {
            cout << 0 << endl;
            continue;
        }

        if (l == 2) {
            if (k & 1) cout << 0 << endl;
            else cout << 2 << endl;
            continue;
        }
        
        int include = sum_of_ratio((k & 1) ? (l - 1) * (l - 1) % mod : (l - 1), k / 2, (l - 1) * (l - 1) % mod);
        int exclude = sum_of_ratio((k & 1) ? (l - 1) : (l - 1) * (l - 1) % mod, (k - 1) / 2, (l - 1) * (l - 1) % mod);
        int sum = l * (include - exclude + mod) % mod;
        int res = sum * (modpow(modpow(((l * l - 3 * l + 3) % mod + mod) % mod, n - 1), k)) % mod;
        cout << res << endl;
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

1
2 3 3

output:

162

result:

ok single line: '162'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3648kb

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