J-Melborp Elcissalc

题目大意：
构造一个长度为n的序列，每个位置的数字在[0,k-1]之间，求连续区间和为k的倍数的方案数。

思路：
看到区间和，比较常见的处理就是前缀和了，从本题中可以发现区间和为k倍数的区间两端的前缀和模k是相同的，即区间[i,j]的和为k的倍数，那么sum[i]%k==sum[j]%k。因此，如果有m个前缀和相同，那么这m个前缀和可以两两组成C(2,m)个区间。本题的第一个转换就是从枚举区间到枚举前缀和。再进一步，组合的数量和前缀和的位置无关，因此只要每种前缀和的数量确定了，就可以确定组成的区间数量。
于是将状态定义为：

dp[i][j][k]表示从[0,i]的数字中一共选了j个作为前缀和，组合数为k种的方案数。
这么设计的原因：
动态规划要求无后效性，因为只有相同的前缀和才能进行组合，因此第一维作为数字，当加入新的数字时，增加的组合数和之前的数是无关的。
后两维主要是为了递推，有了第一维后就很容易得出后两维了。
1
2
3
4

状态转移方程稍微复杂一点

dp[i][j][k] = dp[i-1][j-x][k-C(2,x)]*C(n-j+x,x); //C(n-j+x,x)表示从n个位置里减去已经选的j-x个位置后任选x个的情况
也可以写成：
dp[i][j+x][k+C(2,x)] = dp[i-1][j][k] * C(n-j,x)
枚举x即可。
1
2
3
4

需要注意的是i=0的情况要特殊讨论，因为一个0也可以是符合的区间。

第一种转移方式的常数较小，第二种方式写得不好可能会被卡常
AC代码：

#include 
#define mem(a, v) memset(a, v, sizeof(a))
const long long mod = 998244353;
using namespace std;

long long dp[70][70][5000], C[70][70];

signed main()
{
    int n, k, t;
    cin >> n >> k >> t;
    mem(dp, 0), mem(C, 0);
    for (int i = 0; i < 70; i++) //递推组合数
    {
        for (int j = 0; j <= i; j++)
        {
            if (!j)
                C[i][j] = 1;
            else
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }

    for (int i = 0; i <= n; i++) //i==0的情况特殊处理
        dp[0][i][C[i + 1][2]] = C[n][i];
    for (int i = 1; i <= k - 1; i++)
        for (int j = 0; j <= n; j++)
            for (int x = 0; x <= j; x++)
                for (int p = C[x][2]; p <= t; p++)
                    (dp[i][j][p] += dp[i - 1][j - x][p - C[x][2]] * C[n - j + x][x]) %= mod;

    cout << dp[k - 1][n][t];
    return 0;
}
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

K-Great Party

题目大意：
有若干堆石子，两个人轮流取石子，每次取至少一个，取完后可以把取的那堆剩下的石子合并到另一堆中，也可以不合并。给定一个区间，求出有多少子区间满足先手必赢。

思路：

• 只有1堆的时候显然先手必胜。
• 考虑2堆的情况，两个人都不会进行合并操作，因为合并成1堆后就输了，因此变成了普通的nim游戏，异或和不为0时先手必胜。
• 考虑3堆的情况，先手总能选择一堆将其合并到另一堆中，使得剩下的2堆异或和为0。因此3堆先手必胜。
• 考虑4堆的情况，两个人都不会进行合并操作，一旦谁让堆数减1变成3堆，那就输了，因为前期谁都不会让堆数减少，所以一定会出现所有的堆都是1的情况，因此将所有的堆减1，看谁将减1后的最后一个石子取完，那么另一个人就要去都是1的堆里取石子，也就必然会使得堆数减1，就变成了普通的nim游戏。
• 考虑5堆的情况，先手选择一堆合并使得剩下4堆减1异或和为0，后手在面对4堆的情况时如果不选择合并，就是普通的nim游戏，必输，如果选择合并，3堆的情况先手必胜，因此还是会输。
• …

所以可以用归纳法推得一个结论： 奇数堆时先手必胜，偶数堆时减1异或和不为0先手必胜。

因此问题就简化为求一个区间内有多少偶数长度的子区间减1异或和不为0，因为题目是离线查询，可以用莫队算法处理。

AC代码：

#include 
const int N = 1e6 + 5;
using namespace std;

struct node
{
    int id, l, r;
} nd[N];
int xors[N], cnt[2][N * 2], len; // cnt[i][j]记录从第一个位置开始，长度&1==i，异或和为j的区间数量
long long res, ans[N];

bool cmp(node a, node b)
{
    if (a.l / len != b.l / len) return a.l / len < b.l / len;
    return a.r < b.r;
}
void add(int x)
{
    //与长度同为奇偶的区间异或为0
    res += cnt[x & 1][xors[x]];
    cnt[x & 1][xors[x]]++;
}

void del(int x)
{
    //与add中的顺序相反
    cnt[x & 1][xors[x]]--;
    res -= cnt[x & 1][xors[x]];
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, q, x;
    cin >> n >> q;
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        xors[i] = (x - 1) ^ xors[i - 1]; //记录异或前缀和
    }
    for (int i = 1; i <= q; i++)
    {
        cin >> nd[i].l >> nd[i].r;
        nd[i].id = i;
    }
    sort(nd + 1, nd + 1 + q, cmp);
    int L = 1, R = 0; //上一次的区间范围[L-1,R]
    cnt[0][0] = 1;    //长度为0，异或和为0的情况
    for (int i = 1; i <= q; i++)
    {
        while (R < nd[i].r)
            add(++R);
        while (R > nd[i].r)
            del(R--);
        while (L > nd[i].l)
        {
            L--;
            add(L - 1);
        }
        while (L < nd[i].l)
        {
            del(L - 1);
            L++;
        }
        //所有区间的情况减去长度为偶数且异或和为0的区间数量就是答案
        ans[nd[i].id] = (nd[i].r - nd[i].l + 1ll) * (nd[i].r - nd[i].l + 2ll) / 2 - res;
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
    return 0;
}
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
63
64
65
66
67
68
69
70
71
72