Submission #1124742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124742		Zero_OP	NoM (RMI21_nom)	C++17	100 / 100	50 ms	396 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

const int mod = 1e9 + 7;

int N, M;

namespace subtask1{
    bool check(){
        return N <= 5 && M <= 5;
    }

    void solve(){
        vector<int> perm(2 * N);
        iota(all(perm), 0);

        int ans = 0;
        do{
            vector<int> lst(N, -1);
            bool ok = true;
            for(int i = 0; i < 2 * N; ++i){
                int x = perm[i] % N;
                if(lst[x] == -1) lst[x] = i;
                else if(abs(lst[x] - i) % M == 0){
                    ok = false;
                    break;
                }
            }
            ans += ok;
        } while(next_permutation(all(perm)));
        cout << ans << '\n';
    }
}

struct mint{
    int v;
    mint() : v(0) {}
    mint(int v) : v(v) {}

    mint& operator += (const mint& o){ v += o.v; if(v >= mod) v -= mod; return *this; }
    mint& operator -= (const mint& o){ v -= o.v; if(v < 0) v += mod; return *this; }
    mint& operator *= (const mint& o){ v = 1LL * v * o.v % mod; return *this; }

    mint power(ll n) const{
        mint res(1), base = *this;
        for(; n > 0; n >>= 1, base *= base){
            if(n & 1) res *= base;
        }
        return res;
    }

    mint inv() const{
        return power(mod - 2);
    }

    mint& operator /= (const mint& o){ return *this *= o.inv(); }

    friend mint operator + (mint a, const mint& b){ return a += b; }
    friend mint operator - (mint a, const mint& b){ return a -= b; }
    friend mint operator * (mint a, const mint& b){ return a *= b; }
    friend mint operator / (mint a, const mint& b){ return a /= b; }

    friend bool operator == (const mint& a, const mint& b){
        return a.v == b.v;
    }

    friend bool operator != (const mint& a, const mint& b){
        return a.v != b.v;
    }

    friend ostream& operator << (ostream& out, const mint& v){ return out << v.v; }
};

namespace subtask5{
    mint fact[4002], ifact[4002];

    void prepare(int n){
        fact[0] = ifact[0] = 1;
        for(int i = 1; i <= n; ++i){
            fact[i] = fact[i - 1] * mint(i);
        }

        ifact[n] = fact[n].inv();
        for(int i = n; i > 1; --i){
            ifact[i - 1] = ifact[i] * i;
        }
    }

    mint C(int n, int k){
        if(n < k || k < 0) return 0;
        return fact[n] * ifact[n - k] * ifact[k];
    }

    mint P(int n, int k){
        if(n < k || k < 0) return 0;
        return fact[n] * ifact[n - k];
    }

    int n[2005];

    void solve(){
        prepare(2 * N);

        for(int i = 0; i < 2 * N; ++i){
            ++n[i % M];
        }

//        for(int i = 0; i < M; ++i)
//            cout << n[i] << ' ';
//        }
//        cout << '\n';

        vector<mint> f(N + 1), g(N + 1);
        f[0] = 1;

        int sum = n[0];
        for(int i = 1; i < M; ++i){
            for(int j = 0; j <= n[i]; ++j){
                for(int k = 0; k + j <= N && sum - 2 * k >= j; ++k){
                    g[k + j] += f[k] * P(sum - 2 * k, j) * C(n[i], j);
                }
            }

            sum += n[i];
            for(int j = 0; j <= N; ++j){
                f[j] = g[j];
                g[j] = 0;
            }
        }

        mint ans = f[N] * fact[N];
        for(int i = 0; i < N; ++i) ans *= 2;
        cout << ans << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    file("A");

    cin >> N >> M;

    subtask5::solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:10:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:173:5: note: in expansion of macro 'file'
  173 |     file("A");
      |     ^~~~
Main.cpp:10:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:173:5: note: in expansion of macro 'file'
  173 |     file("A");
      |     ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48