Solution：P11897 「LAOI-9」多维空间中的游戏

以下

n

代表原题面中的

k

。

首先这个游戏显然就是当

\operatorname{popcount}(a\cup b)

为奇数时先手必胜。也就是说题目的意思是我们要对

0\leq a<2^n

求

1-\sum_{i=l}^{r}[\operatorname{popcount}(a\cup i)\equiv 1\pmod 2]p_i=1-\frac 12\sum_{i=l}^{r}p_i-(-1)^{n-\operatorname{popcount}((2^n-1-a)\cap (2^n-1-i))}p_i

显然后面那个东西就是 xor-FWT 的定义式，也就是说我们只要只保留

p_{2^n-1-r\sim 2^n-1-l}

然后做 FWT 就完事了，时间复杂度

\Omicron(nq2^n)

。

然后我们发现这个东西被卡常了过不去。首先加个fread，接下来我们注意两个地方：

FWT 的过程中不要取模。
可以发现，FWT 每做一层只有一个区间是有值的，那么如果我们当前遍历到的区间没有值就直接跳过。

这样就能做到最大点在 1.4s 内通过。

注意以下代码做的其实是 xnor-FWT。

CPP

#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>

#define rgall(arr) (arr).begin(),(arr).end()
#define rgcnt(arr,cnt) (arr).begin(),(arr).begin()+(cnt)
#define rgo1(arr,cnt) (arr).begin()+1,(arr).begin()+1+(cnt)
#define rgany(arr,cnt,offset) (arr).begin()+(offset),(arr).begin()+(offset)+(cnt)

using namespace std;

inline char nc()
{
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int reader()
{
	char ch=nc();
	int sum=0;
	int flag=1;
	while(!(ch>='0'&&ch<='9'))
	{
		if(ch=='-')flag=-1;
		ch=nc();
	}
	while(ch>='0'&&ch<='9')
		sum=sum*10+ch-48,ch=nc();
	return sum*flag;
}

constexpr int moder=998244353,inv_2=moder+1>>1,neg_1=moder-1;

inline int fast_mod(int x)
{
    return x-(x>=moder?moder:0);
}

array<long long,1<<16> vals,val0;

int main(int argc,char* argv[],char* envp[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int outflag;
    unsigned int seed;
    reader(),outflag=reader();
    if(outflag)
        seed=reader();
        // cin>>seed;
    int n=reader();
    // cin>>n;
    const int S=(1<<n)-1;
    for(int i=0;i<1<<n;i++)
        vals[i]=reader();
    int cntq=reader();
    // cin>>cntq;
    for(int q=1;q<=cntq;q++)
    {
        int cntq0,rgl,rgr;
        // cin>>cntq0>>rgl>>rgr;
        cntq0=reader(),rgl=reader(),rgr=reader();
        val0.fill(0);
        long long sum=0;
        for(int i=rgl;i<=rgr;i++)
            sum+=val0[i]=vals[i];
        for(int i=1,curl=rgl,curr=rgr;i<1<<n;curl-=i,curr+=i,i<<=1)
        {
            for(int j=0;j<1<<n;j+=i<<1)
            {
                if(j>curr||j+i+i<curl)
                    continue;
                for(int k=0;k<i;k++)
					val0[i|j|k]=-val0[j|k]-val0[i|j|k],val0[j|k]=val0[i|j|k]+val0[j|k]*2;
            }
            // for(int i=0;i<1<<n;i++)
            //     cerr<<val0[i]<<' ';
            // cerr<<endl;
        }
        int answer=0;
        for(int i=1;i<=cntq0;i++)
        {
            int a;
            if(outflag)
                a=seed*i*q*50007&S;
            else
                a=reader();
                // cin>>a;
            a=(1-(sum-val0[a])/2%moder+moder)%moder;
            if(outflag)
                answer^=a;
            else
                cout<<a<<' ';
        }
        if(outflag)
            cout<<answer;
        cout<<'\n';
    }
    return 0;
}

Solution：P11897 「LAOI-9」多维空间中的游戏

文章操作

相关推荐

评论

Solution：P11897 「LAOI-9」多维空间中的游戏