Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 205
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- const int Mod = 1000000007;
- int n, a[N], x;
- int t;
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> t;
- }
- int dp[N][N*N];
- int calc(int val){
- vector<int> b(a+1,a+1+n);
- for(int i=0; i<n; i++) b[i] -= val;
- int up=0;
- int low = 0;
- int down = 0;
- for(int i=0; i<n; i++) if (b[i] <= 0) down += abs(b[i]);
- for(int i=0; i<n; i++){
- //cout << b[i] << " \n"[i==n-1];
- if (b[i] > 0) up += b[i];
- if (b[i] <= 0) low += b[i];
- }
- memset(dp, 0, sizeof dp);
- dp[0][down]=1;
- for(int i=1; i<=n; i++){
- for(int j=low; j<=up; j++){
- dp[i][j+down] = dp[i-1][j+down];
- if ((j - b[i-1]) + down >= 0){
- dp[i][j+down] += dp[i-1][j-b[i-1]+down];
- dp[i][j+down] %= Mod;
- }
- }
- }
- return dp[n][down]-1;
- }
- void solve(){
- cin >> n >> x;
- int sum = 0;
- for(int i=1; i<=n; i++){
- cin >> a[i];
- }
- cout << calc(x) << '\n';
- }
- void proc()
- {
- while (t--) solve();
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement