Газок та ухилення від сплати податків#12215

Газок та ухилення від сплати податків (Розбір)

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редагував:	Hasan Saleh (MathModel)

Рішення

Спочатку давайте підрахуємо всі можливі масиви, ігноруючи останню умову.

Проблема зводиться до:

$Підрахуйте кількість масивів розміру m \leq x, сума яких дорівнює n$ \textbf{Підрахуйте кількість масивів розміру } m \le x \textbf{, сума яких дорівнює } n.

Це стандартна задача $зірки та бари$ \textbf{зірки та бари}, відповідь для фіксованого $m$ :

(m - 1 n - 1)

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

Отже, загальна кількість масивів (ігноруючи останню умову) дорівнює:

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

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

Ми назвемо цю кількість Загальна.

Тепер ми повинні виключити масиви, де $max - min < k$ \max - \min < k, ми назвемо їх ПЛОХІ масиви.

Якщо $max - min < k$ \max - \min < k, тоді всі елементи масиву лежать у деякому інтервалі довжини не більше $k - 1$ k-1. Тобто, існує деяке ціле число $L$ , таке що:

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)

Зафіксуємо $m$ (розмір масиву), $min$ (мінімальний елемент у масиві) та $c$ (кількість елементів у масиві, які дорівнюють $min$ ).

Ми можемо побачити, що кількість ПЛОХИХ масивів з фіксованими $m$ , $min$ та $c$ дорівнює:

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

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

Де $f (x, y)$ f(x,y) — це кількість масивів розміру $y$ та суми $x$ , такі що всі елементи знаходяться в діапазоні $[1, k - 1]$ [1,k-1].

Ми можемо обчислити $(c m)$ \displaystyle \binom{m}{c} за $O (1)$ , використовуючи деякі попередні обчислення.

І ми можемо обчислити всі можливі $f (x, y)$ f(x,y), використовуючи динамічне програмування:

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

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

d p [0] [0] = 1

dp[0][0]=1

Перехід:

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]

Ми використовуємо префіксні суми, щоб кожен стан можна було обчислити за $O (1)$ .

Загальна складність динамічного програмування дорівнює $O (n \cdot x)$ \mathcal{O}(n \cdot x), оскільки $max i = n, max j = x$ \max i = n , \max j = x.

Тепер відповідь повинна бути Загальна мінус кількість ПЛОХИХ масивів.

Іншими словами:

an s = Загальна - 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{Загальна} - \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}

Для кожного $m$ ( $1 \leq m \leq x$ 1 \le m \le x) існує $\frac{n}{m}$ \frac{n}{m} різних значень $min$ , і $m$ різних значень $c$ , тому складність дорівнює $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).

Отже, загальна складність коду дорівнює $O (n \cdot x)$ \mathcal{O}(n \cdot x), що достатньо швидко, щоб пройти.

Наступне — реалізація:


#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;
}