首页 > ACM题库 > HDU-杭电 > HDU 3693-Math teacher’s homework[解题报告]HOJ
2014
11-30

HDU 3693-Math teacher’s homework[解题报告]HOJ

Math teacher’s homework

问题描述 :

Mr. Furion is a math teacher. His students are very lazy and they do not like to do their homework. One day, Mr. Furion decides to give them a special problem in order to see whether his students are talents in math or they are just too lazy to do their homework. The problem is:

Given an integer k, n integers m1,m2…mn, and a formula below:

X1 xor X2 xor X3… xor Xn = k

Please figure out that how many integral solutions of the formula can satisfy:

0<=Xi<=mi (i=1…n)

输入:

There are at most 100 test cases.

The first line of each test case contains two integers n and k. The second line of each test contains n integers: m1,m2…mn. The meaning of n,k, m1,m2…mn are described above. (1<=n<=50,0<=k,m1,m2…mn<=2^31-1 )

The input is ended by “0 0”.

输出:

There are at most 100 test cases.

The first line of each test case contains two integers n and k. The second line of each test contains n integers: m1,m2…mn. The meaning of n,k, m1,m2…mn are described above. (1<=n<=50,0<=k,m1,m2…mn<=2^31-1 )

The input is ended by “0 0”.

样例输入:

11 2047
1024 512 256 128 64 32 16 8 4 2 1
10 2047
1024 512 256 128 64 32 16 8 4 2 
0 0

样例输出:

1
0

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define INF 305
#define inf 0x0f0f0f0f
#define MOD 1000000003LL

using namespace std;
long long F[55][55],Num[55];
int main()
{
 int n,k,i,j,t,tot;
 long long ans,now;
 while (scanf("%d%d",&n,&k),n)
 {
 for (i=1;i<=n;i++)
 scanf("%I64d",&Num[i]);
 for (ans=0,t=30;t>=0;t--)
 {
 memset(F,0,sizeof(F));
 for (tot=0,now=1<<t,F[0][0]=i=1;i<=n;i++)
 {
 if (now&Num[i]) {
 for (tot++,j=0;j<tot;j++)
 F[i][j]=(F[i-1][j]*(Num[i]-now+1))%MOD;
 F[i][1]=(F[i][1]+F[i-1][0])%MOD;
 for (j=2;j<=tot;j++)
 F[i][j]=(F[i-1][j-1]*(now)+F[i][j])%MOD;
 Num[i]-=now;
 }
 else {
 for (j=0;j<=tot;j++)
 F[i][j]=(F[i-1][j]*(Num[i]+1))%MOD;
 }
 }
 for (j=1;j<=tot;j++)
 if (((tot-j)&1)==((k>>t)&1))
 ans=(ans+F[n][j])%MOD;
 if (((k>>t)&1)!=(tot&1)) break;
 }
 if (t==-1) ans=(ans+1)%MOD;
 printf("%I64d\n",ans);
 }
 return 0;
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。