ub求助
查看原帖
ub求助
324412
Filberte楼主2023/11/23 15:32

本地跑至少能过样例,但是交上去所有数据都RE(包括样例)

#include <bits/stdc++.h>
using namespace std;
const int maxn = (1 << 17) + 100;
const int mod = 998244353;
int f[maxn], cnt[maxn];
void add(int &x, int y){x = (x + y) % mod;}
void sub(int &x, int y){x = (x - y + mod) % mod;}
int mul(int x, int y){return 1LL * x * y % mod;}
int n, m;
int e[20][20];
int ans[20];
int fac[200];
int high_bit(int x){return 31-__builtin_clz(x);}
int low_bit(int x){return __builtin_ctz(x);}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1, u, v;i <= m;i++){
        scanf("%d%d",&u,&v);
        u--, v--;
        e[u][v] = e[v][u] = 1;
    }
    int S = (1 << n) - 1;
    for(int s = 0;s <= S;s++){
        int u = high_bit(s);
        cnt[s] = cnt[s ^ (1 << u)];
        for(int v = u - 1;v >= 0;v--) 
            if(((s >> v) & 1) && e[u][v]) cnt[s]++;
    }
    // cout << "cnt:\n";
    // for(int s = 0;s <= S;s++) cout << cnt[s] << " ";
    // cout << "\n";
    fac[0] = 1;for(int i = 1;i <= m;i++) fac[i] = (fac[i - 1] * 2) % mod;
    for(int s = 1;s <= S;s++){
        f[s] = fac[cnt[s]];
        int sum = 0, nes = low_bit(s);
        for(int t = (s - 1) & s;t;t = (t - 1) & s) if((t >> nes) & 1){
            add(sum, mul(f[t], fac[cnt[s ^ t]]));
        }
        sub(f[s], sum);
    }
    // cout << "f:\n";
    // for(int s = 0;s <= S;s++) cout << f[s] << " ";
    // cout << "\n";
    for(int s = 1;s <= S;s += 2){
        int x = mul(f[s], fac[cnt[S ^ s]]);
        for(int i = 1;i < n;i++) 
            if((s >> i) & 1){
                add(ans[i], x);
            }
    }
    for(int i = 1;i < n;i++) printf("%d\n",ans[i]);
    return 0;
}
2023/11/23 15:32
加载中...