#159463 (C++11) No.498 ワープクリスタル (給料日編)

• 問題: No.498 ワープクリスタル (給料日編)
• ユーザー: ixmel
• 提出日時: 2017-03-24 23:18:41
• 言語: C++11 (gcc 13.3.0)
• 結果: AC
• 実行時間: 7 ms / 2,000 ms
• コード長: 1,704 bytes
• コンパイル時間: 800 ms
• コンパイル使用メモリ: 90,396 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-07-06 00:02:02
• 合計ジャッジ時間: 1,584 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 21

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<vector>
#include<string>
#include<algorithm> 
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e8;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
ll out;
ll x,y,n;
vvi in;
#define MOD 1000000007
// a^b mod MOD
ll powmod(ll a,ll b){
    ll out=1;
    ll p=a%MOD;
    while(b){
        if(b&1)out=out*p%MOD;
        p=p*p%MOD;
        b>>=1;
    }
    return out;
}
#define M 1000
vector<ll> fact;
void init(){
    fact=vector<ll>(M);
    fact[0]=fact[1]=1;
    loop(i,2,M)fact[i]=fact[i-1]*i%MOD;
}
// nCr
ll nCr(ll n,ll r){
    ll out=fact[n]*powmod(fact[r]*fact[n-r]%MOD,MOD-2)%MOD;
    return out;
}   
vi co;
void f(int a,int nx,int ny){
    if(a==n){
        if(nx!=x||ny!=y)return;
        ll sum=0;
        rep(i,n)sum+=co[i];
        ll ot=1;
        rep(i,n){
//          cout<<sum<<" "<<co[i]<<endl;
            (ot*=nCr(sum,co[i]))%=MOD;
            sum-=co[i];
        }
        (out+=ot)%=MOD;
        return;
    }
    rep(i,in[a][2]+1){
        co[a]=i;
        f(a+1,nx+i*in[a][0],ny+i*in[a][1]);
    }
}
int main(){
    init();
    cin>>x>>y>>n;
    co=vi(n);
    in=vvi(n,vi(3));
    rep(i,n)rep(j,3)cin>>in[i][j];
    f(0,0,0);
    cout<<out<<endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX