题解：P3447 [POI 2006] KRY-Crystals

bamboo12345 · 2025-10-14 19:59:55 · 题解

题意：给定 n 个正整数 m_1 到 m_n，对长度为 n 且满足以下条件的整数序列 a 计数：

• 对于任意 1\le i\le n，0\le a_i\le m_i；

做法：

首先我们考虑，如果有一个最大的数满足 a_i = 2^k-1，那么很好的一点是，我们可以令其他的元素随意选择，最后这个数去调整即可。

那么对于正常的情况显然没有这么好的事。我们先按照正常的跟 bit 的题，考虑从高位往地位去确定，发现一个事情，如果我有一个数没有上到上限，那么就等于他变成了我们上面所述的那个可以 a_i=2^{k}-1 的情况！所以我们可以直接枚举到哪一位出现了这种情况然后 dp 那一位。

我们记 dp_{i,0/1,0/1} 代表考虑到了第 i 个元素，目前这一位的异或值为 0/1，是否已经有了可以随意支配的元素。

转移直接就是枚举这一位是什么，是否会成为随意支配元素，乘上对应的权即可，具体可以见代码。

注意一些细节，有可能所有数都顶到上界，这种需要特判一下；枚举第 i 位时，需要保证更高位的异或值要是 0，因为保证了都是顶满的直接计算即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 55;
int dp[maxn][2][2], n, a[maxn], s;
unsigned int ans;
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], s ^= a[i];
    ans = !s, s = 0;
    for (int i = 31; i >= 0; i--) {
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        s = 0;
        int all = (1ll << i) - 1;
        for (int j = 1; j <= n; j++) {
            int t = ((a[j] >> i) & 1);
            if(!t) {
                for (int x = 0; x <= 1; x++)
                    for (int y = 0; y <= 1; y++)
                        dp[j][x][y] = dp[j - 1][x][y] * ((a[j] & all) + 1);
            }
            else {
                dp[j][0][0] = dp[j - 1][1][0] * ((a[j] & all) + 1);
                dp[j][1][0] = dp[j - 1][0][0] * ((a[j] & all) + 1);
                dp[j][0][1] = dp[j - 1][1][1] * ((a[j] & all) + 1) + dp[j - 1][0][1] * (all + 1) + dp[j - 1][0][0];
                dp[j][1][1] = dp[j - 1][0][1] * ((a[j] & all) + 1) + dp[j - 1][1][1] * (all + 1) + dp[j - 1][1][0];
            }
            s ^= (a[j] >> i + 1);
        }
        if(!s)
            ans += dp[n][0][1];
    //  cout << i << " " << ans << " " << (a[2] & all) << endl;
    }
    cout << ans - 1 << endl;
    return 0;
}