trang chủ / đề bài / icpc21_mn_f

Giá trị kỳ vọng

Đề bài

Mô tả

Cho một hoán vị p=(p1,p2,…,pN) của N số nguyên dương đầu tiên, ta định nghĩa:

  • gi(p) là ước chung lớn nhất của i phần tử đầu tiên của p (1≤i≤N).
  • f(p) là số giá trị phân biệt trong dãy g.

Ví dụ, với p=(2,4,6,3,1,5) thì:

  • g1=gcd(2)=2,
  • g2=gcd(2,4)=2,
  • g3=gcd(2,4,6)=2,
  • g4=gcd(2,4,6,3)=1,
  • g5=gcd(2,4,6,3,1)=1,
  • g6=gcd(2,4,6,3,1,5)=1.

Do đó f(p)=2.

Cho số nguyên N, ta sinh ngẫu nhiên một hoán vị p độ dài N (mỗi hoán vị có cùng xác suất). Hãy tính kỳ vọng của f(p).

Dữ liệu vào

Một dòng gồm một số nguyên N.

Dữ liệu ra

In ra kỳ vọng của f(p) modulo 109+7.

Cụ thể, đặt M=109+7. Có thể chứng minh rằng đáp án biểu diễn được dưới dạng phân số tối giản u/v với u, v là các số nguyên và v≢0(modM). Hãy in ra số nguyên bằng u·v−1modM, nói cách khác, số nguyên x thỏa mãn 0≤x<M và x·v≡u(modM).

Ràng buộc

  • 1≤N≤200000.

Ví dụ

Input Output Giải thích
2 500000005 Hoán vị (1,2) có f=1, hoán vị (2,1) có f=2 (dãy g là 2,1). Kỳ vọng là 3/2.
3 666666673 Hai hoán vị bắt đầu bằng 1 có f=1, bốn hoán vị còn lại có f=2. Kỳ vọng là 10/6=5/3.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0