营销网站的建设流程,网站 英语,做宣传网站,一等一网站建设正题
题目链接:https://www.luogu.com.cn/problem/P3214 题目大意
一个由1∼n1\sim n1∼n的所有整数构成的集合SSS#xff0c;求出它的mmm个不同非空子集满足每个元素都出现了偶数次。 解题思路
集合的话不用考虑顺序#xff0c;可以输出有序的答案除以m!m!m!就好了。
选…正题
题目链接:https://www.luogu.com.cn/problem/P3214 题目大意
一个由1∼n1\sim n1∼n的所有整数构成的集合SSS求出它的mmm个不同非空子集满足每个元素都出现了偶数次。 解题思路
集合的话不用考虑顺序可以输出有序的答案除以m!m!m!就好了。
选iii个的话考虑偶数次的条件无论前面i−1i-1i−1个集合如何选取最后一个都能根据情况调整过来所以不考虑重复的话方案就是P2ni−1P_{2^n}^{i-1}P2ni−1 设fif_ifi表示选出iii个集合的答案因为上面那种方案可能会导致最后一个集合出现重复等问题我们要减去不合法的。
首先有可能是空集那么表示前面i−1i-1i−1个集合都是合法的所以方案是fi−1f_{i-1}fi−1。然后是重复考虑和它重复的集合jjj那么剩下i−2i-2i−2个就是合法的然后这两个重复的集合有2n−(i−2)−12^n-(i-2)-12n−(i−2)−1种取值减去空集和前面出现过的方案就是fi−2×(i−1)×(2n−i1)f_{i-2}\times (i-1)\times(2^n-i1)fi−2×(i−1)×(2n−i1)
所以方程就是fiP2ni−1−fn−1−fn−2×(i−1)×(2n−i1)f_iP_{2^n}^{i-1}-f_{n-1}-f_{n-2}\times(i-1)\times(2^n-i1)fiP2ni−1−fn−1−fn−2×(i−1)×(2n−i1)
O(n)O(n)O(n)转移即可。 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610,P1e87;
ll n,m,A[N],f[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
signed main()
{scanf(%lld%lld,m,n);ll p1;for(ll i1;im;i)pp*2ll%P;ll fac1;A[0]1;for(ll i1;in;i)A[i]A[i-1]*(p-i)%P,facfac*i%P;f[0]1;for(ll i2;in;i)f[i](A[i-1]-f[i-1]-f[i-2]*(i-1)%P*(p-i1)%P)%P;f[n]f[n]*power(fac,P-2)%P;printf(%lld\n,(f[n]P)%P);return 0;
}
