QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93977#6137. Sub-cycle GraphksunhokimAC ✓156ms4604kbC++201.8kb2023-04-04 12:14:132023-04-04 12:14:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-04 12:14:16]
  • 评测
  • 测评结果:AC
  • 用时:156ms
  • 内存:4604kb
  • [2023-04-04 12:14:13]
  • 提交

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> two_invs(N+1);
  vector<mint> invs(N+1);
  vector<mint> fact_invs(N+1);
  facts[0] = 1;
  for (int i=1;i<=N;i++){
    facts[i] = i*facts[i-1];
  }
  for (int i=0;i<=N;i++){
    fact_invs[i] = inv(facts[i]);
  }
  for (int i=1;i<=N;i++){
    two_invs[i] = inv(pow(mint(2),i));
  }
  for (int i=1;i<=N;i++){
    invs[i] = inv(mint(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;
      ans += facts[m-1]*facts[n]*fact_invs[max(n-m-i,1ll)]*fact_invs[i]*two_invs[i]*fact_invs[i-1]*fact_invs[m-i];
    }
    cout << ans.v << "\n";
  }

}

詳細信息

Test #1:

score: 100
Accepted
time: 78ms
memory: 4432kb

input:

3
4 2
4 3
5 3

output:

15
12
90

result:

ok 3 number(s): "15 12 90"

Test #2:

score: 0
Accepted
time: 156ms
memory: 4604kb

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
10
45
90
60
12
1
15
105
375
630
360
60
1
21
210
1155
3465
5040
2520
360
1
28
378
2940
13545
35280
45360
20160
2520
1
36
630
6552
42525
170100
393120
453600
181440
20160
1
45
990
13230
114345
643545
2286900
4762800
4989600
1814400
181440
1
55
1485
24750
273735
2047815
10239075
3...

result:

ok 17446 numbers