No.1181 Product Sum for All Subsets
タグ : / 解いたユーザー数 157
作問者 :
PCTprobability
/ テスター :
leafirby
Problem Statement
(21:24 The problem statement has been updated.)
Consider a sequence $S$ of $N$ elements consisting of integers between $1$ and $K$, inclusive.
There are $K^N \times (2^N-1)$ possible combinations of such a sequence $S$ and a proper subset $T$ of the set $\{1,2,...N\}$. Find the sum of $\displaystyle \prod_{i \in T}S_i$ over all of them.
Since the answer can be very large, print the remainder when the answer is divided by $10^9+7$.
Also, the product of all elements of the empty set is defined to be $1$.
Input
$N\ K$
$1 \le N \le 2×10^5$
$1 \le K \le 10^{18}$
All inputs are integers.
Output
Print a newline at the end.
Sample
Sample 1
Input
2 2
Output
16
For convenience, let $G$ be the set consisting of $S_i({i\in T})$.
When $S=\{1,1\}$, there are $3$ possible $G$: $\{1\},\{1\},\{\}$, and the products of all their elements are $1,1,1$, respectively.
When $S=\{1,2\}$, there are $3$ possible $G$: $\{1\},\{2\},\{\}$, and the products of all their elements are $1,2,1$, respectively.
When $S=\{2,1\}$, there are $3$ possible $G$: $\{2\},\{1\},\{\}$, and the products of all their elements are $2,1,1$, respectively.
When $S=\{2,2\}$, there are $3$ possible $G$: $\{2\},\{2\},\{\}$, and the products of all their elements are $2,2,1$, respectively.
Therefore, the answer is $3+4+4+5=16$.
Sample 2
Input
4 3
Output
5265
Sample 3
Input
3435 2835
Output
618988899
Print the remainder when divided by $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。