M개의 다른 표현식이 있고 이 표현식의 답이 범위 1에서 N(둘 다 포함)에 있다고 가정합니다. 따라서 범위 1에서 N까지의 각 i에 대해 x =max(f(i))를 고려하여 예상 값을 찾아야 합니다. x.
따라서 입력이 M =3, N =3과 같으면 출력은 2.2가 됩니다. 왜냐하면
| 순서 | 최대 빈도 |
|---|---|
| 111 | 3 |
| 112 | 2 |
| 113 | 2 |
| 122 | 2 |
| 123 | 1 |
| 133 | 1 |
| 222 | 3 |
| 223 | 2 |
| 233 | 2 |
| 333 | 3 |
$$E(x) =\sum P(x) * x =P(1) + 2P(2) + 3P(3) =\frac{1}{10} + 2 * \frac{6}{10} + 3 * \frac{3}{10} =\frac{22}{10}$$
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 조합:=새 지도
- nCr() 함수를 정의합니다. n, k_in 소요됩니다.
- k :=k_in 및 (n - k_in)의 최소값
- n
- 0을 반환
- 반환 조합[n, k]
- 1을 반환
- 1을 반환
- a :=1
- 0 ~ k - 1 범위의 cnt에 대해
- a :=a * (n - cnt)
- a :=a/(cnt + 1)의 바닥
- 조합[n, cnt + 1] :=a
- 반환
- a :=1
- s :=0
- 0부터 M/k + 2까지의 범위에 있는 i에 대해 다음을 수행합니다.
- M
- 루프에서 나오다
- M
- s :=s + a * nCr(N, i) * nCr(N-1+M-i*k, M-i*k)
- a :=-a
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
combination = {}
def nCr(n, k_in):
k = min(k_in, n - k_in)
if n < k or k < 0:
return 0
elif (n, k) in combination:
return combination[(n, k)]
elif k == 0:
return 1
elif n == k:
return 1
else:
a = 1
for cnt in range(k):
a *= (n - cnt)
a //= (cnt + 1)
combination[(n, cnt + 1)] = a
return a
def solve(M, N):
arr = []
for k in range(2, M + 2):
a = 1
s = 0
for i in range(M // k + 2):
if (M < i * k):
break
s += a * nCr(N, i) * nCr(N - 1 + M - i * k, M - i * k)
a *= -1
arr.append(s)
total = arr[-1]
diff = [arr[0]] + [arr[cnt + 1] - arr[cnt] for cnt in range(M - 1)]
output = sum(diff[cnt] * (cnt + 1) / total for cnt in range(M))
return output
M = 3
N = 3
print(solve(M, N)) 입력
3, 3
출력
1