Home AtCoder. 015 Don't be too close(6)
Post
Cancel

AtCoder. 015 Don't be too close(6)

[Link] https://AtCoder.jp/contests/typical90/tasks/typical90_o


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;
import java.io.*;

public class Main {
  static final int constv = (int)1e9 + 7;
  static long[] fac;
  static long[] rev;
  static long[] revFac;

  public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();
    int n = sc.nextInt();
    fac = new long[n + 1]; rev = new long[n + 1]; revFac = new long[n + 1];
    fac[0] = revFac[0] = 1; rev[1] = fac[1] = revFac[1] = 1;

    for(int i = 2; i <= n; i++) {
      fac[i] = (fac[i - 1] * i) % constv;
      int quotient = constv / i;
      rev[i] = constv - quotient * rev[constv - i * quotient] % constv;
      revFac[i] = revFac[i-1] * rev[i] % constv;
    }
    for(int i = 1; i <= n; i++) {
      int cnt = 1;
      long sum = 0;
      while(true) {
        int pn = n - (cnt - 1)*(i - 1);
        if(pn < cnt) break;
        sum = (sum + combi(pn, cnt)) % constv;
        cnt++;
      }
      sb.append(sum+"\n");
    }
    System.out.print(sb);
  }
  static long combi(int n, int k) { return (fac[n] * revFac[k] % constv) * revFac[n-k] % constv; }
}
This post is licensed under CC BY 4.0 by the author.