直播类型网站开发,项目管理软件哪个好,山西省建设银行网站,wordpress多本小说题意#xff1a;给定 nnn 个数 aia_iai #xff0c;求选出#xff08;可以重复#xff0c;考虑顺序#xff09;MMM 个数和为 SSS 的方案数模 222。 n≤200,ai≤105,M,S≤1018n\leq 200,a_i\leq 10^5,M,S\leq 10^{18}n≤200,ai≤105,M,S≤1018
首先给每个数分配一个出…题意给定 nnn 个数 aia_iai 求选出可以重复考虑顺序MMM 个数和为 SSS 的方案数模 222。
n≤200,ai≤105,M,S≤1018n\leq 200,a_i\leq 10^5,M,S\leq 10^{18}n≤200,ai≤105,M,S≤1018
首先给每个数分配一个出现次数 cic_ici,这个 ccc 贡献的方案数为
M!c1!c2…cn!\frac{M!}{c_1!c_2\dots c_n!}c1!c2…cn!M!
即
(Mc1)(M−c1c2)(M−c1−c2c3)…\binom{M}{c_1}\binom{M-c_1}{c_2}\binom{M-c_1-c_2}{c_3}\dots(c1M)(c2M−c1)(c3M−c1−c2)…
写出 M,ciM,c_iM,ci 的二进制发现上式为奇数当且仅当 c1∣c2∣c3…∣cnMc_1|c_2|c_3\dots|c_nMc1∣c2∣c3…∣cnM
证明考虑模 222 意义下的卢卡斯定理对于组合数 (ab)\binom{a}{b}(ba)该式为 000 当且仅当二进制某个对应位置 aaa 为 000bbb 为 111。也就是说整个式子为 111 当且仅当每个组合数下面都是上面的子集。通过归纳法就可以证明。
如果想找个没这么启发式的证明可以考虑对于 222 的 ruler(x)2x−count(x)\operatorname{ruler}(x)2x-\operatorname{count}(x)ruler(x)2x−count(x)
这意味着对于 MMM 每一个为 111 的位 iii都可以且必须选 2i2^i2i 个相同的数。
所以从高到底考虑 SSS 的每一位做个背包设 f(i,j)f(i,j)f(i,j) 表示考虑到第 iii 位剩下 jjj 的空间的方案数每枚举一位就把这个空间乘以 222 加上这一位的数。因为 aia_iai 只有 10510^5105所以这个 jjj 不用记太大用 bitset 优化即可。
复杂度 O(TnailogS/w)O(T na_i\log S /w)O(TnailogS/w)
#include iostream
#include cstdio
#include cstring
#include cctype
#include bitset
using namespace std;
typedef long long ll;
const int N2e5;
int a[205];
bitsetN5 f[2];
int main()
{int T;scanf(%d,T);while (T--){ll M,S;int n;scanf(%lld%lld%d,M,S,n);for (int i1;in;i) scanf(%d,a[i]);f[0].reset(),f[1].reset();f[0].set(0);for (int d60;d0;d--){f[1].reset();for (int i0;((i1)|((Sd)1))N;i) if (f[0][i]) f[1].set((i1)|((Sd)1));f[0]f[1];if ((Md)1){f[0].reset();for (int i1;in;i) f[0]^(f[1]a[i]);} else f[0]f[1];}coutf[0][0]\n;}return 0;
}
