結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー roaris
提出日時 2019-12-16 18:05:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 212 ms / 2,000 ms
コード長 1,455 bytes
コンパイル時間 1,850 ms
コンパイル使用メモリ 176,712 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 20:17:45
合計ジャッジ時間 5,392 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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);
                res %= MOD;
            }
            
            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