2200G. Operation Permutation

Combinatorics, dp, math, probabilities

https://codeforces.com/problemset/problem/2200/G

AksLolCoding has an integer 𝑥 and a list of 𝑛 operations. Each operation is a string starting with one of the symbols +,-,x, or /(representing addition, subtraction, multiplication, and real number division respectively), followed immediately by a positive integer 𝑦 (1≤𝑦≤109). For example, the operation x3 represents multiplying 𝑥 by 3.

AksLolCoding will randomly permute the operations and then apply all operations sequentially to 𝑥 in the permuted order. Help AksLolCoding compute the expected∗ final value of 𝑥 modulo 109+7.

Formally, let 𝑀=109+7. It can be shown that the answer can be expressed as an irreducible fraction 𝑝𝑞, where 𝑝 and 𝑞 are integers and 𝑞≢0(mod𝑀). Output the integer equal to 𝑝⋅𝑞−1(mod𝑀). In other words, output such an integer 𝑎 that 0≤𝑎<𝑀 and 𝑎⋅𝑞≡𝑝(mod𝑀).

∗The expected final value of 𝑥 is the average of the final value of 𝑥 over all 𝑛! permutations.

Input

The first line contains a single integer 𝑡 (1≤𝑡≤1000), the number of test cases.

For each test case, the first line contains two integers 𝑛 and 𝑥 (1≤𝑛≤3000, 1≤𝑥≤109).

The second line of each test case contains 𝑛 strings, each representing an operation in the format described above.

The sum of 𝑛2 over all test cases does not exceed 30002.

Note: x is used to represent multiplication, not *

Output

For each test case, output a single integer: the expected final value of 𝑥 modulo 109+7.

Example

input

4
2 10
x2 -10
4 2
+6 +7 /1 -13
8 1
+1 x2 x3 +4 +5 +6 -7 -8
9 864209753
-918273645 x564738291 /365107362 x734582911 -654321789 x998244353 +172519103 /482193765 /482091376

output

Note

In the first test case, 𝑥 can either be (10⋅2)−10=10 or (10−10)⋅2=0, resulting in an expected value of 5.

In the second test case, all possible permutations result in 𝑥=2.

In the third test case, the expected value of 𝑥 is 556.

【尹显齐 2500011456 物理学院】

数学基础：费马小定理

a^{p - 1} \equiv 1 (对 p 取余，当 gcd (a, p) = 1)

我们可以利用它求逆元：

a^{- 1} \equiv a^{p - 2} (对 p 取余)

此题中，模数 $p = 10^{9} + 7$ 。
最trivial的方法的时间复杂度是 $O (n!)$ ，明显不行。
首先，我们应当意识到，本质上我们只进行 $+$ 和 $*$ 两种运算。减去 $a$ 相当于加 $- a$ ，除以 $a$ 相当于乘 $a^{p - 2}$ 。接下来，与其按照式子顺序计算最终值。我们考察加上的每一个数在之后的变化。即：对于一个具体的式子，如果加上的每个数为

a_{1}, \dots, a_{m}

那么最终的结果一定可以表示为

r e s = x + k_{1} a_{1} + \dots + k_{m} a_{m}

注意到，在某一步加上的数 $a_{i}$ 只会受到之后所有乘法的作用，那么为计算这个数对平均值的贡献我们可以这样考虑：假设所有乘数

b_{1}, \dots, b_{l}

排成一个特定顺序，此时我们在这个序列中随机地插入 $a_{i}$ ，则在这个特定序列下它的贡献的平均值为

E [a_{i}]_{b_{1}, \dots, b_{l}} = \frac{a_{i} \sum_{j = 1}^{l} (Π_{k = j}^{l} b_{k}) + a_{i}}{l + 1}

现在，考虑这个值对所有乘数排成的序列的平均值。序列总共有 $l!$ 种，对于最后 $k$ 个数确定（但相对未知不确定）的情况，共有

k! \cdot (l - k)!

种序列，那么如果我们能计算出所有不同方式得到的 $k$ 个数的乘积的总和 $S (k)$ ，那么就有

\overset{―}{Π_{k = j}^{l} b_{k}} = \frac{k! \cdot (l - k)! \cdot S (k)}{l!}

注意到 $S (0) = 1$ ，那么有 $a_{i}$ 的贡献的平均值为

E [a_{i}] = \frac{a_{i} \sum_{j = 0}^{l} k! \cdot (l - k)! \cdot S (k)}{(l + 1) l!}

那么答案就是对 $a_{i}$ 求和，加上初始值 $x$ 的贡献：

a n s = \frac{\sum_{i = 1}^{n - l} a_{i} \sum_{j = 0}^{l} k! \cdot (l - k)! \cdot S (k)}{(l + 1) l!} + x \prod_{i = 1}^{l} b_{i}

而计算 $S (k)$ 则可以采用二维dp的方式。令 $d p (i, j)$ 为前 $i$ 个数中所有不同的 $j$ 个数的乘积之和，则有

d p (i, j) = d p (i - 1, j - 1) \cdot b_{i} + d p (i - 1, j)

那么

S (k) = d p (l, k)

实际计算时，除以分母都采用乘以分母的逆元。这样，我们就在 $O (n^{2})$ 的时间复杂度内解决了此问题。

python

MOD = 10**9+7 # 模数
N = 3000 # n最大值、
# 预计算1到3000的阶乘值
fact = [1]*(N+1)
for i in range(1,N+1):
    fact[i] = fact[i-1]*i%MOD
# 主程序
for _ in range(int(input())):
    n,x = map(int,input().split())
    oper = input().split()
    ans = 0 # 记录所有加减之和
    mul = [] # 记录所有乘数
    for op in oper:
        a,b = op[0],int(op[1:])
        if a == "+":
            ans += b
        elif a == "-":
            ans -= b
        elif a == "x":
            mul.append(b)
        else:# 是除法，乘以其逆元
            mul.append(pow(b,MOD-2,MOD))
    ans %= MOD
    l = len(mul)#乘数个数
    dp = [[0]*(l+1) for _ in range(l+1)]#dp计算S(k)
    dp[0][0] = 1#初始化
    for i in range(1,l+1):
        for j in range(i+1):
            dp[i][j] = (dp[i-1][j]+(dp[i-1][j-1]*mul[i-1])%MOD)%MOD
    #下面过程和上方式子一一对应
    mulans = 0
    for i in range(l+1):
        mulans += dp[l][i]*(fact[i]*fact[l-i])%MOD
        mulans %= MOD
    mulans *= pow(l*fact[l]%MOD,MOD-2,MOD)
    mulans %= MOD
    print(((x*dp[l][l])%MOD + (ans*mulans)%MOD)%MOD)

2200G. Operation Permutation ​

2200G. Operation Permutation