結果
問題 |
No.498 ワープクリスタル (給料日編)
|
ユーザー |
![]() |
提出日時 | 2017-03-26 01:20:13 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 1,556 bytes |
コンパイル時間 | 539 ms |
コンパイル使用メモリ | 64,172 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 06:17:48 |
合計ジャッジ時間 | 1,796 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:53:24: warning: iteration 74 invokes undefined behavior [-Waggressive-loop-optimizations] 53 | inv[i] = MOD - ( MOD / i ) * inv[ MOD % i ] % MOD; | ^ main.cpp:52:38: note: within this loop 52 | for ( long long int i = 2; i <= CON_MAX; i++ ) { | ^
ソースコード
#include <iostream> #include <vector> using namespace std; #define MOD 1000000007 #define CON_MAX 76 long long int inv[ CON_MAX ] = {}; long long int con[ CON_MAX ][ CON_MAX ]; long long int gx, gy, k; vector< long long int > x, y, n; long long int ans = 0; void kansu( long long int a, vector< long long int > v, long long int px, long long int py ) { if ( a == k ) { if ( px == gx && py == gy ) { long long int ma = 0; long long int cnt = 1; for ( long long int i = 0; i < k; i++ ) { ma += v[i]; cnt *= con[v[i]][ma]; cnt %= MOD; } ans += cnt; ans %= MOD; } return; } for ( long long int i = 0; i <= n[a]; i++ ) { kansu( a + 1, v, px, py ); px += x[a]; py += y[a]; v[a]++; } return; } int main() { inv[1] = 1; for ( long long int i = 2; i <= CON_MAX; i++ ) { inv[i] = MOD - ( MOD / i ) * inv[ MOD % i ] % MOD; } for ( long long int i = 0; i < CON_MAX; i++ ) { con[0][i] = 1; for ( long long int j = 1; j < CON_MAX; j++ ) { con[j][i] = con[j-1][i] * ( i - j + 1 ); con[j][i] %= MOD; con[j][i] *= inv[j]; con[j][i] %= MOD; } } cin >> gx >> gy >> k; vector< long long int > v; for ( long long int i = 0; i < k; i++ ) { long long int inx, iny, inn; cin >> inx >> iny >> inn; x.push_back( inx ); y.push_back( iny ); n.push_back( inn ); v.push_back( 0 ); } kansu( 0, v, 0, 0 ); cout << ans << endl; return 0; }