公式 1
[g(n) = sum_{i = 0}^n inom n if(i)
]
[f(n) = sum_{i = 0}^n (-1)^{n - i} inom n ig(i)
]
证明
[f(n) = sum_{i = 0}^n(-1)^{n - i} inom n i g(i)
]
[= sum_{i = 0}^n (-1)^{n - i} inom ni sum_{j = 0}^i inom i j f(j)
]
[=sum_{j = 0}^nf(j)sum_{i = j}^ninom n i inom i j (-1)^{n - i}
]
[= sum_{j = 0}^n f(j) sum_{i = j}^ninom n j inom {n - j} {i - j} (-1)^{n - i}
]
[= sum_{j = 0}^ninom n j f(j) sum_{i = 0}^{n- j} inom {n - j} i (-1)^{n - j - i}
]
[= sum_{j = 0}^n f(j) (inom n jsum_{i = 0} ^{n - j} (1 - 1)^{n - j} )
]
[=f(n)
]
公式 2
[g(k) = sumlimits_{i = k} ^ n inom i k f(i)
]
[f(k) = sumlimits_{i = k} ^ n inom i k g(i)* (-1) ^ {i - k}
]
证明
[g(k) = sumlimits_{i = k} ^ n inom i k sumlimits_{j = i} ^ n inom j i g(j) * (-1) ^ {j - i}
]
[= sum_{j = k} ^n g(j) sum_{i = k} ^j inom j i inom i k (-1) ^ {j - i}
]
[= sum_{j = k} ^n g(j)sum_{i = k} ^ j inom j k inom {j - k} {i - k} (-1)^ {j - i}
]
[= sum_{j = k}^n g(j) inom j k sum_{i = 0} ^ {j - k} inom {j - k} i (-1) ^{j - k - i}
]
[= sum_{j = k}^n g(j) inom j k (1 - 1) ^ {j - k}
]
[= g(k)
]
例题
题意
有 (n) 个相邻格子， (m) 种颜色， 每种颜色有价值 (v_i) 把 (m) 种颜色喷涂到格子上，要求相邻格子颜色不相同，每种颜色的价值只算一遍，求格子总价值的期望，由于答案过大，你只需要求出答案 (mod 998244353) 即可
(n leq 1e16, m leq 2000)
解法
设 (g(m)) 为 (m) 种颜色随便喷涂的方案数
显然
[g(m) = m * (m - 1) ^ {n - 1}
]
设 (f(m)) 为恰好用 (m) 种颜色的方案数
[g(m) = sum_{i = 0}^m inom m i f(i)
]
[f(m) = sum_{i = 0}^m (-1) ^ {m - i} inom m i g(i)
]
[total = sum_{i = 1}^m v_i
]
[E = sum_{i = 0}^m frac {f(i)} {g(m)} * inom m i i * frac { total} m
]