Project Euler 409

Posted on | Views:

$dp$ 计数.

记 $p(i)=\prod_{j=2^n-i}^{2^n-1} j$ ,即不考虑胜负情况的所有合法方案.

记 $f(i)=p(i)-W(i)$ ,即先手必败的状态数,考虑如何求出 $f(i)$ .

让前 $i-1​$ 个数随便选,共有 $p(i-1)​$ 种情况,最后一个数通过恰当的选法使得所有数的异或和为 $0​$ .

考虑将不合法的情况减掉,由于不能选 $0​$ ,所以前 $i-1​$ 个数异或和为 $0​$ 时,就不合法.

由于不能选相同的元素,所以当前 $i-1​$ 个数中,有 $i-2​$ 个数异或和为 $0​$ 时,剩下一个数怎么选都不合法.

剩下的这个数有 $i-1$ 个的可能的位置,由于前面的数没有重复,所以每个位置有 $2^n-i+1$ 个可能的值.

将这两种情况减掉,得到
$$
f(i)=p(i-1)-f(i-1)-(i-1)\cdot (2^n-i+1) \cdot f(i-2)
$$
边界有 $f(1)=f(2)=0$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=1e7+10;
int n=10000000,m,p[MAXN],f[MAXN];
int main()
{
	m=add(fpow(2,n),P-1);
	p[1]=m,p[2]=mul(m,add(m,P-1));
	f[1]=f[2]=0;
	for(int i=3;i<=n;++i)
	{
		f[i]=add(p[i-1],P-f[i-1]);
		inc(f[i],P-mul(mul(i-1,add(m+2,P-i)),f[i-2]));
		p[i]=mul(p[i-1],add(m+1,P-i));
	}
	cout<<add(p[n],P-f[n])<<endl;
	return 0;
}