結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー Tawara
提出日時 2016-03-14 19:25:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 1,320 bytes
コンパイル時間 882 ms
コンパイル使用メモリ 41,856 KB
実行使用メモリ 11,124 KB
最終ジャッジ日時 2024-10-15 19:42:54
合計ジャッジ時間 2,501 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:30:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   30 |         scanf("%d %d %d",&Gx,&Gy,&K);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
main.cpp:35:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |                 scanf("%d %d %d",&x,&y,&N); p = P(x,y); shift = i*4;
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

struct P {
	int x,y;
	P() {}
	P(int x, int y) : x(x), y(y){}
	P operator + (P p){return P(x + p.x, y + p.y);}
	P operator * (int d){return P(x*d, y*d);}
	bool operator == (P p){return (x == p.x && y == p.y);}
	bool operator != (P p){return (x != p.x || y != p.y);}
};

#define range(i,a,b) for(int i=(a); i < (b); i++)
#define rep(i,n) range(i,0,n)
#define MOD 1000000007

LL C[76][76];

int main(){
	int Gx,Gy,K,x,y,N,shift,mul,total,dup_n;
	LL tmp,ans = 0;
	P p,mp,g,np = P(MOD,MOD);
	vector <P> dp(1<<20);
	scanf("%d %d %d",&Gx,&Gy,&K);
	rep(i,1<<(K*4)) dp[i] = np;
	dp[0] = P(0,0); g = P(Gx,Gy); C[0][0] = 1;
	rep(i,K*15) rep(j,i+2) C[i+1][j] = (C[i][j]+(j>0 ? C[i][j-1]:0))%MOD;
	rep(i,K){
		scanf("%d %d %d",&x,&y,&N); p = P(x,y); shift = i*4;
		for (int j = 0; N > 0; j++){
			mul = min(1<<j,N); mp = p * mul; N-=mul;
			for (int k = (1<<(j+shift))-1; k >= 0; k--){
				if (dp[k] == np) continue;
				dp[k+(mul<<shift)] = dp[k] + mp;
			}
		}
	}
	rep(k,1<<(K*4)){
		if (dp[k] != g) continue;
		total = 0; tmp = 1;
		rep(i,K) total+=(k>>(i*4))%16;
		rep(i,K){
			dup_n = (k>>(i*4))%16;
			tmp = tmp * C[total][dup_n] % MOD;
			total-=dup_n;
		}
		ans = (ans + tmp) % MOD;
	}
	printf("%lld\n",ans);
	return 0;
}
0