結果

問題 No.824 Many Shifts Hard
ユーザー kyort0nkyort0n
提出日時 2019-04-26 23:14:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,499 bytes
コンパイル時間 1,639 ms
コンパイル使用メモリ 169,592 KB
実行使用メモリ 181,432 KB
最終ジャッジ日時 2024-11-25 06:53:11
合計ジャッジ時間 50,270 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 221 ms
33,792 KB
testcase_01 AC 221 ms
102,072 KB
testcase_02 WA -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 WA -
testcase_14 TLE -
testcase_15 WA -
testcase_16 AC 283 ms
181,432 KB
testcase_17 TLE -
testcase_18 AC 211 ms
165,812 KB
testcase_19 AC 211 ms
33,920 KB
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;
ll inv[1000000];
ll FactorialInv[1000000];
ll Factorial[1000000];
ll beki(ll a, ll b){
    if(b == 0){
        return 1;
    }
    ll ans = beki(a, b / 2);
    ans = ans * ans % mod;
    if(b % 2 == 1){
        ans = ans * a % mod;
    }
    return ans;
}
void init_combination(){
    inv[1] = 1;
    FactorialInv[1] = 1;
    Factorial[1] = 1;
    Factorial[0] = 1;
    FactorialInv[0] = 1;
    inv[1] = 0;
    for(int i = 2; i < 1000000; i++){
        inv[i] = beki(i, mod - 2);
        Factorial[i] = Factorial[i - 1] * i % mod;
        FactorialInv[i] = FactorialInv[i - 1] * inv[i] % mod;
    }
}
ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a - b] % mod;
    return ans;
}
ll N, K;
ll dp[305][305][305]; //dp[i][j][k]:iターン経過時点で、境界直前の駒がjマス移動、境界直後のコマがkマス移動している確率
//ただし、途中で境界直後のコマが境界直前のコマに追いついてはいけない
ll dp2[305][305];
int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    init_combination();
    cin >> N >> K;
    if(N==1) {
        cout << 0 << endl;
        return 0;
    }
    dp[0][0][0] = 1;
    ll sum = 0;
    for(int time = 0; time <= K; time++) {
        for(int before = 0; before <= time; before++) {
            for(int after = 0; after <= time; after++) {
                //cerr << time << " " << before << " " << after << " " << dp[time][before][after] << endl;
                dp[time+1][after][before] += dp[time][after][before] * (N-2);
                dp[time+1][after][before] %= mod;
                dp[time+1][after+1][before] += dp[time][after][before];
                dp[time+1][after+1][before] %= mod;
                if(after > before) {
                    dp[time+1][after][before+1] += dp[time][after][before];
                    dp[time+1][after][before+1] %= mod;
                }
            }
        }
    }
    dp2[0][0] = 1;
    for(ll time = 0; time <= K; time++) {
        for(ll before = 0; before <= time; before++) {
            dp2[time+1][before] += dp2[time][before] * (N-1);
            dp2[time+1][before] %= mod;
            dp2[time+1][before+1] += dp2[time][before];
            dp2[time+1][before+1] %= mod;
        }
    }
    ll ans = 0;
    ll total = 1;
    for(int i = 1; i <= K; i++) total = (total * N) % mod;
    //cerr << total << endl;
    for(ll pos = 1; pos <= N; pos++) {
        ll ways = total;
        for(ll cant = pos+1; cant <= N; cant++) {
            //for(ll arrive1 = 0; arrive1 < pos; arrive1++) {
            for(ll delta = cant-pos; delta <= K; delta++) {
                for(ll arrive2 = pos+1; arrive2 <= cant; arrive2++) {
                    ways = (ways - dp[K][delta][cant-arrive2] + mod) % mod;
                }
            }
            //cerr << pos << " " << cant << " " << ways << endl;
        }
        //cerr << pos << " " << ways << endl;
        for(ll arrive = 0; arrive < pos; arrive++) {
            ways = (ways - dp2[K][N-arrive] + mod) % mod;
        }
        //cerr << pos << " " << ways << endl;
        ans = (ans + ways * pos) % mod;
    }
    cout << ans << endl;
    return 0;
}
0