結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー roarisroaris
提出日時 2019-12-16 17:52:05
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,427 bytes
コンパイル時間 2,148 ms
コンパイル使用メモリ 174,424 KB
実行使用メモリ 4,512 KB
最終ジャッジ日時 2023-09-15 18:13:57
合計ジャッジ時間 5,690 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 WA -
testcase_05 AC 1 ms
4,384 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 217 ms
4,380 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 2 ms
4,376 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007

int Gx, Gy, K;
int x[7], y[7], N[7];
vector<int> fact = {1};

int mod_pow(int a, int n) {
    int res = 1;
    
    while (n>0) {
        if (n&1) {
            res = res*a%MOD;
        }
        
        a = a*a%MOD;
        n >>= 1;
    }
    
    return res;
}

int dfs(int d, stack<int> s) {
    if (d==K) {
        int xs = 0;
        int ys = 0;
        int ss = 0;
        vector<int> vec;
        
        for (int i=0; i<K; i++) {
            int si = s.top(); s.pop();
            xs += x[K-1-i]*si;
            ys += y[K-1-i]*si;
            ss += si;
            vec.push_back(si);
        }
        
        if (xs==Gx && ys==Gy) {
            int res = fact[ss];
            
            for (auto& vec_i : vec) {
                res *= mod_pow(fact[vec_i], MOD-2);
            }
            
            return res;
        }
        else {
            return 0;
        }
    }
    
    int res = 0;
    
    for (int i=0; i<=N[d]; i++) {
        s.push(i);
        res += dfs(d+1, s);
        res %= MOD;
        s.pop();
    }
    
    return res;
}

signed main() {
    cin >> Gx >> Gy >> K;
    
    for (int i=0; i<K; i++) {
        cin >> x[i] >> y[i] >> N[i];
    }
    
    for (int i=1; i<100; i++) {
        fact.push_back(fact.back()*i%MOD);
    }
    
    stack<int> s;
    
    cout << dfs(0, s) << endl;
}
0