39 与 93
简化题面
给定 \(n\) 堆石子，第 \(i\) 堆石子数量为 \(a_i\) ，你是先手，你现在可以删除 \(x\) 堆石子，满足 \(0\leq x\leqq n-1\) 并且 \(s|x\) ，问你必胜的方案数。
\(n\leq 5 \cdot 10^5,\sum_i a_i\leq 10^7,s\leq 10\) 。
简要题解
首先显然的博弈论，摆出 \(nim\) 游戏的结论：若各堆石子异或和为 0，则满足先手必胜，否则后手必胜 。
那么此题就是要我们求出有多少种方案，满足在 \(n\) 堆石子中取出 \(s\) 的倍数堆，满足这几堆石子数量的异或和等于 \(n\) 堆石子的异或和。
考虑 \(DP\) ,我们设 \(f_{i,j,k}\) 表示考虑完前 \(i\) 堆石子，当前删除的石子堆数模 \(s=j\) ，当前异或和为 \(k\) 的方案数。
然后我们考虑优化：
时间优化
由于\(\sum a_i\leq 10^7\) ，并且假设当前考虑的数的最大值的二进制最高位为 \(s\) ，那么最大的异或和一定小于 \(2s\) ，于是我们可以将 \(a\) 数组从大到小排序，每次限制 \(k\) 这一维的枚举范围即可。
空间优化
滚动数组优化即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,P=1e9+7;
inline int read() {
int x=0,w=0; char ch=getchar();
while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
while(isdigit(ch)) x=x*10+(ch^48), ch=getchar();
return w?-x:x;
}
int n,s,sum,a[N],f[10][1<<20|1],b[1<<20|1];
inline void Add(int &x,int y) { x+=y-P; x+=(x>>31)&P; }
int main() {
n=read(); s=read(); for(int i=1;i<=n;i++) a[i]=read(), sum^=a[i];
sort(a+1,a+1+n);
f[0][0]=1;
for(int i=1,m=1;i<=n;i++) {
while(m<=a[i]) m<<=1;
for(int j=0;j<m;j++) b[j]=f[s-1][j];
for(int j=s-1;j;j--)
for(int k=0;k<m;k++) Add(f[j][k],f[j-1][k^a[i]]);
for(int j=0;j<m;j++) Add(f[0][j],b[j^a[i]]);
}
printf("%d\n",(f[0][sum]-(n%s==0)+P)%P);
return 0;
}
zbox 的刷题
简要题面
现在有 \(n\) 道题目，在任意时刻，做对任意一道题的概率为 \(p\) ，你要把所有题目都做完，你会先把所有的题目先做一遍，再把错误的题目都拿出来再做一遍，以此往复，直到做完为止，每次做题的疲劳程度为 \(ax+b\) ，\(x\) 表示这一轮的题目数量，问做完所有题目的期望疲劳程度。
简要题解
我们把贡献拆开来考虑，发现每一道题目，它做一次就会产生 \(x\) 的疲劳程度，并且每一道题做的期望次数都是 \(\frac{1}{1-p}\) ，所以 \(a\) 的贡献就是 \(\frac{na}{1-p}\) ，再来考虑 \(b\) 这一部分。
\(b\) 的贡献与做题的轮数有关，而做题的轮数的期望取决于完成的最后一道题的期望次数，即 \(E(max_{x\in s}{f(x)})\) ，\(f(x)\) 为完成第 \(x\) 道题目的期望次数，对于这个式子我们考虑 \(Min-Max\)容斥。
\(E(max_{x\in s}f(x))=\sum_{T\in s} (-1)^{|T|-1}E(min_{x\in T}f(x))=\sum_{T\in s} (-1)^{|T|-1}\frac{1}{1-p^{|T|}}=\sum_{i=1}^n(-1)^{i-1}\frac{1}{1-p^i}\)
第二步的推导是因为 \(E(min_{x\in T}f(x))\) 表示最早被做对的题目的期望次数，那么每一次没有一道题做对的概率为 \(p^{|T|}\) ，因此该式值就等于 \(\frac{1}{1-p^{|T|}}\) 。
直接将两部分的贡献加起来就行了。
code
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,P=998244353;
int n,u,v,a,b,s1,s2,p,fac[N],ifac[N];
inline void Add(int &x,int y) { x+=y-P; x+=(x>>31)&P; }
inline int C(int x,int y) { return 1LL*fac[x]*ifac[y]%P*ifac[x-y]%P; }
inline int Power(int a,int b) { int res=1; for(;b;b>>=1,a=1LL*a*a%P) if(b&1) res=1LL*res*a%P; return res; }
int main() {
cin>>n>>u>>v>>a>>b;
p=1LL*u*Power(v,P-2)%P;
s1=1LL*a*n%P*Power((1-p+P)%P,P-2)%P;
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%P;
ifac[n]=Power(fac[n],P-2);
for(int i=n-1;i>=1;i--) ifac[i]=1LL*ifac[i+1]*(i+1)%P;
for(int i=1,o=p;i<=n;o=1LL*o*p%P,i++)
if(i&1) Add(s2,1LL*C(n,i)*Power((1-o+P)%P,P-2)%P);
else Add(s2,P-1LL*C(n,i)*Power((1-o+P)%P,P-2)%P);
Add(s1,1LL*s2*b%P);
cout<<s1<<endl;
return 0;
}
原文地址：http://www.cnblogs.com/oscaryangzj/p/16848622.html
