Hazoq and tax evasion#12215

Hazoq and tax evasion (Çözgüdiň düşündirişi)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Solution

Let's first count all possible arrays ignoring the last condition.

The problem reduces to:

$Count the number of arrays of size m \leq x whose sum is n$ \textbf{Count the number of arrays of size } m \le x \textbf{ whose sum is } n.

This is a standard $stars and bars$ problem, the answer for a fixed $m$ is:

(m - 1 n - 1)

\binom{n-1}{m-1}

Therefore, the total number of arrays (ignoring the last condition) is:

m = 1 \sum x (m - 1 n - 1)

\sum_{m=1}^x \binom{n-1}{m-1}

We'll call the number Total.

Now we must remove the arrays where $max - min < k$ \max - \min < k, we'll call them BAD arrays.

If $max - min < k$ \max - \min < k, then all elements of the array lie in some interval of length at most $k - 1$ k-1. That is, there exists some integer $L$ such that:

L \leq a_{i} \leq L + k - 1\forall (1 \leq i \leq n)

L \leq a_i \leq L + k - 1 \forall (1 \le i \le n)

Let's fix $m$ (size of the array), $min$ (minimum element in the array) and $c$ (number of elements in the array that are equal to $min$ ).

We can see that the number of BAD arrays with fixed $m$ , $min$ and $c$ is:

f (n - m \cdot min, m - c) \cdot (c m)

f(n-m \cdot \min,m-c) \cdot \binom{m}{c}

Where $f (x, y)$ f(x,y) is the number of arrays of size $y$ and sum $x$ such that all elements are in the range $[1, k - 1]$ [1,k-1].

We can calculate $(c m)$ \displaystyle \binom{m}{c} in $O (1)$ using some precalculations.

And we can calculate all possible $f (x, y)$ f(x,y) using dynamic programming:

d p [i] [j] = f (i, j)

dp[i][j] = f(i,j)

d p [0] [0] = 1

dp[0][0]=1

Transiotion:

d p [i] [j] = v = 1 \sum k - 1 d p [i - v] [j - 1]

dp[i][j] = \sum_{v=1}^{k-1} dp[i-v][j-1]

We use prefix sums so that each state can be computed in $O (1)$ .

Total complexity of the dp is $O (n \cdot x)$ \mathcal{O}(n \cdot x) since $max i = n, max j = x$ \max i = n , \max j = x.

Now the answer should be Total minus the number of BAD arrays.

In other words:

an s = Total - 1 \leq m \leq x 1 \leq m i n \leq ⌊ \frac{n}{m} ⌋ 1 \leq c \leq m \sum d p [n - m \cdot min] [m - c] \cdot (c m)

ans = \textbf{Total} - \sum\limits_{\substack{1 \le m \le x \\ 1 \le \min \le \left\lfloor \frac{n}{m} \right\rfloor \\ 1 \le c \le m}} dp[n - m \cdot \min][m - c] \cdot \binom{m}{c}

For every $m$ ( $1 \leq m \leq x$ 1 \le m \le x) there are $\frac{n}{m}$ \frac{n}{m} different values of $min$ , and $m$ different values of $c$ , so complexity is $O (m = 1 \sum x \frac{n}{m} \cdot m) = O (n \cdot x)$ \displaystyle \mathcal{O}(\sum_{m=1}^x \frac{n}{m} \cdot m) = \mathcal{O}(n \cdot x).

So the total complexity of the code is $O (n \cdot x)$ \mathcal{O}(n \cdot x) which is fast enough to pass.

The following is the implementation:


#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
#define double long double
 
using namespace std;

mt19937 rnd(time(0));

const ll N = 1e5+9 , m = 1e9+7;

ll n , x , k;
int dp[N][501] , p[N];
ll ans = 0;
ll f[N] , inv[N];

ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    z*=z;
    z%=m;
    if(y&1)
        return z*x%m;
    else
        return z;
}

ll c(ll x , ll y)
{
    if(y>x||y<0||x<0)
        return 0;
    return f[x]*inv[y]%m*inv[x-y]%m;
}

int main()
{
    d3
    cin >> n >> x >> k;
    f[0]=1;
    for(ll i = 1 ; N>i ; i++)
        f[i]=f[i-1]*i%m;
    for(ll i = 0 ; N>i ; i++)
        inv[i]=fp(f[i],m-2);
    for(int sz = 1 ; x>=sz ; sz++)
    {
        ans+=c(n-1,sz-1);
        if(ans>m)
            ans-=m;
    }
    if(k==0)
    {
        cout << ans;
        return 0;
    }
    ans--;
    dp[0][0]=1;
    for(int sz = 1 ; x>=sz ; sz++)
    {
        p[0]=dp[0][sz-1];
        for(int i = 1 ; n>=i ; i++)
        {
            p[i]=p[i-1]+dp[i][sz-1];
            if(p[i]>m)
                p[i]-=m;
        }
        for(int sum = 1 ; n>=sum ; sum++)
        {
            dp[sum][sz]=p[sum-1];
            if(sum>=k)
                dp[sum][sz]-=p[sum-k];
            if(dp[sum][sz]<0)
                dp[sum][sz]+=m;
        }
    }
    for(int sz = 2 ; x>=sz ; sz++)
    {
        for(int j = 1 ; sz>=j ; j++)
        {
            ll e = 0;
            for(int i = n-sz ; i>=0 ; i-=sz)
                e+=dp[i][sz-j];
            e%=m;
            e*=c(sz,j);
            e%=m;
            ans-=e;
            if(ans<0)
                ans+=m;
        }
    }
    cout << ans;
}