Submission #3771304

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[0].size()){ cout << m[i][j] << ","; } cout << endl; }}

int modpow(int x, int n, int m){
    int a = 1;
    IREP(i, 64){
        a = (a * a) % m;
        if(((n >> i) & 1) == 1) a = (a * x) % m;
    }
    return a;
}

#define M 3300
signed main(){

    int N, K; cin >> N >> K;
    int mod = 1000000007;

    mat dp(N + 1, vec(M + 1, 0));
    if(K >= N) dp[N][1] = 1;
    dp[N][0] = K + 1 - dp[N][1];
    IFOR(i, 1, N){
        int d = K - i;
        if(d > 0) REP(j, M + 1){
            dp[i][j] += d * dp[i + 1][j];
            dp[i][j] %= mod;
        }
        REP(a, min(K, i) + 1){
            REP(j, M + 1){
                int s = j + (a + j) / i;
                if(s <= M){
                    dp[i][s] += dp[i + 1][j];
                    dp[i][s] %= mod;
                }
            }
        }
    }
    //debug(dp);
    
    int ans = (K * (K + 1) / 2 * N * modpow(K + 1, N - 1, mod)) % mod;;
    //cout << ans << endl;
    REP(i, M + 1){
        ans -= i * dp[1][i];
        ans = (ans % mod + mod) % mod; 
    }

    cout << ans << endl;
    
    return 0;
}

Submission Info

Judge Result