P10104 题解

· · 题解

P10104 题解

Problem Link

题目大意

给定 a_1\sim a_n,C，以及一张 n 个点 m 条边的无向图 G，求有多少 b_1\sim b_n 满足：

  • \forall i\in[1,n]$，满足 $b_i\in[0,a_i]

数据范围：n\le 15。

思路分析

先考虑 m=0 的情况，容易发现我们只要找到第一个存在一个自由元的位 d，那么 <d 的位都可以随便填。

枚举 d，然后 dp 求出当前这一位有至少一个自由元，且异或和满足条件的方案数。

时间复杂度 \mathcal O(n\log V)。

那么最朴素的想法就是 \mathcal O(2^m) 枚举一些边相等，那么我们只保留每个奇数大小的连通块里最小的 a_i。

很显然我们只关心最终的连通块划分情况，因此可以 \mathcal O(3^n) 预处理出 f_S 表示点集为 S 时每个连通块的容斥系数 (-1)^{|E|} 之和。

可以直接状压哪些点被选，哪些点是关键点，暴力 dp 时间复杂度 \mathcal O(4^n)。

考虑进一步压缩状态，我们按 a_i 排序，每次取出 a_u 最小的未被加入的 u，然后枚举 u 所在的连通块，此时 <a_u 的全部被加入，只要维护他们是不是关键点，同理 >a_u 的全部不是关键点，只要维护他们是否被选入连通块。

那么状态数为 \mathcal O(2^n)，转移复杂度为 \mathcal O(n3^n)。

时间复杂度 \mathcal O((m+n\log V)2^n+n3^n)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353;
void add(ll &x,ll y) { x=(x+y)%MOD; }
ll calc(vector<ll>a) {
    ll ans=0;
    for(int d=60;~d;--d) {
        ll hi=0;
        for(ll i:a) hi^=i>>(d+1);
        if(hi) break;
        array<array<ll,2>,2> f{1,0,0,0},g{0,0,0,0}; //xor free
        for(ll i:a) {
            g={0,0,0,0};
            for(int x:{0,1}) for(int y:{0,1}) if(f[x][y]) {
                ll lo=((i&((1ll<<d)-1))+1)%MOD;
                if(~(i>>d)&1) add(g[x][y],f[x][y]*lo);
                else {
                    if(y) add(g[x][1],(1ll<<d)%MOD*f[x][y]);
                    else add(g[x][1],f[x][y]);
                    add(g[x^1][y],f[x][y]*lo);
                }
            }
            f=g;
        }
        add(ans,f[0][1]);
    }
    ll hi=0;
    for(ll i:a) hi^=i;
    if(!hi) ++ans;
    return ans;
}
int n,m,ord[15],id[15],ec[1<<15];
ll C,a[15],cf[1<<15],cg[1<<15],dp[1<<15],tmp[1<<15];
ll solve(vector<ll>vi) {
    if(!C) return calc(vi);
    vi.push_back(C);
    ll ans=calc(vi);
    --vi.back();
    return (ans+MOD-calc(vi))%MOD;
}
signed main() {
    scanf("%d%d%lld",&n,&m,&C);
    for(int i=0;i<n;++i) scanf("%lld",&a[i]);
    iota(ord,ord+n,0),sort(ord,ord+n,[&](int x,int y){ return a[x]<a[y]; }),sort(a,a+n);
    for(int i=0;i<n;++i) id[ord[i]]=i;
    for(int i=0,u,v;i<m;++i) {
        scanf("%d%d",&u,&v),u=id[u-1],v=id[v-1];
        ll x=(1<<u)|(1<<v);
        for(int s=0;s<(1<<n);++s) if((s&x)==x) ++ec[s];
    }
    for(int s=0;s<(1<<n);++s) cg[s]=!ec[s];
    for(int s=0;s<(1<<n);++s) {
        cf[s]=cg[s];
        int lb=s&-s;
        for(int t=(s-1)&s;t;t=(t-1)&s) if(t&lb) {
            cf[s]=(cf[s]+MOD-cf[t]*cg[s^t])%MOD;
        }
    }
    dp[0]=1;
    for(int i=0;i<n;++i) {
        //<i: is key?, >=i in queue?
        memset(tmp,0,sizeof(tmp));
        for(int s=0;s<(1<<n);++s) if(dp[s]) {
            if(s&(1<<i)) { add(tmp[s^(1<<i)],dp[s]); continue; }
            int rem=(s^((1<<n)-1))&(~((1<<(i+1))-1));
            for(int t=rem;;t=(t-1)&rem) {
                int u=t|(1<<i);
                if(__builtin_popcount(u)&1) add(tmp[s|u],dp[s]*cf[u]);
                else add(tmp[s|t],(a[i]+1)%MOD*dp[s]%MOD*cf[u]);
                if(!t) break;
            }
        }
        swap(tmp,dp);
    }
    ll ans=0;
    for(int s=0;s<(1<<n);++s) {
        vector <ll> vi;
        for(int i=0;i<n;++i) if(s&(1<<i)) vi.push_back(a[i]);
        add(ans,dp[s]*solve(vi));
    }
    printf("%lld\n",ans);
    return 0;
}