Submission #1110038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110038		koukirocks	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2325 ms	2384 KiB

amusementpark

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

int main() {
    speed;
    int n,m;
    cin>>n>>m;
    vvector<bool> G(n+1,vector<bool>(n+1));
    for (int i=0;i<m;i++) {
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a][b]=true;
        G[b][a]=true;
    }
    vector<ll> dp((1<<n));
    vector<bool> pos((1<<n));
    for (int st=1;st<(1<<n);st++) {
        pos[st]=true;
        for (int a=0;a<n;a++) {
            for (int b=a+1;b<n;b++) {
                if (st&(1<<a) and st&(1<<b)) pos[st]=pos[st]&(!G[a][b]);
            }
        }
    }
    dp[0]=1;
    for (int st=1;st<(1<<n);st++) {
        dp[st]=0;
        for (int mask=st;;mask=(mask-1)&st) {
            if (mask==0) break;
            if (!pos[mask]) continue;
            dp[st]+=(__builtin_popcount(mask)&1?1:P-1)*dp[st^mask];
            dp[st]%=P;
        }
        // cout<<st<<" "<<dp[st]<<" st dp\n";
    }
    cout<<dp[(1<<n)-1]*m%P*((P+1)/2)%P<<"\n";
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37