[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; }
}