bndsoj0758 A. 2018-8-12noip模拟测验(一)-篮球比赛1

定义 \(f[i][j]\) 为从\([1,i]\)中选出若干数使得他们异或和为 \(j\),并且 \(i\) 在集合中的方案数,
\(g[i][j]\) 为在\([i+1,n]\)中选若干数使得其按位与和为 \(j\),并且 \(i\) 在集合中的方案数

有转移方程:$$f[i][j\hat{}a[i]]=\sum_{k=1}^{i-1}f[k][j]$$

$$g[i][j\&a[i]]=\sum_{k=i+1}^{n}g[k][j]$$

答案即为:

$$ans=\sum_{i=1}^{n}\sum_{j=1}^{n}\left[\left(\sum_{k=1}^{i}f[k][j]\right)*g[i+1][j]\right]$$

代码写出来再补

发表评论

电子邮件地址不会被公开。 必填项已用*标注