Submission #1404352


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using pii = pair<int, int>;
using vi = vector<int>;
using lint = long long;

const int inf = 1001001001;
const lint linf = 1001001001001001001ll;
const int mod = 1e9 + 7;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};

template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; }
template<typename T> inline void print(const T &x, string s = "\n") { cout << x << s; }
template<typename T> inline void print(const vector<T> &v, string s = " ")
{ if (!v.size()) puts(""); rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }
inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }
inline lint in() { lint x; std::cin>>x; return x; }

lint mod_pow(lint a, lint x, int p = 1e9 + 7) {
  lint ret = 1;
  for (lint i  = 1ll << 60; i; i >>= 1) {
    ret *= ret;
    ret %= p;
    if (x & i) { ret *= a; ret %= p; }
  }

  return ret;
}

lint inv(lint n, int p = 1e9 + 7) {
  return mod_pow(n, p - 2);
}

vector<lint> fact(1, 1);
lint Fact(lint n, int p = 1e9 + 7) {
  if (n == 0) return 1;
  if (fact.size() <= n) {
    fact.push_back(Fact(n - 1) * n % p);
  }
  return fact[n];
}

// nCk のmod
lint mod_Combination(lint n, lint k, int p = 1e9 + 7) {
  if (n < k || n < 0 || k < 0) return 0;
  return Fact(n, p) * inv(Fact(k, p), p) % p * inv(Fact(n - k, p), p) % p;
}

int n = in(), k = in();
int ei[110][110];
int beet(int s, int i = 0) {
  if (i == n) return s == 0;

  int ret;

  ret = 0;
  for (int j = 0; j <= s; ++j) {
    ret += beet(s - j, i + 1);
  }

  return ret;
}

signed main() {
  if (k / n == 0) {
    memset(ei, -1, sizeof(ei));
    cout << beet(k) << endl;
  }
  else {
    cout << mod_Combination(n, k - k / n * n) << endl;
  }
}

Submission Info

Submission Time
Task B - 高橋幼稚園
User Luzhiled
Language C++14 (GCC 5.4.1)
Score 80
Code Size 2178 Byte
Status TLE
Exec Time 2103 ms
Memory 256 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 80 / 80 0 / 20
Status
AC × 3
AC × 21
AC × 27
TLE × 6
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt
Subtask2 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask0_sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_12.txt AC 1 ms 256 KB
subtask1_13.txt AC 1 ms 256 KB
subtask1_14.txt AC 1 ms 256 KB
subtask1_15.txt AC 1 ms 256 KB
subtask1_16.txt AC 1 ms 256 KB
subtask1_17.txt AC 1 ms 256 KB
subtask1_18.txt AC 1 ms 256 KB
subtask1_19.txt AC 1 ms 256 KB
subtask2_01.txt AC 2 ms 256 KB
subtask2_02.txt AC 667 ms 256 KB
subtask2_03.txt TLE 2103 ms 256 KB
subtask2_04.txt TLE 2103 ms 256 KB
subtask2_05.txt TLE 2103 ms 256 KB
subtask2_06.txt TLE 2103 ms 256 KB
subtask2_07.txt AC 255 ms 256 KB
subtask2_08.txt TLE 2103 ms 256 KB
subtask2_09.txt AC 1 ms 256 KB
subtask2_10.txt TLE 2103 ms 256 KB
subtask2_11.txt AC 1 ms 256 KB