fork download
copy 
  1. /*
  2.  *  D. Aragorn is Gone | SRBD Code Contest - 2024 (Round 1)
  3.  *  Author: Sohom Sahaun | @sohomsahaun | CF: sahaun
  4.  */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
  10. using ll = long long;
  11.  
  12. const ll MOD = 1000000007;
  13. const int MX = 105;
  14. ll dp[MX][MX][2*MX];
  15. ll a[MX];
  16. ll n, groups;
  17.  
  18. ll solve(ll ind, ll rem, ll mod) {
  19.   if (ind > n) {
  20.     if ((rem == 0) && (mod == groups)) return 1;
  21.     return 0;
  22.   }
  23.  
  24.   ll& curr = dp[ind][rem][mod];
  25.   if (curr != -1) return curr;
  26.  
  27.   curr = solve(ind+1, rem, mod);
  28.  
  29.   if (rem > 0) {
  30.     ll m = (mod - groups + a[ind]) % groups;
  31.     curr = (curr + solve(ind+1, rem-1, m + groups)) % MOD;
  32.   }
  33.  
  34.   return curr;
  35. }
  36.  
  37. void clear() {
  38.   ll i, j, k;
  39.   for (i = 0; i <= n+1; ++i) {
  40.     for (j = 0; j <= n+1; ++j) {
  41.       for (k = 0; k <= 2*n+1; ++k) dp[i][j][k] = -1;
  42.     }
  43.   }
  44. }
  45.  
  46. int main() {
  47.   FAST;
  48.  
  49.   int tc = 1, ti;
  50.   cin >> tc;
  51.  
  52.   for (ti = 1; ti <= tc; ++ti) {
  53.     ll i, ans;
  54.     cin >> n;
  55.  
  56.     for (i = 1; i <= n; ++i) cin >> a[i];
  57.  
  58.     ans = 0;
  59.     for (i = 1; i <= n; ++i) {
  60.       clear();
  61.       groups = i;
  62.       ans = (ans + solve(1, groups, groups)) % MOD;
  63.     }
  64.  
  65.     cout << "Case " << ti << ": ";
  66.     cout << ans << "\n";
  67.   }
  68.  
  69.   return 0;
  70. }
  71.  
Success #stdin #stdout 0.01s 5664KB
comments (?)
stdin
copy 
2
5
1 2 3 4 5
7
1 2 2 1 0 1 1
stdout
copy 
Case 1: 15
Case 2: 51
https://ideone.com/UULc68
language:
C++14 (gcc 8.3)
created:
282 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!