Submission #1305133

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int M = 1000000007;

int cnt[100010];
long long dp[5][100010];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int d;
        cin >> d;
        ++cnt[d];
    }
    for (int i = 0; i < 100010; ++i) {
        dp[0][i] = 1;
    }
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 100005; ++j) {
            dp[i + 1][j] = dp[i][j / 2] * cnt[j] % M;
        }

        for (int j = 0; j < 100005; ++j) {
            dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i + 1][j + 1]) % M;
        }
    }
    cout << dp[4][100001] << "\n";

    return 0;
}

Submission Info

Judge Result