Submission #54166489

---

Source Code Expand

//
// Created by Barichek on 14.03.2024 22:06:28
//

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 10, inf = 1000111222;

/*
 * long long version

long long mul(long long a, long long b) {
    long long x = (long double) a * b / mod;
    long long y = (a * b - x * mod) % mod;
    return y < 0 ? y + mod : y;
}

long long power(long long a, long long b) {
    if (b == 0) {
        return 1 % mod;
    }
    if (b % 2 == 0) {
        return power(mul(a, a), b / 2);
    }
    return mul(a, power(a, b - 1));
}*/

const int mod = 998244353;

inline void inc(int &x, int y) {
    x += y;
    if (x >= mod) {
        x -= mod;
    }
}

inline void dec(int &x, int y) {
    x -= y;
    if (x < 0) {
        x += mod;
    }
}

inline int neg(int x) {
    return x ? (mod - x) : 0;
}

inline int mul(int x) {
    return x;
}

template<typename... Args>
inline int mul(int x, Args... args) {
    return (1LL * x * mul(args...)) % mod;
}

int power(int a, long long b) {
    int res = 1 % mod;
    while (b) {
        if (b % 2) {
            res = mul(res, a);
        }
        b /= 2;
        a = mul(a, a);
    }
    return res;
}

int inv(int x) {
    return power(x, mod - 2);
}

string str_fraction(int x, int n = 20) {
    stringstream res;
    pair<int, int> best(x, 1);
    for (int j = 1; j < n; ++j) {
        best = min(best, {mul(x, j), j});
        best = min(best, {mod - mul(x, j), -j});
    }
    if (best.second < 0) {
        best.first *= -1;
        best.second *= -1;
    }
    res << best.first << "/" << best.second;
    return res.str();
}

inline bool get_bit(int mask,int bit)
{
    return (mask>>bit)&1;
}

int x[max_n];

int dp[2][1ll<<max_n];

int fixes_this_element[max_n];

void solve()
{
    int m,n;
    cin>>m>>n;
    for (int i=0;i<m;i++){
        cin>>x[i];
        x[i]--;
    }
    memset(fixes_this_element,0,sizeof(fixes_this_element));
    for (int i=0;i<m;i++){
        fixes_this_element[x[i]]|=(1ll<<i);
    }
    for (int i=0;i<m;i++){
        LOG(i,bitset<10>(fixes_this_element[i]));
    }
    int q1=0,q2=1;
    memset(dp,0,sizeof(dp));
    dp[q1][(1ll<<m)-1]=1;
    for (int i=1;i<=n;i++){
        memset(dp[q2],0,sizeof(dp[q2]));

        {
            for (int mask=0;mask<(1ll<<m);mask++){
                for (int cur=0;cur<m;cur++){
                    if (!get_bit(mask,cur) && x[cur]!=cur){
                        continue;
                    }
                    const int new_mask=mask&(~(1ll<<cur))|(fixes_this_element[cur]);
                    if (dp[q1][mask]){
                        LOG(i,cur,bitset<10>(mask),bitset<10>(new_mask),dp[q1][mask]);
                    }
                    inc(dp[q2][new_mask],dp[q1][mask]);
                }
            }
        }

        swap(q1,q2);
    }
    int ans=0;
    for (int mask=0;mask<(1ll<<m);mask++){
        inc(ans,dp[q1][mask]);
    }
    cout<<ans<<"\n";
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tests=1;
//    cin>>tests;
    while (tests--){
        solve();
    }

    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:156:44: warning: suggest parentheses around arithmetic in operand of ‘|’ [-Wparentheses]
  156 |                     const int new_mask=mask&(~(1ll<<cur))|(fixes_this_element[cur]);
      |                                        ~~~~^~~~~~~~~~~~~~

Judge Result