# HackerEarth Large Sub-Arrays problem solution

In this HackerEarth Large Sub-Arrays problem solution You are given an array A with size N and two integers M and K.
Let's define another array B with size N x M as the array that's formed by concatenating M copies of array A.

You have to find the number of sub-arrays of the array B with sum <= K. Since the answer can be very large you have to print the answer mod 10^9+7.

## HackerEarth Large Sub-Arrays problem solution.

`#include <bits/stdc++.h>#include <tr1/unordered_map>using namespace std;using namespace std::tr1;#define opt ios_base::sync_with_stdio(0)#define lli long long int#define ulli unsigned long long int#define I int#define S string#define D double#define rep(i,a,b) for(i=a;i<b;i++)#define repr(i,a,b) for(i=a;i>b;i--)#define in(n) scanf("%lld",&n)#define in2(a,b) scanf("%lld %lld",&a,&b)#define in3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)#define out(n) printf("%lld\n",n)#define inu(a) scanf("%lld",&a)#define outu(a) printf("%llu",a)#define ins(s) scanf("%s",&s)#define outs(s) printf("%s",s)#define mod 1000000007#define inf 100000000000000typedef long long       ll;typedef pair<lli,lli>  plli;typedef vector<lli>     vlli;typedef vector<ulli>    vulli;typedef vector<ll>      vll;typedef vector<string>  vs;typedef vector<plli>     vplli;#define MM(a,x)  memset(a,x,sizeof(a));#define ALL(x)   (x).begin(), (x).end()#define P(x)       cerr<<"{"#x<<" = "<<(x)<<"}"<<endl;#define P2(x,y)       cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<"}"<<endl;#define P3(x,y,z)  cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<"}"<<endl;#define P4(x,y,z,w)cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<", "#w" = "<<(w)<<"}"<<endl;#define PP(x,i)     cerr<<"{"#x"["<<i<<"] = "<<x[i]<<"}"<<endl;#define TM(a,b)     cerr<<"{"#a" -> "#b": "<<1000*(b-a)/CLOCKS_PER_SEC<<"ms}\n";#define UN(v)    sort(ALL(v)), v.resize(unique(ALL(v))-v.begin())#define mp make_pair#define pb push_back#define f first#define s second#define sz() size()#define nl cout<<"\n"#define MX1 100005#define MX2 1000005#define bs binary_search#define lb lower_bound#define ub upper_boundlli dx[]={0,0,-1,1,-1,-1,1,1};lli dy[]={1,-1,0,0,1,-1,-1,1};lli power(lli a,lli b)    {    lli value;    if(b==0)        {        return 1;    }    else if(b%2==0)        {        value=power(a,b/2)%mod;        return(value*value)%mod;    }    else        {        value=power(a,b/2)%mod;        return ((a*value)%mod*(value))%mod;    }}string f(lli n) {    vlli v;    lli i;    if(n==0) {        return "00";    }    string s="0";    while(n) {        v.pb(n%10);        n/=10;    }    reverse(ALL(v));    rep(i,0,v.sz()) {        s+=(v[i]+'0');    }    return s;}lli a[100005],pref[100005],suf[100005];int main(){    /*lli files=10;    while(files--) {    #ifndef ONLINE_JUDGE        string input="in"+f(files)+".txt";        string output="out"+f(files)+".txt";        freopen(input.c_str(),"r",stdin);        freopen(output.c_str(),"w",stdout);        #endif*/        opt;        lli t;        cin>>t;        while(t--) {            lli n,m,k;            cin>>n>>m>>k;            lli ans=0,i,sum=0;            rep(i,1,1+n) {                cin>>a[i];                pref[i]=a[i];                suf[i]=a[i];                sum+=a[i];            }            sum*=m;            if(sum<=k) {                lli temp=(n*m)%mod;                ans=(temp*(temp+1))%mod;                ans=(ans*power(2,mod-2))%mod;                cout<<ans<<endl;                continue;            }            sum/=m;            rep(i,2,1+n) {                pref[i]+=pref[i-1];            }            repr(i,n-1,0) {                suf[i]+=suf[i+1];            }            rep(i,1,1+n) {                if(suf[i]>=k) {                    lli temp=-1,l=i,r=n;                    while(l<=r) {                        lli mid=(l+r)/2;                        if((pref[mid]-pref[i-1])<=k) {                            temp=mid;                            l=mid+1;                        } else {                            r=mid-1;                        }                    }                    if(temp!=-1) {                        ans=(ans+(m*(temp-i+1)))%mod;                    }                    continue;                }                if((suf[i]+(m-1)*sum)<=k) {                    lli temp=(m*(2*(n-i+1)+(m-1)*n));                    temp/=2;                    ans=(ans+temp)%mod;                    continue;                }                lli cnt=(k-suf[i])/sum;                cnt++;                lli temp=(cnt*(2*(n-i+1)+(cnt-1)*n));                temp/=2;                temp%=mod;                ans=(ans+temp)%mod;                cnt--;                lli val=(k-suf[i]-cnt*sum);                lli l=1,r=n,idx=0;                while(l<=r) {                    lli mid=(l+r)/2;                    if(pref[mid]<=val) {                        idx=mid;                        l=mid+1;                    } else {                        r=mid-1;                    }                }                lli no=(n-i+1)+(cnt*n)+idx;                no%=mod;                ans=(ans+(no*(m-cnt-1)))%mod;            }            cout<<ans<<endl;        }}`