题解：P3447 [POI 2006] KRY-Crystals

AC_Lover · 2025-09-11 15:00:34 · 题解

P3447 [POI 2006] KRY-Crystals

简要题意： 求满足 0\le a_i\le m_i，满足 \displaystyle\bigoplus_{i=1}^{n} a_i=0 且 a_i 不全为 0 的分配方案数。

解法：

考虑一个类似数位 \mathrm{dp} 的思路，对于上界 m_i 的限制，可以记录类似【是否脱离上界】的状态来决定 a_i 的取值。并且注意到关键的性质：如果某个数在第 k 位脱离上界，那么更低位的数就可以随便选。

这启发我们考虑这样一种方法：枚举位 k，限定 k 的更高位都顶到上界，并且【存在 a_i 恰好第一次在第 k 位脱离上界】，对其统计方案。

如果有 a_i 在第 k 位脱离上界，那么 a_i 的更低位可以随便取，这样无论其他的数如何选择，a_i 都有且仅有一种方案与之对应，相当于在更低位处异或和为 0 的限制被消除了。设计这样一个 \mathrm{dp} 对其计数：f_{i,0/1,0/1} 表示考虑前 i 个数，当前第 k 位得到的异或值为 0/1，是否已经有脱离上界的数。此时将用于调整的数钦定在第一个脱离上界的数上，防止算重。

用 \mathrm{bit}(x) 表示数 x 的第 k 位，\mathrm{msk}(x) 表示数 x 比第 k 位更低的部分，分类讨论一下转移：

• \mathrm{bit}(m_i)=0

  那么 a_i 仅能取到 \mathrm{bit}(a_i)=0，一定顶到上界，所以这里不会发生脱离上界的跃迁，考虑方案数的贡献，由于顶到上界了，并且比 k 高的位也是顶到上界点，所以此处需要限定 a_i 后面的位不能超过 m_i，方案数就是 \mathrm{msk}(m_i)+1。于是得到转移：

  f_{i,x,y}\leftarrow f_{i-1,x,y}\times [\mathrm{msk}(m_i)+1]
• \mathrm{bit}(m_i)=1
  • \mathrm{bit}(a_i)=0

  于是 a_i 就脱离上界了，由于要将贡献算在第一个脱离上界的位置，如果之前没有脱离上界的数，那么 a_i 是要用来确定异或和位的 0 ，是唯一确定，所以有转移 f_{i,x,1}\leftarrow f_{i,x,0}。否则说明已经存在一个数来保证异或和，这个数比 k 低的位都可以随便选，总共有 2^k 中方案，得到 f_{i,x,1}\leftarrow f_{i,x,1}\times 2^k，总结到

  f_{i,x,1}\leftarrow f_{i,x,0} \\ f_{i,x,1}\leftarrow f_{i,x,1}\times 2^k
  • \mathrm{bit}(a_i)=1

  那么 a_i 依旧顶着上界，类似的：

  f_{i,x,y}\leftarrow f_{i-1,x\oplus 1,y}\times [\mathrm{msk}(m_i)+1]

于是完成了，总方案数就是 f_{n,0,1}。

注意细节：

1. 如果 \displaystyle\bigoplus_{i=1}^{n} m_i=0，那么每一位都不脱离上界是可行的，此时不会被统计到，答案要记上 1。
2. 由于要求 a_i 不全为 0，答案要舍弃全 0，减去 1。

:::info[代码]

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long

using namespace std;

typedef unsigned long long ull;
const int N=55;
int n;
int m[N];
ull f[N][2][2];

signed main()
{
    cin >> n;
    int msk=0;
    for (int i=1;i<=n;i++)
    {
        cin >> m[i];
        msk^=m[i];
    }
    ull ans=0;
    if (!msk) ans++;
    for (int k=31;~k;k--)
    {
        if ((msk>>(k+1))&1) break;
        int bit=(1ll<<k)-1;
        memset(f,0,sizeof(f));
        f[0][0][0]=1;
        for (int i=1;i<=n;i++)
        {
            int cur=(m[i]>>k)&1;
            if (cur)
            {
                for (int x=0;x<2;x++) 
                {
                    f[i][x][1]+=f[i-1][x][0];
                    f[i][x][1]+=f[i-1][x][1]*(1ll<<k);
                }
            }
            for (int x=0;x<2;x++) 
            {
                for (int y=0;y<2;y++)
                {
                    ull cof=(m[i]&bit)+1;
                    f[i][x][y]+=f[i-1][x^cur][y]*cof;
                }
            }
        }
        ans+=f[n][0][1];
    }
    cout << ans-1 << "\n";

    return 0; 
}

:::