結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー legendcn
提出日時 2025-02-26 00:08:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 1,512 bytes
コンパイル時間 1,693 ms
コンパイル使用メモリ 160,152 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-26 00:08:05
合計ジャッジ時間 3,462 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:58:11: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |     scanf ("%lld%lld%lld", &X, &Y, &K);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:59:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |     for (int i = 1; i <= K; i ++ ) scanf ("%lld%lld%lld", &x[i], &y[i], &c[i]);
      |                                    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

# include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
# define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 10, M = 100005, mod = 1e9 + 7;

int X, Y, K;
int x[N], y[N], c[N];
int mul[M], inv[M];
int quick_pow (int a, int b = mod - 2)
{
    int ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}
void init ()
{
    mul[0] = 1; for (int i = 1; i < M; i ++ ) mul[i] = mul[i - 1] * i % mod;
    inv[M - 1] = quick_pow (mul[M - 1]);
    for (int i = M - 2; i >= 0; i -- ) inv[i] = inv[i + 1] * (i + 1) % mod;
}
int chs[N];
int ans;
void dfs (int dep)
{
    if (dep > K)
    {
        int nowx = 0, nowy = 0;
        for (int i = 1; i <= K; i ++ ) nowx += x[i] * chs[i], nowy += y[i] * chs[i];
		if (nowx == X && nowy == Y)
        {
            int cnt = 0;
            for (int i = 1; i <= K; i ++ ) cnt = (cnt + chs[i]) % mod;
            int fangan = mul[cnt];
            for (int i = 1; i <= K; i ++ ) fangan = fangan * inv[chs[i]] % mod;
            ans = (ans + fangan) % mod;
		}
		return;
	}
    for (int i = 0; i <= c[dep]; i ++ )
    {
		chs[dep] = i;
		dfs (dep + 1);
	}
}
signed main ()
{
    // freopen ("move.in", "r", stdin); freopen ("move.out", "w", stdout);
    init ();
    scanf ("%lld%lld%lld", &X, &Y, &K);
    for (int i = 1; i <= K; i ++ ) scanf ("%lld%lld%lld", &x[i], &y[i], &c[i]);
	dfs (1);
    printf ("%lld\n", ans);
    return 0;
}
0