C++11(clang++ 3.9) 解法, 执行用时: 980ms, 内存消耗: 10096K, 提交时间: 2018-08-24 16:39:10

#include<bits/stdc++.h>

const int N = 14;
const int M = 1000010;
const int moder = 998244353;
typedef long long ll;

int inv[M];

void init(){
    inv[1] = 1;
    for (int i = 2; i < M; ++ i){
        inv[i] = (moder - 1ll * (moder / i) * inv[moder % i] % moder) % moder;
    }
}

int powermod(int a, int exp){
    int ret = 1;
    for ( ; exp > 0; exp >>= 1){
        if (exp & 1){
            ret = 1ll * ret * a % moder;
        }
        a = 1ll * a * a % moder;
    }
    return ret;
}

struct poly{
    int a[N];

    poly(){memset(a, 0, sizeof(a));}

    int &operator [](const int &n){
        return a[n];
    }

    poly operator +(const poly &p)const{
        poly ret;
        for (int i = 0; i < N; ++ i){
            ret.a[i] = a[i] + p.a[i];
            ret.a[i] -= ret.a[i] >= moder ? moder : 0;
        }
        return ret;
    }

    poly operator -(const poly &p)const{
        poly ret;
        for (int i = 0; i < N; ++ i){
            ret.a[i] = a[i] - p.a[i];
            ret.a[i] += ret.a[i] < 0 ? moder : 0;
        }
        return ret;
    }

    poly operator *(const poly &p)const{
        poly ret;
        for (int i = 0; i < N; ++ i){
            for (int j = 0; i + j < N; ++ j){
                ret.a[i + j] = (ret.a[i + j] + 1ll * a[i] * p.a[j]) % moder;
            }
        }
        return ret;
    }

    poly operator *(const int &p)const{
        poly ret;
        for (int i = 0; i < N; ++ i){
            ret.a[i] = 1ll * a[i] * p % moder;
        }
        return ret;
    }
};

void FMT(poly *f, int len, int type){
    for (int j = 0; j < len; ++ j){
        for (int i = 0; i < 1 << len; ++ i){
            if (i >> j & 1){
                if (type == 0){
                    f[i] = f[i] + f[i ^ 1 << j];
                }
                else{
                    f[i] = f[i] - f[i ^ 1 << j];
                }
            }
        }
    }
}

ll a[N];
bool mat[N][N];
poly p[1 << N], q[1 << N];
int ways[1 << N];
ll min[1 << N];
std::vector <int> vec[1 << N];
int coef[1 << N];

int solve(std::vector <ll> vec, ll c){
    std::sort(vec.begin(), vec.end());
    if (vec.back() == 0){
        return c == 0;
    }
    int maxv = 63 - __builtin_clzll(vec.back());
    int maxc = c ? 63 - __builtin_clzll(c) : -1;
    if (maxv < maxc){
        return 0;
    }
    int dp[2] = {1, 0};
    for (int i = 0, sz = vec.size(); i < sz - 1; ++ i){
        int small = std::min(vec[i] + 1, 1ll << maxv) % moder;
        int big = std::max(0ll, vec[i] - (1ll << maxv) + 1) % moder;
        int tmp0 = (1ll * dp[0] * small + 1ll * dp[1] * big) % moder;
        int tmp1 = (1ll * dp[1] * small + 1ll * dp[0] * big) % moder;
        dp[0] = tmp0, dp[1] = tmp1;
    }
    int ret = dp[maxv == maxc];
    *(vec.rbegin()) ^= 1ll << maxv;
    c ^= 1ll << maxv;
    ret += solve(vec, c);
    ret -= ret >= moder ? moder : 0;
    return ret;
}

int ans = 0;

void dfs(int set, int coe, int chosen){
    if (!set){
        ans = (ans + 1ll * coe * ways[chosen]) % moder;
        return;
    }
    for (auto u : vec[set]){
        int ncoe = 1ll * coe * coef[u] % moder;
        int nchosen = chosen;
        if (__builtin_parity(u)){
            nchosen ^= 1 << min[u];
        }
        else{
            ncoe = 1ll * ncoe * (a[min[u]] % moder + 1) % moder;
        }
        dfs(set ^ u, ncoe, nchosen);
    }
}

int main(){
    init();
    int n, m;
    ll c;
    scanf("%d%d%lld", &n, &m, &c);
    for (int i = 0; i < n; ++ i){
        scanf("%lld", &a[i]);
    }
    for (int i = 0, u, v; i < m; ++ i){
        scanf("%d%d", &u, &v);
        -- u, -- v;
        mat[u][v] = mat[v][u] = true;
    }
    memset(min, -1, sizeof(min));
    for (int i = 0; i < 1 << n; ++ i){
        std::vector <int> vec;
        std::vector <ll> vec1;
        for (int j = 0; j < n; ++ j){
            if (i >> j & 1){
                vec.push_back(j);
                vec1.push_back(a[j]);
                if (min[i] == -1 || a[min[i]] > a[j]){
                    min[i] = j;
                }
            }
        }
        bool flag = true;
        for (int j = 0, sz = vec.size(); j < sz; ++ j){
            for (int k = j + 1; k < sz; ++ k){
                if (mat[vec[j]][vec[k]]){
                    flag = false;
                }
            }
        }
        p[i][vec.size()] = flag;
        if (i){
            ways[i] = solve(vec1, c);
        }
    }
    FMT(p, n, 0);
    for (int i = 0; i < 1 << n; ++ i){
        p[i][0] = 0;
        poly now = p[i], tmp = p[i];
        for (int j = 1; j <= n; ++ j){
            q[i] = q[i] + now * (j & 1 ? inv[j] : (moder - inv[j]));
            now = now * tmp;
        }
    }
    FMT(q, n, 1);
    for (int i = 0; i < 1 << n; ++ i){
        coef[i] = q[i][__builtin_popcount(i)];
    }
    for (int i = 1; i < 1 << n; ++ i){
        for (int j = 1; j <= i; ++ j){
            if ((i & j) != j) continue;
            for (int k = 0; k < n; ++ k){
                if ((i >> k & 1) || (j >> k & 1)){
                    if ((i & j) >> k & 1){
                        vec[i].push_back(j);
                    }
                    break;
                }
            }
        }
    }
    dfs((1 << n) - 1, 1, 0);
    printf("%d\n", ans);
    return 0;
}