結果

問題 No.616 へんなソート
ユーザー warabi0906
提出日時 2023-03-03 12:57:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 115 ms / 2,000 ms
コード長 3,536 bytes
コンパイル時間 3,869 ms
コンパイル使用メモリ 233,452 KB
実行使用メモリ 57,984 KB
最終ジャッジ日時 2024-09-17 21:57:52
合計ジャッジ時間 5,313 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include "atcoder/all"
#define debug cout << "OK" << endl;
template<typename T>
inline bool chmax(T& a, const T b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
inline bool chmin(T& a, const T b) { if (a > b) { a = b; return true; } return false; }
inline int Code(char c) {
    if ('A' <= c and c <= 'Z')return (int)(c - 'A');
    if ('a' <= c and c <= 'z')return (int)(c - 'a');
    if ('0' <= c and c <= '9')return (int)(c - '0');
    assert(false);
}
inline long long sigma(const long long begin, const long long end, const long long mod = (1LL << 60)) {
    long long t = (begin + end) % mod;
    long long l = (end - begin + 1) % mod;
    return (t * l / 2) % mod;
}
using namespace std;
using namespace atcoder;
using minit = modint1000000007;
using minit2 = modint998244353;
constexpr int MOD = 1000000007;
constexpr int MOD2 = 998244353;
constexpr long long INF = 1e18;
template<typename T>
ostream& operator << (ostream& st, const vector<T>& v) {
    for (const T value : v) {
        st << value << " ";
    }
    return st;
}
template<typename T>
istream& operator >> (istream& st, vector<T>& v) {
    for (T& value : v) {
        st >> value;
    }
    return st;
}
long long pow_(const long long a, const long long b, const long long m = INF) {
    long long res = 1;
    long long base = a;
    for (int i = 0; i < 64; i++) {
        if (b & (1ll << i))res *= base;
        res %= m;
        base = base * base;
        base %= m;
    }
    return res;
}
inline int gcd(const int a, const int b) { return (b == 0 ? a : gcd(b, a % b)); }
inline int lcm(const int a, const int b) { return a * b / gcd(a, b); }
//
int Div(int a, int b, int m) {
    return (a * pow_(b, m - 2, m)) % m;
}
class nCk {
public:
    vector<long long> fact, fact_inv, inv;
    long long m;
    /*  init_nCk :二項係数のための前処理
        計算量:O(n)
    */
    void init_nCk(int SIZE,int mod) {
        m = mod;
        fact.resize(SIZE + 5);
        fact_inv.resize(SIZE + 5);
        inv.resize(SIZE + 5);
        fact[0] = fact[1] = 1;
        fact_inv[0] = fact_inv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < SIZE + 5; i++) {
            fact[i] = fact[i - 1] * i % m;
            inv[i] = m - inv[m % i] * (m / i) % m;
            fact_inv[i] = fact_inv[i - 1] * inv[i] % m;
        }
    }
    /*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
        計算量:O(1)
    */
    long long com(int n, int k) {
        assert(!(n < k));
        assert(!(n < 0 || k < 0));
        return fact[n] * (fact_inv[k] * fact_inv[n - k] % m) % m;
    }
};
//
class Solver {
public:
    int T;
    Solver() :T(1) {}
    ~Solver(){}
    void ios()const;
    void multi();
    void solve() const;
    void sp(int x)const;
    void ft()const;
    //
    
    //
};
void Solver::ios() const {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    return;
}
void Solver::multi() {
    cin >> T;
    return;
}
void Solver::sp(const int x)const {
    cout << fixed << setprecision(x) << endl;
    return;
}
void Solver::ft() const {
    
}
void Solver::solve() const {
    long long N, K;
    cin >> N >> K;
    vector<vector<minit>> DP(N + 3, vector<minit>(K + N + 10, 0));
    DP[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= K; j++) {
            DP[i + 1][j] += DP[i][j];
            DP[i + 1][j + i + 1] -= DP[i][j];
        }
        for (int j = 0; j <= K + N; j++)DP[i + 1][j + 1] += DP[i + 1][j];
    }
    minit ans = 0;
    for (int i = 0; i <= K; i++) {
        ans += DP[N][i];
    }
    cout << ans.val() << endl;
}
signed main() {
    Solver solver;
    solver.ios();
    //solver.ft();
    //solver.multi();
    //solver.sp();
    for (int i = 0; i < solver.T; i++)
        solver.solve();
    return 0;
}
/*
* わらびのコードこーどすぺーす
 (σ･∀･)σｹﾞｯﾂ!!
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0