【luoguP4221】[WC2018]州区划分

这个题目比较考察科技啊。

首先让我们考虑最暴力的状态方程,设dp_{s}表示目前所有已经被选择的城市集合为s,这样的满意度之和。那么方程为
dp_{s}=\frac{1}{sum_s}\sum_{T\in s}dp_{T}sum_{s-T}

之所以乘\sum_{s-T}是为了抵消原来的分母的影响。这里默认sum都是p次方之后的。

那么现在这个东西首先可以枚举子集来做,复杂度O(3^n),t到不知道哪里去了,接下来怎么办?

注意到后面这个式子,实际上他相当于满足T \; and \; (s-T) = 0,T \; or \; (s-T) = s

那么这个东西就相当Ts-T二进制上的1加起来正好等于s上的1个数,且T \; xor \; (s-T) = s这么一个情况,那么我们多加一维限制,分层fwt。

注意sum就不要逆变换回去了,并且dp值除了最后都要保证一直fwt,正变换之后和fft结果类似,可以O(n)乘起来,还要注意fwt不要带乘法,能换成加减就别用乘法和取模,这破题卡常

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 23;

const int mo = 998244353, inv2 = 499122177;

int lx, fa[ms], ly, n, m, p, de[ms];

int w[ms], su[3000030], dp[ms][3000030], vx[ms][3000030];

struct edge
{
    int x, y;
}e[1010];

inline int ksm(lo x, lo k)
{
    lo rt = 1, a = x;
    while(k)
        rt = rt * ((k & 1) ? a : 1) % mo, a = a * a % mo, k >>= 1;
    return (int)rt;
}

inline int ask(int x)
{
    int rt = 0;
    while(x)
        x -= (x & (-x)), rt ++;
    return rt;
}

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline bool check(int s)
{
    for(ri i = 1; i <= n; i ++)
        fa[i] = i, de[i] = 0;
    int cnt = ask(s), fx, fy;
    for(ri i = 1; i <= m; i ++)
        if(((1 << (e[i].x - 1) & s)) && (((1 << (e[i].y - 1)) & s)))
        {
            de[e[i].x] ++, de[e[i].y] ++, fx = find(e[i].x), fy = find(e[i].y);
            if(fx != fy)
                fa[fx] = fy, cnt --;
        }
    if(cnt > 1)
        return 1;
    for(ri i = 1; i <= n; i ++)
        if(((1 << (i - 1)) & s) && (de[i] & 1))
            return 1;
    return 0;
}

inline int add(int x, int y)
{
    x += y, x -= (x >= mo) ? mo : 0;
    return x;
}

inline void fwt(int *a, int len, int tp)
{
    /*int la, lb;
    for(ri i = 1; i < len; i <<= 1)
        for(ri j = 0; j < len; j += (i << 1))
            for(ri k = j; k < j + i; k ++)
            {
                la = a[k], lb = a[k + i];
                a[k] = add(la, lb), a[k + i] = add(la, mo - lb);
                if(tp == -1)
                    a[k] = 1ll * a[k] * inv2 % mo, a[k + i] = 1ll * a[k + i] * inv2 % mo;
            }*/
    for(ri i = 1; i < len; i <<= 1)
        for(ri j = 0; j < len; j += (i << 1))
            for(ri k = 0; k < i; k ++)
                a[j + k + i] = add(a[j + k + i], (tp == -1 ? mo - a[j + k] : a[j + k]));
}

int main()
{
    re(n), re(m), re(p);
    for(ri i = 1; i <= m; i ++)
        re(lx), re(ly), e[i] = (edge){lx, ly};
    for(ri i = 1; i <= n; i ++)
        re(w[i]);
    int S = 1 << n;
    for(ri s = 0; s < S; s ++)
    {
        int cnt = 0;
        for(ri i = 0; i < n; i ++)
            if((1 << i) & s)
                cnt ++, su[s] += w[i + 1];
        su[s] = ksm(su[s], p), vx[cnt][s] = check(s) ? su[s] : 0;
    }
    dp[0][0] = 1, fwt(dp[0], S, 1);
    for(ri i = 1; i <= n; i ++)
    {
        fwt(vx[i], S, 1);
        for(ri j = 0; j < i; j ++)
            for(ri s = 0; s < S; s ++)
                dp[i][s] = (dp[i][s] + 1ll * dp[j][s] * vx[i - j][s] % mo) % mo;
        fwt(dp[i], S, -1);
        for(ri s = 0; s < S; s ++)
            dp[i][s] = (ask(s) != i) ? 0 : 1ll * dp[i][s] * ksm(su[s], mo - 2) % mo;
        if(i != n)
            fwt(dp[i], S, 1);
    }
    printf("%d", dp[n][S - 1]);
    system("pause");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注