QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93955#6137. Sub-cycle GraphksunhokimTL 4ms6740kbC++171.5kb2023-04-04 11:16:152023-04-04 11:16: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 11:16:16]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:6740kb
  • [2023-04-04 11:16:15]
  • 提交

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() {
  cin.tie(nullptr)->sync_with_stdio(false);

  const int N = 1e6;
  vector<mint> facts(N+1);
  facts[0] = 1;
  for (int i=1;i<=N;i++){
    facts[i] = i*facts[i-1];
  }

  int t;
  cin >> t;
  while (t--) {
    int n,m;
    cin >> n >> m;
    if (m > n) {
      cout << 0 << "\n";
      continue;
    }
    if (m == n) {
      cout << 1 << "\n";
      continue;
    }
    mint ans = 0;
    for (int i=1;i<=n-m;i++){
      if (m < i) continue;
      mint ncr = facts[m-1]/(facts[i-1]*facts[m-i]);
      ans += ncr*facts[n]/(i*pow(mint(2),i));
    }
    cout << ans.v << "\n";
  }

}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 6740kb

input:

3
4 2
4 3
5 3

output:

15
12
90

result:

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

Test #2:

score: -100
Time Limit Exceeded

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:

0
3
3
1
0
12
15
12
1
0
60
75
90
60
1
0
360
450
570
630
360
1
0
2520
3150
3990
5040
5040
2520
1
0
20160
25200
31920
40950
50400
45360
20160
1
0
181440
226800
287280
368550
476280
559440
453600
181440
1
0
1814400
2268000
2872800
3685500
4785480
6161400
6804000
4989600
1814400
1
0
19958400
24948000
316...

result: