Hazoq y la evasión fiscal#12215

Hazoq y la evasión fiscal (Editorial)

Autor del problema:	De3b0o
Preparado por:	De3b0o
Editado por:	Hasan Saleh (MathModel)

Solución

Primero contemos todos los arreglos posibles ignorando la última condición.

El problema se reduce a:

$Contar el n u ˊ mero de arreglos de tama n ˜ o m \leq x cuya suma es n$ \textbf{Contar el número de arreglos de tamaño } m \le x \textbf{ cuya suma es } n.

Este es un problema estándar de $estrellas y barras$ , la respuesta para un $m$ fijo es:

(m - 1 n - 1)

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

Por lo tanto, el número total de arreglos (ignorando la última condición) es:

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

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

Llamaremos al número Total.

Ahora debemos eliminar los arreglos donde $max - min < k$ \max - \min < k, los llamaremos arreglos MALOS.

Si $max - min < k$ \max - \min < k, entonces todos los elementos del arreglo están en algún intervalo de longitud como máximo $k - 1$ k-1. Es decir, existe algún entero $L$ tal que:

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)

Fijemos $m$ (tamaño del arreglo), $min$ (elemento mínimo en el arreglo) y $c$ (número de elementos en el arreglo que son iguales a $min$ ).

Podemos ver que el número de arreglos MALOS con $m$ , $min$ y $c$ fijos es:

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

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

Donde $f (x, y)$ f(x,y) es el número de arreglos de tamaño $y$ y suma $x$ tales que todos los elementos están en el rango $[1, k - 1]$ [1,k-1].

Podemos calcular $(c m)$ \displaystyle \binom{m}{c} en $O (1)$ usando algunos precálculos.

Y podemos calcular todos los posibles $f (x, y)$ f(x,y) usando programación dinámica:

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

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

d p [0] [0] = 1

dp[0][0]=1

Transición:

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]

Usamos sumas prefijas para que cada estado pueda ser computado en $O (1)$ .

La complejidad total de la dp es $O (n \cdot x)$ \mathcal{O}(n \cdot x) ya que $max i = n, max j = x$ \max i = n , \max j = x.

Ahora la respuesta debería ser Total menos el número de arreglos MALOS.

En otras palabras:

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}

Para cada $m$ ( $1 \leq m \leq x$ 1 \le m \le x) hay $\frac{n}{m}$ \frac{n}{m} valores diferentes de $min$ , y $m$ valores diferentes de $c$ , así que la complejidad es $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).

Por lo tanto, la complejidad total del código es $O (n \cdot x)$ \mathcal{O}(n \cdot x) que es lo suficientemente rápida para pasar.

Lo siguiente es la implementación:


#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 << "SÍ" << "\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;
}