lcb-0077
1.000
Proposed solution
I'll solve this step by step.
## Problem Understanding
We need to calculate the sum of all possible subarray sums raised to the power K:
$$\sum_{1\leq l\leq r\leq N} \left(\sum_{l\leq i\leq r} A_i\right)^K$$
Let me trace through Sample 1 to understand:
- A = [3, 1, 2] (1-indexed)
- K = 2
- All subarrays and their sums:
- l=1,r=1: A[1]=3, sum=3, contribution=3²=9
- l=1,r=2: A[1]+A[2]=3+1=4, sum=4, contribution=4²=16
- l=1,r=3: A[1]+A[2]+A[3]=3+1+2=6, sum=6, contribution=6²=36
- l=2,r=2: A[2]=1, sum=1, contribution=1²=1
- l=2,r=3: A[2]+A[3]=1+2=3, sum=3, contribution=3²=9
- l=3,r=3: A[3]=2, sum=2, contribution=2²=4
- Total = 9+16+36+1+9+4 = 75
## Key Insight
Instead of computing each subarray sum separately, I can use the fact that:
$$\left(\sum_{l\leq i\leq r} A_i\right)^K = \sum_{i_1+i_2+...+i_K=l+r} \binom{K}{i_1,i_2,...,i_K} A_{l}^{i_1} A_{l+1}^{i_2} ... A_r^{i_K}$$
But there's a better approach using the multinomial theorem.
Actually, let me think differently. For each term $A_i^K$, I need to count how many times it appears in the sum of all subarrays.
More precisely, for each element $A_i$, I want to count how many subarrays include this element and contribute to the power K sum.
## Better Approach
Let's use the multinomial expansion:
$$\left(\sum_{l\leq i\leq r} A_i\right)^K = \sum_{i_1+i_2+...+i_K=K} \binom{K}{i_1,i_2,...,i_K} \prod_{j=1}^K A_{l+j-1}^{i_j}$$
But this is still complex. Let me think of it combinatorially.
## Even Better Approach
For each subarray [l,r], we compute $(\sum_{i=l}^r A_i)^K$.
Using the multinomial theorem:
$$\left(\sum_{i=1}^n x_i\right)^K = \sum_{k_1+k_2+...+k_n=K} \binom{K}{k_1,k_2,...,k_n} \prod_{i=1}^n x_i^{k_i}$$
So for our case:
$$\left(\sum_{i=l}^r A_i\right)^K = \sum_{k_1+k_2+...+k_{r-l+1}=K} \binom{K}{k_1,k_2,...,k_{r-l+1}} \prod_{j=0}^{r-l} A_{l+j}^{k_j}$$
This is still complex. Let me think of a simpler way.
## Simpler Approach - Direct Computation with Optimization
Let's compute the contribution of each element $A_i$ to the final sum.
For any element $A_i$, it appears in subarrays [l,r] where $l \leq i \leq r$.
- Number of such subarrays = $i \times (N - i + 1)$
But we need to compute $(\sum_{i=l}^r A_i)^K$ for each subarray.
## Efficient Approach Using Polynomial Expansion
Let's think about this differently. For each element, we can count how many times it contributes to the power K sum.
Actually, let me use a mathematical approach:
$$\sum_{l,r} \left(\sum_{i=l}^r A_i\right)^K = \sum_{l,r} \sum_{k_1+...+k_K=K} \binom{K}{k_1,...,k_K} \prod_{j=1}^K A_{l+j-1}^{k_j}$$
This is getting complex. Let me try a more direct approach.
## Final Approach - Using Prefix Sums and Multinomial Coefficients
Let's compute for each possible combination of powers that sum to K.
For example, if K=2, we have terms like:
- $A_i^2$ (appears in subarrays containing only element i)
- $2 A_i A_j$ (appears when both elements are in same subarray)
Actually, let me think of it this way:
We can compute for each power k from 1 to K, how many times each element contributes to that power.
But there's a simpler mathematical approach:
$$\sum_{l,r} \left(\sum_{i=l}^r A_i\right)^K = \sum_{k_1+k_2+...+k_K=K} \binom{K}{k_1,k_2,...,k_K} \sum_{l,r} \prod_{j=1}^K A_{l+j-1}^{k_j}$$
Let me implement a cleaner approach:
## Cleaner Mathematical Insight
For any fixed $k_1 + k_2 + ... + k_K = K$, we want to compute:
$$\sum_{l,r} \prod_{j=1}^K A_{l+j-1}^{k_j}$$
This is equivalent to computing for each subarray [l,r] the product of powers.
But there's an even better way - use linearity and compute contribution of each element.
## Simpler Implementation Approach
Let me implement a direct solution that works with the constraints:
For K=1: We can compute sum of all subarrays directly.
For higher K, we can use multinomial expansion.
Actually, let me just code up the straightforward approach for small K values.
Looking at the constraints (K ≤ 10), I'll use the multinomial approach.
## Implementation
```python
def modinv(a, mod):
return pow(a, mod - 2, mod)
def solve():
MOD = 998244353
N, K = map(int, input().split())
A = list(map(int, input().split()))
# Precompute prefix sums for efficiency
prefix = [0] * (N + 1)
for i in range(N):
prefix[i + 1] = (prefix[i] + A[i]) % MOD
# For each possible way to distribute K among the elements of a subarray
# We'll use multinomial coefficients
result = 0
# Use the fact that we can compute this efficiently using polynomial expansion
# But for small K, let's do it directly
# Let's compute contribution of each element in all subarrays
# For each element A[i], count how many times it appears in power k terms
# Actually, let's use a different approach:
# We'll compute the sum using multinomial expansion
# Precompute factorials for multinomial coefficients
fact = [1] * (K + 1)
for i in range(1, K + 1):
fact[i] = (fact[i-1] * i) % MOD
def nCr(n, r):
if r > n or r < 0:
return 0
return (fact[n] * modinv(fact[r], MOD)) % MOD
# For each subarray [l,r], we compute sum of A_i^k for all k
# But that's not right either.
# Let me use the correct approach:
# We want to compute sum over all subarrays of (sum of elements)^K
# Use multinomial theorem: (x1 + x2 + ... + x_n)^K = sum_{k1+...+kn=K} C(K,k1,...,kn) * x1^k1 * ... * x_n^kn
# For each subarray [l,r], we compute (sum_{i=l}^r A_i)^K
# Using multinomial theorem:
# = sum_{k1+...+(r-l+1)=K} C(K,k1,...,k(r-l+1)) * prod_{j=0}^{r-l} A[l+j]^{k_j}
# But this is still complex to compute directly.
# Let's use the fact that we can compute it as:
# For each way of distributing K powers among elements in a subarray,
# we count how many times that pattern occurs
# Simpler approach:
# Use dynamic programming or mathematical formula
# Let's do it by computing for each element A[i], how many times it contributes to the final sum
# when raised to power k.
# Actually, let me just implement a working solution:
# For small K, we can compute directly using multinomial expansion
# But that's complex. Let's use a simpler approach:
# We'll compute for each subarray [l,r] the sum of A_i^k terms
# Simpler and more direct approach:
# Use the fact that (sum of elements)^K can be computed using multinomial coefficients
# But let's just compute it directly for small K
if K == 1:
result = 0
for l in range(N):
for r in range(l, N):
result = (result + prefix[r+1] - prefix[l]) % MOD
print(result)
return
# For higher K, we'll compute using multinomial approach
# But let's implement a working version:
# Let's use the fact that for small K, we can compute this efficiently
# by considering all possible combinations of powers
# Actually, let me just do it properly with multinomial coefficients
# Precompute multinomial coefficients for K
# This is complex. Let me think of a cleaner way.
# Simpler approach:
# For each subarray [l,r], compute sum_{i=l}^r A_i, then raise to power K
result = 0
for l in range(N):
current_sum = 0
for r in range(l, N):
current_sum = (current_sum + A[r]) % MOD
# Compute (current_sum)^K mod MOD
power_result = pow(current_sum, K, MOD)
result = (result + power_result) % MOD
print(result)
solve()
```
Wait, let me re-read the problem and think more carefully.
The key insight is that we can compute this using the multinomial theorem but in a smarter way. Let me re-implement:
```python
def modinv(a, mod):
return pow(a, mod - 2, mod)
def solve():
MOD = 998244353
N, K = map(int, input().split())
A = list(map(int, input().split()))
# For small K, we can compute directly
result = 0
# For each subarray [l,r], compute (sum_{i=l}^r A_i)^K
for l in range(N):
current_sum = 0
for r in range(l, N):
current_sum = (current_sum + A[r]) % MOD
# Compute (current_sum)^K mod MOD
power_result = pow(current_sum, K, MOD)
result = (result + power_result) % MOD
print(result)
solve()
```Test output (stdout)
... [100%] 3 passed in 0.05s
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.