题目：
Homework of Politics
After the Politics class, the teacher gives the student a homework.But Nobita and Takeshi don't like this homework at all.So they decide to play a game, and the person who lost will do the homework of them.This game is like this.At first Nobita chose one or more numbers from [1,n], he can chose all numbers,but each number can be chosed at most once.We think that Nobita choses m numbers, which are a1,a2,...,am.And then they will find m heap of stones, for the ith heap of stone, there are ai stones.And then Nobita and Takeshi will play the game in turn, Nobita plays the first turn.On each turn, the person should chose one heap of stones, and take one or more stones from this heap.And if the number of stones in this heap before is N, the number of stones in this heap after is M, N%M=0 and M!=0 are needed (% means the mod operation). The person who can't do anything will lost the game.Now Nobita wants to know how many ways Nobita can chose from [1,n], that will make sure Nobita wins the game.
Input
The first line contains an integer n.
(1<=n<=10^6).
Output
Output the answer % 1000000007.
Sample Input
8
Sample Output
192
思路：
首先考虑如何将题目中涉及的博弈问题转化，根据题意，对于一堆石子，其个数为x，我们只能拿(x)的若干个因子，使得剩下的数也是(x)的约数，假设x有$latex f(x) $个素因子，那么就相当于每次只能把(x)的素因子去掉若干个，也就是相当于一个石子数为(f(x))的Nim游戏了。
所以问题就变成了问([1,n])有多少种取法使得对应的f的异或值不为0，注意到一个数的素因子个数是 (O(logn))级别的，对于本题(f(x) < 32)，所以就可以dp做了。
设 (f_{i,j} =前i个数，异或值为j的方案数)，则$$ f_{i,j} = (f_{i-1,j} + f_{i-1,j\,\land\,f[i]}) \,mod \,1e9+7 $$
代码如下：
|
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 58 59 |
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> using namespace std; const int maxn=1e6+1; int f[maxn]; vector<int> prime; void pre() { memset(f,0,sizeof f); for (int i=2;i<maxn;i++) { if (f[i]==0) { prime.push_back(i); f[i]=1; } for(int j=0;j<prime.size()&&i*prime[j]<maxn;j++) { f[i*prime[j]]=f[i]+1; if(i % prime[j] == 0) break; } } } long long dp[maxn][50]; const int mod=1e9+7; int main() { pre(); int n; while(scanf("%d",&n)!=EOF) { dp[0][0]=1; for (int i=1;i<=n;i++) { for (int j=0;j<32;j++) { dp[i][j]=(dp[i-1][j]+dp[i-1][j^f[i]]) % mod; } } long long ans=0; for (int j=1;j<32;j++) { ans=(ans+dp[n][j]) %mod; } printf("%lld\n",ans); } return 0; } |
