自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 23:12:07，当前版本为作者最后更新于2021-08-19 13:29:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

稀里糊涂地跑出了目前最优解

抽屉原理可知，总共选集合的方案有 $2^{len}-1$ 种 而总和最多只有 $1000\times len$ 种，根据抽屉原理，当 $len>13$ 时必然有解。

接下来考虑 $len\leq 13$ 的时候怎么做。

很多题解写的是 bitset 优化 dp，但我们其实考虑直接暴力就行。

$2^{len}$ 枚举每个集合，然后直接判断之前的集合有没有和当前集合和相同的，找到的话就直接退出。

$len$ 最大是 $13$ ，所以看上去很慢，但是实际上当 $len$ 较大的时候跑到相同的集合可能性是比较大的，所以直接退出能减少很多不必要的枚举。

值得注意的一点是很多人可能会写成 $2^{len}\times len$，多了一个判断每一位是否在当前枚举的集合里然后求和的过程，但实际上这个可以做，设 $mask$ 是当前集合，$last$ 是 $mask$ 中最后一个 $1$ 的位置，那么直接 $s_{mask}=s_{mask-2^{last}}+a_{last}$ 即可。

这样子你已经能拿到最优解了。

诶，我把 $len$ 的上界调到 $11$ 会咋样

诶，我把 $len$ 的上界调到 $9$ 会咋样

//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();
}
/*

*/