Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- ll int MOD = 998244353;
- function <ll int (ll int, ll int)> pow = [&](ll int base, ll int exp)
- {
- ll int res = 1;
- while(exp)
- {
- if(exp%2)
- (res *= base) %= MOD;
- (base *= base) %= MOD;
- exp /= 2;
- }
- return res;
- };
- ll int n, x;
- cin>>n>>x;
- vector<ll int> t(n);
- for(auto &e: t) cin>>e;
- vector<ll int> prob(x+1);
- ll int inv = pow(n, MOD-2);
- vector<ll int> prob2(x+1);
- prob[0] = inv;
- for(int i=0; i<n; i++)
- {
- (prob2[t[i]] += inv) %= MOD;
- }
- for(int j=1; j<=x; j++)
- {
- (prob[j] += (inv * 1ll * prob2[j])) %= MOD;
- for(int i=0; i<n; i++)
- {
- if(t[i] + j <= x)
- (prob2[t[i]+j] += (prob2[j]*inv)) %= MOD;
- }
- }
- ll int ans = 0;
- for(int j=x; j>max(x-t[0], -1ll); j--)
- (ans += prob[j]) %= MOD;
- cout<<ans<<"\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment