AtCoder Regular Contest 116 D

https://atcoder.jp/contests/arc116/tasks/arc116_d

题意：
给出2个正整数n和m，询问可以构造多少个长为n的数列，满足(1<=a[i]<=m),数列和为m，数列异或和为0

因为要求异或和为0，所以每个2的幂次在数列中要出现偶数次
将m拆分为若干个2的幂次，每个2的幂次都是偶数个，就满足和为m且异或和为0的条件
将问题转化为有一个容积为m的分组背包，有(log_2 (m))个组，第i个组的若干个物品的体积分别为(2k*2^{i}),(k∈N^{+})且(2k*2^{i}<=m)
往背包里放体积为(2k*2^{i})的物品，就相当于把(2k)个为(2^{i})分给序列里的n个数
所以有有(C_{n}^{2k})种方式
所以转移方程为(f[j]+=f[j-2k*2^{i}]*C_{n}^{2k})

#include<cstdio>
 
#define mod 998244353
#define N 5001
 
int f[N],C[N][N];
 
int main()
{
	int n,m,t;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;++i)
	{
		C[i][0]=1;
		for(int j=1;j<=i;++j) 
		{
			C[i][j]=C[i-1][j-1]+C[i-1][j];
			if(C[i][j]>=mod) C[i][j]-=mod;
		}
	}
	f[0]=1;
	for(int i=0;i<=11;++i)
	{
		t=(1<<i)<<1;
		for(int k=m;k>=t;--k)
			for(int j=t,l=2;j<=k;j+=t,l+=2)
			{
				f[k]+=1ll*f[k-j]*C[n][l]%mod;
				if(f[k]>=mod) f[k]-=mod;
			}
	}
	printf("%d",f[m]);
}