Hazoq et l'évasion fiscale#12215

Hazoq et l'évasion fiscale (Corrigé)

Auteur du problème:	De3b0o
Préparé par:	De3b0o
Édité par:	Hasan Saleh (MathModel)

Solution

Commençons par compter tous les tableaux possibles en ignorant la dernière condition.

Le problème se réduit à :

$Compter le nombre de tableaux de taille m \leq x dont la somme est n$ \textbf{Compter le nombre de tableaux de taille } m \le x \textbf{ dont la somme est } n.

C'est un problème standard de $e ˊ toiles et barres$ \textbf{étoiles et barres}, la réponse pour un $m$ fixe est :

(m - 1 n - 1)

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

Par conséquent, le nombre total de tableaux (en ignorant la dernière condition) est :

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

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

Nous appellerons ce nombre Total.

Maintenant, nous devons retirer les tableaux où $max - min < k$ \max - \min < k, nous les appellerons tableaux MAL.

Si $max - min < k$ \max - \min < k, alors tous les éléments du tableau se trouvent dans un intervalle de longueur au plus $k - 1$ k-1. C'est-à-dire qu'il existe un entier $L$ tel 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)

Fixons $m$ (taille du tableau), $min$ (élément minimum dans le tableau) et $c$ (nombre d'éléments dans le tableau qui sont égaux à $min$ ).

Nous pouvons voir que le nombre de tableaux MAL avec $m$ , $min$ et $c$ fixes est :

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

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

Où $f (x, y)$ f(x,y) est le nombre de tableaux de taille $y$ et de somme $x$ tels que tous les éléments sont dans l'intervalle $[1, k - 1]$ [1,k-1].

Nous pouvons calculer $(c m)$ \displaystyle \binom{m}{c} en $O (1)$ en utilisant quelques précalculs.

Et nous pouvons calculer tous les $f (x, y)$ f(x,y) possibles en utilisant la programmation dynamique :

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

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

d p [0] [0] = 1

dp[0][0]=1

Transition :

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]

Nous utilisons des sommes préfixes afin que chaque état puisse être calculé en $O (1)$ .

La complexité totale de la programmation dynamique est $O (n \cdot x)$ \mathcal{O}(n \cdot x) puisque $max i = n, max j = x$ \max i = n , \max j = x.

Maintenant, la réponse devrait être Total moins le nombre de tableaux MAL.

En d'autres termes :

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}

Pour chaque $m$ ( $1 \leq m \leq x$ 1 \le m \le x), il y a $\frac{n}{m}$ \frac{n}{m} valeurs différentes de $min$ , et $m$ valeurs différentes de $c$ , donc la complexité est $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).

Ainsi, la complexité totale du code est $O (n \cdot x)$ \mathcal{O}(n \cdot x), ce qui est suffisamment rapide pour passer.

Voici l'implémentation :


#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 << "OUI" << "\n";
#define no cout << "NON" << "\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;
}