Ankit_132

E

Oct 8th, 2023
256
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll     long long
  6.  
  7. int main()
  8. {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.     cout.tie(NULL);
  12.  
  13.     ll int MOD = 998244353;
  14.  
  15.     function <ll int (ll int, ll int)> pow = [&](ll int base, ll int exp)
  16.     {
  17.         ll int res = 1;
  18.  
  19.         while(exp)
  20.         {
  21.             if(exp%2)
  22.                 (res *= base) %= MOD;
  23.  
  24.             (base *= base) %= MOD;
  25.             exp /= 2;
  26.         }
  27.  
  28.         return res;
  29.     };
  30.  
  31.     ll int n, x;
  32.     cin>>n>>x;
  33.  
  34.     vector<ll int> t(n);
  35.     for(auto &e: t)   cin>>e;
  36.  
  37.     vector<ll int> prob(x+1);
  38.  
  39.     ll int inv = pow(n, MOD-2);
  40.     vector<ll int> prob2(x+1);
  41.     prob[0] = inv;
  42.  
  43.     for(int i=0; i<n; i++)
  44.     {
  45.         (prob2[t[i]] += inv) %= MOD;
  46.     }
  47.  
  48.     for(int j=1; j<=x; j++)
  49.     {
  50.         (prob[j] += (inv * 1ll * prob2[j])) %= MOD;
  51.         for(int i=0; i<n; i++)
  52.         {
  53.  
  54.             if(t[i] + j <= x)
  55.                 (prob2[t[i]+j] += (prob2[j]*inv)) %= MOD;
  56.         }
  57.     }
  58.  
  59.     ll int ans = 0;
  60.     for(int j=x; j>max(x-t[0], -1ll); j--)
  61.         (ans += prob[j]) %= MOD;
  62.  
  63.     cout<<ans<<"\n";
  64. }
  65.  
Advertisement
Add Comment
Please, Sign In to add comment