洛谷 5527 「Ynoi 2012」NOIP2016 人生巅峰

首先注意到修改只有立方并且模数非常小！
于是可以只维护每个数被修改的次数然后倍增得到实际值。

然后感觉这种题就有某个结论，可以把某些区间直接判成有解。
那就来猜下这个结论。

首先如果有相同的数肯定有解，所以 r−l+1>v 就有解了（逃
显然并没有什么用。

假设某个区间 [l,r] 内无解，则所有 2r−l+1 个子集的贡献都不同。
然而贡献最多只能到 v(r−l+1)，所以若 2r−l+1>v(r−l+1) 则一定有解。
故 r−l+1>13 时有解。

然后考虑一个能跑 r−l+1≤13 的算法。
可以考虑 DP，设 fi,j 表示前 i 个数中能不能选出一个总贡献为 j 的子集。
如果对于某个 i 有 fi−1,j 和 fi−1,j−a−i−1 都为 1 则意味着有解，因为给后一个状态选出的集合添上一个 i 就相等了。
转移也类似。

看起来跑不动……？
注意到全是 0,1，bitset 走起。

代码：

#include <cstdio>
#include <bitset>
#define lowbit(x) ((x) & -(x))
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);
    }
}