首先注意到修改只有立方并且模数非常小！
于是可以只维护每个数被修改的次数然后倍增得到实际值。
然后感觉这种题就有某个结论，可以把某些区间直接判成有解。
那就来猜下这个结论。
首先如果有相同的数肯定有解，所以 \(r-l+1 > v\) 就有解了（逃
显然并没有什么用。
假设某个区间 \([l,r]\) 内无解，则所有 \(2^{r-l+1}\) 个子集的贡献都不同。
然而贡献最多只能到 \(v(r-l+1)\)，所以若 \(2^{r-l+1} > v(r-l+1)\) 则一定有解。
故 \(r-l+1 > 13\) 时有解。
然后考虑一个能跑 \(r-l+1 \le 13\) 的算法。
可以考虑 DP，设 \(f_{i,j}\) 表示前 \(i\) 个数中能不能选出一个总贡献为 \(j\) 的子集。
如果对于某个 \(i\) 有 \(f_{i-1,j}\) 和 \(f_{i-1,j-a-i-1}\) 都为 \(1\) 则意味着有解，因为给后一个状态选出的集合添上一个 \(i\) 就相等了。
转移也类似。
看起来跑不动……？
注意到全是 \(0,1\)，bitset 走起。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using namespace std;
const int N = 1e5;
const int V = 1e3;
const int LG = 17;
int n,m,v;
int a[N + 5],f[LG + 5][V + 5];
int c[N + 5];
inline void update(int x,int k)
{
for(;x <= n;x += lowbit(x))
c[x] += k;
}
inline int query(int x)
{
int ret = 0;
for(;x;x -= lowbit(x))
ret += c[x];
return ret;
}
bitset<13 * V + 5> ans;
int main()
{
scanf("%d%d%d",&n,&m,&v);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 0;i < v;++i)
f[0][i] = i * i * i % v;
for(register int i = 1;i < LG;++i)
for(register int j = 0;j < v;++j)
f[i][j] = f[i - 1][f[i - 1][j]];
for(int op,l,r,flag;m;--m)
{
scanf("%d%d%d",&op,&l,&r);
if(op == 1)
{
if(r - l + 1 > 13)
puts("Yuno");
else
{
flag = 0,ans.reset(),ans[0] = 1;
for(register int i = l,x,s;i <= r;++i)
{
x = a[i],s = query(i);
for(register int j = 0;j <= LG;++j)
(s & (1 << j)) && (x = f[j][x]);
if((ans & (ans << x + 1)).any())
{
flag = 1;
break;
}
ans |= ans << x + 1;
}
puts(flag ? "Yuno" : "Yuki");
}
}
else
update(l,1),update(r + 1,-1);
}
}