2019-11-02 14:30:58

$[l,r]$ 的非空子集数为 $2^{r-l+1}-1$ ，而子集贡献数至多为 $1000(r-l+1)$ 。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#define re register
using namespace std;

int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}

const int N=100000+10,P=1000+10;

int n,Q,mod;
int a[N],f[17][P];
bitset<P*13> dp;

int c[N];
inline void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]+=y; }
inline int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

int main() {

for (re int i=0;i<mod;++i) f[0][i]=i*i*i%mod;
for (re int i=1;i<17;++i)
for (re int j=0;j<mod;++j)
f[i][j]=f[i-1][f[i-1][j]];

while (Q--) {
else {
if (r-l+1>13) { puts("Yuno"); continue; }
int flag=0; dp.reset(); dp[0]=1;
for (re int i=l;i<=r;++i) {
int x=a[i],t=sum(i);
for (re int i=16;~i;--i)
if (t&(1<<i)) x=f[i][x];
++x;
if ((dp&(dp<<x)).any()) flag=1;
dp|=dp<<x;
}
puts(flag?"Yuno":"Yuki");
}
}
return 0;
}
• star
首页