Submission #467900

#	Time	Username	Problem	Language	Result	Execution time	Memory
467900		ivan_tudor	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	2879 ms	1820 KiB

amusementpark

#include<bits/stdc++.h>
using namespace std;
const int N = 18;
bool canb[1<<N];
int dp[1<<N];
vector<int> gr[N];
const int MOD =998244353;
void add(int &x, long long y){
  y%=MOD;
  x+=y;
  if(x >= MOD)
    x-=MOD;
  if(x < 0)
    x+=MOD;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, m;
  cin>>n>>m;
  for(int i = 1; i <= m; i++){
    int x, y;
    cin>>x>>y;
    x--;
    y--;
    gr[x].push_back(y);
    gr[y].push_back(x);
  }
  canb[0] = true;
  for(int mask = 0; mask < (1<<n); mask++){
    if(canb[mask] == false)
      continue;

    for(int i = 0; i < n; i++){
      bool ok = true;
      if((mask & (1<<i)) == 0){
        for(auto x:gr[i]){
          if(mask & (1<<x)){
            ok = false;
            break;
          }
        }
        canb[mask ^(1<<i)] = ok;
      }
    }
  }
  dp[0] = 1;
  for(int mask = 0; mask < (1<<n); mask ++){
    for(int layer = mask; layer > 0; layer = (layer - 1) & mask){
      if(canb[layer]){
        if(__builtin_popcount(layer)%2 == 1)
          add(dp[mask], dp[mask ^ layer]);
        else
          add(dp[mask], -dp[mask ^ layer]);
      }
    }
  }
  cout<<(1LL * dp[(1<<n) - 1] *((MOD + 1) / 2) % MOD * m) % MOD;
  return 0;
}

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