[SDOI2019] 移动金币

分析

阶梯NIM模型：共有m+1堆石子，石子总数不超过n-m，求必胜的，即奇数堆石子数目异或和非零的局面数。补集转化，答案C(n,m)-奇数堆石子数目异或和位0的局面数。

可以想到按位dp，设f[i,j]表示已经考虑了前i位（异或和0），石子和为j的方案数；转移时考虑下一位出现的被统计1的个数k，k为偶数，带系数C((m+1)/2,k)，即m+1/2个奇数堆中出现k个1的方案。

最后将没有分配的n-m-i个石子放入m/2个偶数堆中，可以一个都不放。

实现

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=2e5+10;

const int mod=1e9+9;

int n,m;

ll fc[N],fv[N],f[20][N];

inline ll c(int n,int m) {

	return fc[n]*fv[m]%mod*fv[n-m]%mod;

}

int main() {

	scanf("%d%d",&n,&m);

	fc[0]=fc[1]=fv[0]=fv[1]=1;

	for(int i=2; i<=n+m; ++i) fv[i]=fv[mod%i]*(mod-mod/i)%mod;

	for(int i=2; i<=n+m; ++i) fv[i]=fv[i-1]*fv[i]%mod,fc[i]=fc[i-1]*i%mod;

	f[19][0]=1;

	for(int i=19; i; --i)

	for(int j=0; j<=n-m; ++j) if(f[i][j])

		for(int k=0; k<=(m+1)/2&&j+(k<<(i-1))<=n-m; k+=2)

			(f[i-1][j+(k<<(i-1))]+=f[i][j]*c((m+1)/2,k)%mod)%=mod;

	int ans=c(n,m);

	for(int i=0; i<=n-m; ++i) ans=(ans-f[0][i]*c(n-m-i+m/2,m/2)+mod)%mod;

	printf("%d\n",ans);

	return 0;

}

暴力

#include <bits/stdc++.h>

#include <typeinfo>

#define ll long long

using namespace std;

const int N=255;

const int M=55;

const int mod=1e9+9;

int n,m,T;

int f[M][N][N<<2];

inline void add(int&x,int y) {

    if((x+=y)>=mod) x-=mod;

}

int main() {

    scanf("%d%d",&n,&m);

    for(T=1; T<n; T<<=1);

    f[0][0][0]=1;

    for(int j=0; j<m; ++j) {

        int(&F)[N][N<<2]=f[j+1];

        int(&G)[N][N<<2]=f[j];

        if(j&1) {

            for(int i=j; i<=n; ++i)

            for(int p=0; p<T; ++p) if(G[i][p])

            for(int k=i+1; k<=n; ++k)

                add(F[k][p],G[i][p]);

        }

        else {

            for(int i=j; i<=n; ++i)

            for(int p=0; p<T; ++p) if(G[i][p])

            for(int k=i+1; k<=n; ++k)

                add(F[k][p^(k-i-1)],G[i][p]);

        }

    }

    int ans=0;

    for(int i=m; i<=n; ++i)

    for(int p=1; p<T; ++p)

        add(ans,f[m][i][p]);

    printf("%d\n",ans);

    return 0;

}

巴特西

[SDOI2019] 移动金币

分析

实现

暴力

最新文章

热门文章