QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#93972 | #6137. Sub-cycle Graph | ksunhokim | WA | 1735ms | 3800kb | C++20 | 1.7kb | 2023-04-04 12:05:10 | 2023-04-04 12:05:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Modular Integer
// does arithmetics (mod P) automatically
const int MOD = 1000000007; // 998244353
struct mint {
int v;
mint() : v(0) {}
mint(ll v) : v(v % MOD) { v += (v < 0) * MOD; }
};
mint& operator+=(mint& a, mint b) { if ((a.v += b.v) >= MOD) a.v -= MOD; return a; }
mint& operator-=(mint& a, mint b) { if ((a.v -= b.v) < 0) a.v += MOD; return a; }
mint operator*(mint a, mint b) { return mint((ll) a.v * b.v); }
mint operator+(mint a, mint b) { return a += b; }
mint operator-(mint a, mint b) { return a -= b; }
mint& operator*=(mint& a, mint b) { return a = a * b; }
mint pow(mint a, ll p) { return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1); }
mint inv(mint a) { return pow(a, MOD - 2); }
mint operator/(mint a, mint b) { return a * inv(b); }
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
const int N = 1e5;
vector<mint> facts(N+1);
vector<mint> twos(N+1);
facts[0] = 1;
for (int i=1;i<=N;i++){
facts[i] = i*facts[i-1];
}
for (int i=1;i<=N;i++){
twos[i] = pow(mint(2),i);
}
int t;
cin >> t;
while (t--) {
ll n,m;
cin >> n >> m;
if (m > n) {
cout << 0 << "\n";
continue;
}
if (m == n) {
cout << (facts[n-1]/2).v << "\n";
continue;
}
if (m == 0) {
cout << 1 << "\n";
continue;
}
mint ans = 0;
for (int i=1;i<=n-m;i++){
if (m < i) break;
//mint ncr = facts[m-1]/(facts[i-1]*facts[m-i]);
ans += facts[m-1]*facts[n]/(max(n-m-i,1ll)*i*twos[i]*facts[i-1]*facts[m-i]);
}
cout << ans.v << "\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 13ms
memory: 3800kb
input:
3 4 2 4 3 5 3
output:
15 12 90
result:
ok 3 number(s): "15 12 90"
Test #2:
score: -100
Wrong Answer
time: 1735ms
memory: 3664kb
input:
17446 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 4 4 5 0 5 1 5 2 5 3 5 4 5 5 6 0 6 1 6 2 6 3 6 4 6 5 6 6 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 9 0 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 10 0 10 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 11 0 11 1 11 2 11 3 11 4 11 5 11 6 11 7 11...
output:
1 3 3 1 1 6 15 12 3 1 20 45 90 60 12 1 90 165 390 630 360 60 1 504 840 1680 3780 5040 2520 360 1 3360 5292 9240 19950 40320 45360 20160 2520 1 25920 39312 64008 119070 264600 468720 453600 181440 20160 1 226800 334800 521640 882630 1761480 3817800 5896800 4989600 1814400 181440 1 2217600 3207600 484...
result:
wrong answer 11th numbers differ - expected: '10', found: '20'