oj.uz

Submission #363923

# Submission time Handle Problem Language Result Execution time Memory
363923 2021-02-07T14:16:47 Z 2qbingxuan Asceticism (JOI18_asceticism) C++14
24 / 100
 600 ms 6380 KB 
//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\Q
//   \###################\Q
//    \        ____       \B
//     \_______\___\_______\X
// An AC a day keeps the doctor away.
 
#ifdef local
// #define _GLIBCXX_DEBUG AC
#include <bits/extc++.h>
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
#define TAK(args...) std::ostream& operator<<(std::ostream &O, args)
#define NIE(STL, BEG, END, OUT) template <typename ...T> TAK(std::STL<T...> v) \
    { O << BEG; int f=0; for(auto e: v) O << (f++ ? ", " : "") << OUT; return O << END; }
NIE(deque, "[", "]", e) ; NIE(vector, "[", "]", e)
NIE(set, "{", "}", e) ; NIE(multiset, "{", "}", e) ; NIE(unordered_set, "{", "}", e)
NIE(map , "{", "}", e.first << ":" << e.second)
NIE(unordered_map , "{", "}", e.first << ":" << e.second)
template <typename ...T> TAK(std::pair<T...> p) { return O << '(' << p.first << ',' << p.second << ')'; }
template <typename T, size_t N> TAK(std::array<T,N> a) { return O << std::vector<T>(a.begin(), a.end()); }
template <typename ...T> TAK(std::tuple<T...> t) {
    return O << "(", std::apply([&O](T ...s){ int f=0; (..., (O << (f++ ? ", " : "") << s)); }, t), O << ")";
}
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    if(!cnt) return std::cerr << "\033[1;32m() = ()\033\[0m\n", void();
    (std::cerr << "\033[1;32m(" << s << ") = (" , ... , (std::cerr << args << (--cnt ? ", " : ")\033[0m\n")));
}
#else
#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#include <bits/stdc++.h>
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back
#define all(v) begin(v),end(v)
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
 
template <typename T, T MOD> class Modular {
public:
    constexpr Modular() : v() {}
    template <typename U> Modular(const U &u) { v = (0 <= u && u < MOD ? u : (u%MOD+MOD)%MOD); }
    template <typename U> explicit operator U() const { return U(v); }
    T operator()() const { return v; }
#define REFOP(type, expr...) Modular &operator type (const Modular &rhs) { return expr, *this; }
    REFOP(+=, v += rhs.v - MOD, v += MOD & (v >> width)) ; REFOP(-=, v -= rhs.v, v += MOD & (v >> width))
    // fits for MOD^2 <= 9e18
    REFOP(*=, v = 1LL * v * rhs.v % MOD) ; REFOP(/=, *this *= inverse(rhs.v))
#define VALOP(op) friend Modular operator op (Modular a, const Modular &b) { return a op##= b; }
    VALOP(+) ; VALOP(-) ; VALOP(*) ; VALOP(/)
    Modular operator-() const { return 0 - *this; }
    friend bool operator == (const Modular &lhs, const Modular &rhs) { return lhs.v == rhs.v; }
    friend bool operator != (const Modular &lhs, const Modular &rhs) { return lhs.v != rhs.v; }
    friend std::istream & operator>>(std::istream &I, Modular &m) { T x; I >> x, m = x; return I; }
    friend std::ostream & operator<<(std::ostream &O, const Modular &m) { return O << m.v; }
private:
    constexpr static int width = sizeof(T) * 8 - 1;
    T v;
    static T inverse(T a) {
        // copy from tourist's template
        T u = 0, v = 1, m = MOD;
        while (a != 0) {
            T t = m / a;
            m -= t * a; std::swap(a, m);
            u -= t * v; std::swap(u, v);
        }
        assert(m == 1);
        return u;
    }
};

using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T> using max_heap = std::priority_queue<T,vector<T>,less<T> >;
template <typename T> using min_heap = std::priority_queue<T,vector<T>,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template <typename V, typename T> int get_pos(const V &v, T x) { return lower_bound(all(v),x) - begin(v); }
template <typename V> void sort_uni(V &v) { sort(all(v)), v.erase(unique(all(v)),end(v)); }
template <typename T> bool chmin(T &x, const T &v) { return v < x ? (x=v, true) : false; }
template <typename T> bool chmax(T &x, const T &v) { return x < v ? (x=v, true) : false; }
constexpr inline ll cdiv(ll x, ll m) { return x/m + (x%m ? (x<0) ^ (m>0) : 0); } // ceiling divide
constexpr inline ll modpow(ll e,ll p,ll m) { ll r=1; for(e%=m;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r; }

constexpr ld PI = acos(-1), eps = 1e-7;
constexpr ll N = 500025, INF = 1e18, MOD = 1000000007, K = 14699, inf = 1e9;
using Mint = Modular<int, MOD>;
Mint modpow(Mint e, uint64_t p) { Mint r = 1; while(p) (p&1) && (r *= e), e *= e, p >>= 1; return r; } // 0^0 = 1

Mint fac[N], inv[N], ifac[N];
Mint C(int n, int k) {
    return fac[n] * ifac[k] * ifac[n-k];
}
signed main() {
    inv[1] = fac[0] = ifac[0] = 1;
    for (int i = 2; i < N; i++) inv[i] = -inv[MOD % i] * (MOD / i);
    for (int i = 1; i < N; i++) fac[i] = fac[i-1] * i, ifac[i] = ifac[i-1] * inv[i];
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, k;
    cin >> n >> k;

    vector<Mint> dp[2];
    dp[0].resize(n+1);
    dp[1].resize(n+1);
    dp[0][0] = 1;
    vector<Mint> way(k+1);
    Mint ans = 0;
    for (int t = 1; t <= k; t++) {
        for (int i = 0; i <= n; i++) dp[t & 1][i] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[t & 1][i] += dp[~t & 1][j] * C(i, j);
            }
        }
        ans += dp[t & 1][n] * C(n-t, n-k) * (k-t & 1 ? -1 : 1);
        // cout << dp[t & 1] << '\n';
    }
    cout << ans << '\n';
}

Compilation message

asceticism.cpp:39: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
   39 | #pragma loop_opt(on)
      | 
asceticism.cpp: In function 'int main()':
asceticism.cpp:130:47: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  130 |         ans += dp[t & 1][n] * C(n-t, n-k) * (k-t & 1 ? -1 : 1);
      |                                              ~^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6252 KB Output is correct
2 Correct 11 ms 6252 KB Output is correct
3 Correct 11 ms 6252 KB Output is correct
4 Correct 11 ms 6252 KB Output is correct
5 Correct 11 ms 6252 KB Output is correct
6 Correct 13 ms 6252 KB Output is correct
7 Correct 12 ms 6252 KB Output is correct
8 Correct 11 ms 6252 KB Output is correct
9 Correct 10 ms 6252 KB Output is correct
10 Correct 11 ms 6252 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6252 KB Output is correct
2 Correct 11 ms 6252 KB Output is correct
3 Correct 11 ms 6252 KB Output is correct
4 Correct 11 ms 6252 KB Output is correct
5 Correct 11 ms 6252 KB Output is correct
6 Correct 13 ms 6252 KB Output is correct
7 Correct 12 ms 6252 KB Output is correct
8 Correct 11 ms 6252 KB Output is correct
9 Correct 10 ms 6252 KB Output is correct
10 Correct 11 ms 6252 KB Output is correct
11 Correct 13 ms 6252 KB Output is correct
12 Correct 11 ms 6252 KB Output is correct
13 Correct 12 ms 6124 KB Output is correct
14 Correct 58 ms 6252 KB Output is correct
15 Correct 133 ms 6380 KB Output is correct
16 Correct 132 ms 6380 KB Output is correct
17 Correct 15 ms 6252 KB Output is correct
18 Correct 52 ms 6252 KB Output is correct
19 Correct 20 ms 6272 KB Output is correct
20 Correct 10 ms 6252 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6252 KB Output is correct
2 Correct 11 ms 6252 KB Output is correct
3 Correct 11 ms 6252 KB Output is correct
4 Correct 11 ms 6252 KB Output is correct
5 Correct 11 ms 6252 KB Output is correct
6 Correct 13 ms 6252 KB Output is correct
7 Correct 12 ms 6252 KB Output is correct
8 Correct 11 ms 6252 KB Output is correct
9 Correct 10 ms 6252 KB Output is correct
10 Correct 11 ms 6252 KB Output is correct
11 Correct 13 ms 6252 KB Output is correct
12 Correct 11 ms 6252 KB Output is correct
13 Correct 12 ms 6124 KB Output is correct
14 Correct 58 ms 6252 KB Output is correct
15 Correct 133 ms 6380 KB Output is correct
16 Correct 132 ms 6380 KB Output is correct
17 Correct 15 ms 6252 KB Output is correct
18 Correct 52 ms 6252 KB Output is correct
19 Correct 20 ms 6272 KB Output is correct
20 Correct 10 ms 6252 KB Output is correct
21 Correct 15 ms 6252 KB Output is correct
22 Correct 22 ms 6252 KB Output is correct
23 Execution timed out 1085 ms 6252 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6252 KB Output is correct
2 Correct 11 ms 6252 KB Output is correct
3 Correct 11 ms 6252 KB Output is correct
4 Correct 11 ms 6252 KB Output is correct
5 Correct 11 ms 6252 KB Output is correct
6 Correct 13 ms 6252 KB Output is correct
7 Correct 12 ms 6252 KB Output is correct
8 Correct 11 ms 6252 KB Output is correct
9 Correct 10 ms 6252 KB Output is correct
10 Correct 11 ms 6252 KB Output is correct
11 Correct 13 ms 6252 KB Output is correct
12 Correct 11 ms 6252 KB Output is correct
13 Correct 12 ms 6124 KB Output is correct
14 Correct 58 ms 6252 KB Output is correct
15 Correct 133 ms 6380 KB Output is correct
16 Correct 132 ms 6380 KB Output is correct
17 Correct 15 ms 6252 KB Output is correct
18 Correct 52 ms 6252 KB Output is correct
19 Correct 20 ms 6272 KB Output is correct
20 Correct 10 ms 6252 KB Output is correct
21 Correct 15 ms 6252 KB Output is correct
22 Correct 22 ms 6252 KB Output is correct
23 Execution timed out 1085 ms 6252 KB Time limit exceeded
24 Halted 0 ms 0 KB -