문제 설명

특정 게임에서는 다양한 장비를 수집하고 강화할 수 있는 시스템이 존재한다. 각 장비는 여러 개의 슬롯을 가지며, 각 슬롯에는 특정 가치를 가진 인쇄물이 무한히 존재한다.

게임 내 특정 캐릭터(예: 카구야마 하루카)가 기계 팔을 사용해 아래 방향으로만 움직이며 인쇄물을 추출한다. 이때 기계 팔은 오른쪽으로 이동하거나 제자리에 머무를 수 있으며, 시작 위치는 임의이나 항상 어떤 슬롯 위에 있어야 한다.

총 k번의 추출 동안 얻은 인쇄물들의 가치 곱이 최종 보상이 되며, 모든 가능한 조작 경우의 수에 대해 평균 보상을 구해야 한다. 결과는 매우 큰 수일 수 있으므로 주어진 소수 19260817로 나눈 나머지를 출력한다.

입력 형식

n k
a₁ a₂ ... aₙ

• n: 슬롯의 개수
• k: 추출 횟수
• aᵢ: i번째 슬롯의 인쇄물 가치

출력 형식

평균 보상 값을 모듈러 연산하여 출력한다.

예제 입력 및 출력

예제 1

입력:
3 2
3 1 2

출력:
16050685

예제 2

입력:
6 3
1 1 4 5 1 4

출력:
16509294

풀이 아이디어

이 문제는 동적 계획법(DP)과 조합론을 활용한 확률적 기댓값 계산이다. 각 단계에서 현재까지 선택된 아이템들의 가치 곱과 선택 방법 수를 동시에 추적하면서 진행한다.

DP 상태 정의:

• F[i][j]: i번째 슬롯까지 고려했을 때 j개를 선택하는 방법의 수
• G[i][j]: i번째 슬롯까지 고려했을 때 j개를 선택했을 때 가치 곱의 합

점화식은 다음과 같다:

• F[i][j] = F[i-1][j] + F[i][j-1]
• G[i][j] = G[i-1][j] + G[i][j-1] * a[i]

최종적으로 G[n][k]/F[n][k]가 평균이며, 이를 모듈러 역원을 이용해 처리한다.

C++ 코드 구현

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

using ll = long long;
const int MOD = 19260817;
const int MAX_N = 100005;
const int MAX_K = 305;

// 메모리 절약을 위해 rolling array 사용
ll dp_count[2][MAX_K];     // 선택 방법 수
ll dp_value[2][MAX_K];     // 가치 누적 곱의 합
int values[MAX_N];

// 빠른 입출력 함수
inline int read_int() {
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    int ret = 0;
    while (isdigit(c)) {
        ret = ret * 10 + (c - '0');
        c = getchar();
    }
    return ret;
}

// 모듈러 거듭제곱
ll mod_pow(ll base, ll exp, ll mod) {
    ll result = 1;
    while (exp > 0) {
        if (exp & 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

// 모듈러 역원
inline ll mod_inverse(ll x) {
    return mod_pow(x, MOD - 2, MOD);
}

int main() {
    ios::sync_with_stdio(false);
    
    int n = read_int();
    int k = read_int();
    
    for (int i = 1; i <= n; ++i)
        values[i] = read_int();

    bool curr = 0, next = 1;
    
    // 초기 상태 설정
    dp_count[curr][0] = 1;
    dp_value[curr][0] = 1;
    
    // DP 진행
    for (int pos = 1; pos <= n; ++pos) {
        dp_count[next][0] = 1;
        dp_value[next][0] = 1;
        
        for (int cnt = 1; cnt <= k; ++cnt) {
            dp_count[next][cnt] = 
                (dp_count[curr][cnt] + dp_count[next][cnt - 1]) % MOD;
                
            dp_value[next][cnt] = 
                (dp_value[curr][cnt] + 
                 (dp_value[next][cnt - 1] * values[pos]) % MOD) % MOD;
        }
        
        swap(curr, next);
    }
    
    ll total_ways = dp_count[curr][k];
    ll total_value_sum = dp_value[curr][k];
    
    // 평균 = 총 가치합 / 총 경우의 수
    ll avg = (total_value_sum * mod_inverse(total_ways)) % MOD;
    
    cout << avg << "\n";
    return 0;
}