高橋君とカード / Tak and Cards [ABC 044, ARC 060 : C]

問題

http://arc060.contest.atcoder.jp/tasks/arc060_a

N枚の数が書かれたカードがある。
ここから1枚以上のカード選んで数の平均がAとなる組合せは何通り？

1 <= N <= 50
1 <= A <= 50
1 <= xi(カードの数) <= 50

考察

1. 組合せ問題と言えばDPか数学
2. DPっぽい（数が小さいから）
3. DPでした

dp[i][j][k] = i枚目までのカードでj枚選んで合計がkである組合せ
カードを選ばない　dp[i + 1][j][k] += dp[i][j][k]
カードを選ぶ　　　dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]

4. あとはdp[N][i][i*A]の総和を答えるだけ

実装

http://arc060.contest.atcoder.jp/submissions/858514

typedef long long ll;
int N, A;
int x[50];
ll dp[51][51][3010];
//-----------------------------------------------------------------
int main() {
	cin >> N >> A;
	rep(i, 0, N) cin >> x[i];
 
	dp[0][0][0] = 1;
	rep(i, 0, N) rep(j, 0, N) rep(k, 0, 2500) if(dp[i][j][k]){
		dp[i + 1][j][k] += dp[i][j][k];
		dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
	}
 
	ll ans = 0;
	rep(i, 1, N + 1) ans += dp[N][i][i*A];
	cout << ans << endl;
}