Qoj7562 Except One

wgyhm

2023-10-19

qoj, 思维, 计数, 递推

Except One

给定 $p,k,t$，定义集合 $S={x|1\le x\le p-1,x\not = k }$。求恰好包含 $t$ 个数的子集的乘积和。答案对 $p$ 取模。

$p\le 10^9$

非常喵喵啊。

观察到无论 $t$ 是多少，如果去掉 $k$ 的限制模 $p$ 后答案一定是 $0$。令 $f_t$ 表示恰好包含 $t$ 个数的答案，则在模 $p$ 意义下，有转移 $f_t=-k\times f_{t-1}$。

然后发现不仅是 $f_t$ ，$f_{t-1},f_{t-2}\dots$ 也可以从前面递推过来。

答案就是 $(-k)^t$ 在模 $p$ 意义下的值。

1 2	read(mod);read(k);read(t); printf("%lld",power(mod-k,t));