Submission #862631

#TimeUsernameProblemLanguageResultExecution timeMemory
862631Mizo_CompilerMagneti (COCI21_magneti)C++14
0 / 110
195 ms4700 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double ld; #define pb push_back #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define F first #define S second const int N = 50, M = 1e9+7, L = 1e4; int n, l, r[N]; ll fact[L+2], dp[N][L+1]; ll fp(ll b, ll p) { ll ret = 1; while (p) { if ((p & 1))ret = (ret * b) % M; b = (b * b) % M; p >>= 1; } return ret; } ll nCr(int a, int b) { return (fact[a] * fp((fact[b] * fact[n-b])%M, M-2))%M; } ll sol(int i, int j) { if (i == n)return 1; if (j > l)return 0; ll &ret = dp[i][j]; if (~ret)return ret; return ret = (sol(i, j+1) + sol(i+1, j + r[0]))%M; } int main () { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> l; fact[0] = 1; for (ll i = 1; i <= L; i++) { fact[i] = (fact[i-1] * i) % M; } for (int i = 0; i < n; i++) { cin >> r[i]; } if (n <= 10) { sort(r, r+n); ll ans = 0; do { ll len = 1; for (int i = 1; i < n; i++) { len += r[i-1]; } if (len > l)continue; len %= M; ans += (len * fp(n, l - len)) % M; } while(next_permutation(r, r+n)); cout << ans << "\n"; return 0; } memset(dp, -1, sizeof dp); cout << sol(0, 1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...