题解 P5527 [Ynoi2012] NOIP2016 人生巅峰
Lynkcat
·
·
题解
稀里糊涂地跑出了目前最优解
抽屉原理可知，总共选集合的方案有 2^{len}-1 种 而总和最多只有 1000\times len 种，根据抽屉原理，当 len>13 时必然有解。
接下来考虑 len\leq 13 的时候怎么做。
很多题解写的是 bitset 优化 dp，但我们其实考虑直接暴力就行。
$len$ 最大是 $13$ ，所以看上去很慢，但是实际上当 $len$ 较大的时候跑到相同的集合可能性是比较大的，所以直接退出能减少很多不必要的枚举。
值得注意的一点是很多人可能会写成 $2^{len}\times len$，多了一个判断每一位是否在当前枚举的集合里然后求和的过程，但实际上这个可以做，设 $mask$ 是当前集合，$last$ 是 $mask$ 中最后一个 $1$ 的位置，那么直接 $s_{mask}=s_{mask-2^{last}}+a_{last}$ 即可。
[这样子你已经能拿到最优解了。](https://www.luogu.com.cn/record/56355694)
[诶，我把 $len$ 的上界调到 $11$ 会咋样](https://www.luogu.com.cn/record/56355136)
[诶，我把 $len$ 的上界调到 $9$ 会咋样](https://www.luogu.com.cn/record/56355951)
```c++
//QwQcOrZ yyds!!!
#include<bits/stdc++.h>
#define ll long long
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define R(i,a,b) for (int i=(a);i<(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define go(i,x) for (int i=head[x];i;i=e[i].nx)
#define mp make_pair
#define pb push_back
#define pa pair < int,int >
#define fi first
#define se second
#define re register
#define be begin()
#define en end()
#define sqr(x) ((x)*(x))
#define ret return puts("-1"),0;
#define put putchar('\n')
#define inf 1000000005
#define mod 998244353
#define int ll
#define N 1000005
using namespace std;
inline char gc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
// #define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
int n,m,q,mx,o,l,r,a[N],dp[505*1005],c[N],tong[1005*505],f[N][25],b[N],s[6005];
inline void update(int x,int y)
{
if (x==0)return;
while (x<=n)
{
c[x]+=y;
x+=(x&(-x));
}
}
inline int query(int x)
{
int res=0;
while (x>0)
{
res+=c[x];
x-=(x&(-x));
}
return res;
}
inline void sub1()
{
for (re int i=0;i<m;i++)
{
f[i][0]=i*i%m*i%m;
}
for (re int i=1;i<=20;i++)
for (int j=0;j<m;j++)
f[j][i]=f[f[j][i-1]][i-1];
int Lg[6025];
for (re int i=0;i<=11;i++) Lg[1<<i]=i;
while (q--)
{
o=read(),l=read(),r=read();
if (o==2)
{
update(l,1),update(r+1,-1);
}
else
if (r-l+1>13) puts("Yuno");
else
{
for (re int i=l;i<=r;i++)
{
int now=a[i],x=query(i);
for (int j=20;j>=0;j--)
if ((x>>j)%2) now=f[now][j];
b[i-l]=now+1;
}
int n=r-l+1,bl=0;
s[0]=0;
for (re int stat=1;stat<(1<<n);stat++)
{
int now=stat&(stat-1),ls=stat-now;
s[stat]=s[now]+b[Lg[ls]];
tong[s[stat]]++;
if (tong[s[stat]]>=2)
{
bl=1;
break;
}
}
if (bl) puts("Yuno");
else puts("Yuki");
for (re int stat=1;stat<(1<<n);stat++)
{
tong[s[stat]]=0;
s[stat]=0;
}
}
}
}
signed main()
{
n=read(),q=read(),m=read();
for (int i=1;i<=n;i++) a[i]=read();
sub1();
}
/*
*/
```