C - 高橋君とカード / Tak and Cards AtCoder Beginner Contest 044

C - 高橋君とカード / Tak and Cards
問題概略
N枚のカードがあり数字が書かれている。これらの中から1枚以上を選び、数の平均をAにしたい。選び方は何通りあるか。

制約
1<=N<=50
1<=A<=50
1<=xi <=50

解法
まず普通にナップザックとして解いてみる。
つまり、boolean[i][j]:=i枚目までで合計jが作れるかどうかを埋める。
それとは別に、long[i][j][k]:=i枚目までで合計jをk枚で作る方法は何通りあるかを作り、遷移していく。

 public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        int ave = ni();
        A = nia(N);
        boolean[][] dp = new boolean[N + 1][3000];
        long[][][] cou = new long[N + 1][3000][51];//[i][j][k]:= i枚目まででjをk枚で作る方法は何通りか
        dp[0][0] = true;
        cou[0][0][0] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3000; j++) {
                if (!dp[i][j]) continue;
                dp[i + 1][j] = true;
                dp[i + 1][j + A[i]] = true;
                for (int k = 0; k < 51; k++) {
                    cou[i + 1][j][k] += cou[i][j][k];//使わない
                    if (k < 50) cou[i + 1][j + A[i]][k + 1] += cou[i][j][k];//使う
                }
            }
        }
        long res = 0;
        for (int sum = 1; sum < 2501; sum++) {
            if (sum % ave != 0) continue;
            if (sum / ave > 50) continue;
            res += cou[N][sum][sum / ave];
        }
        System.out.println(res);
    }