LOJ6436 神仙的游戏

目录

• LOJ6436 神仙的游戏
• 题意
• 题解
• Code:

LOJ6436 神仙的游戏

题目传送门

题意

题解

咕咕咕～

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Md=998244353;
const int N=5e5+500;
char s[N];
int vis[N];
vector<int>a,b;

namespace NTT {
  inline int Mul(const int &x,const int &y) {return (ll)x*y%Md;}
  inline int Add(const int &x,const int &y) {return (x+y)>=Md?(x+y-Md):(x+y);}
  inline int Sub(const int &x,const int &y) {return (x-y)<0?(x-y+Md):(x-y);}
  int rev[N<<2|1];
  int Powe(int x,int y) {
    int ans=1;
    while(y) {
      if(y&1) ans=Mul(ans,x);
      x=Mul(x,x);
      y>>=1;
    }
    return ans;
  }

  void DFT(vector<int>&a,int len) {
    for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int i=1;i<len;i<<=1) {
      int wn=Powe(3,(Md-1)/(i<<1));
      for(int j=0;j<len;j+=i<<1) {
    int nw=1,x,y;
    for(int k=0;k<i;k++,nw=Mul(nw,wn)) {
      x=a[j+k],y=Mul(a[i+j+k],nw);
      a[j+k]=Add(x,y);a[i+j+k]=Sub(x,y);
    }
      }
    }
  }

  void IDFT(vector<int>&a,int len) {
    reverse(a.begin()+1,a.end());
    DFT(a,len);
    int Inv=Powe(len,Md-2);
    for(int i=0;i<len;i++) a[i]=Mul(a[i],Inv);
  }

  vector<int> MUL(vector<int>a,vector<int>b) {
    int len,n=a.size(),m=b.size();
    for(len=1;len<n+m-2;len<<=1);
    a.resize(len),b.resize(len);
    for(int i=0;i<len;i++) {
      rev[i]=(rev[i>>1]>>1)|(i&1?len>>1:0);
    }
    DFT(a,len);DFT(b,len);
    for(int i=0;i<len;i++) a[i]=Mul(a[i],b[i]);
    IDFT(a,len);
    return a;
  }
}

int main() {
  scanf("%s",s);
  int n=strlen(s);
  a.resize(n),b.resize(n+1);
  for(int i=0;i<n;i++) {
    if(s[i]=='0') a[i]=1;
    if(s[i]=='1') b[i]=1;
  }
  reverse(b.begin(),b.end());
  a=NTT::MUL(a,b);
  ll ret=(ll)n*n;
  for(int i=1;i<n;i++) {
    int f=1;
    int t=n-i;
    for(int j=t;j<n;j+=t) {
      if(a[n-j]||a[n+j]) f=0;
    }
    if(f) ret^=(ll)i*i;
  }
  printf("%lld\n",ret);
  return 0;
}

LOJ6436 神仙的游戏

原文：https://www.cnblogs.com/Apocrypha/p/10153596.html