Hazoq və vergi qaçaqlığı#12215

Hazoq və vergi qaçaqlığı (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

İlk öncə son şərti nəzərə almadan bütün mümkün massivləri sayaq.

Problem aşağıdakı kimi sadələşir:

$Hesablay ı n m \leq x o ¨ l c ¸ u ¨ s u ¨ ndə n cəmi olan massivlərin say ı n ı$ \textbf{Hesablayın } m \le x \textbf{ ölçüsündə } n \textbf{ cəmi olan massivlərin sayını}.

Bu, standart $ulduzlar və c ¸ ubuqlar$ \textbf{ulduzlar və çubuqlar} problemi olub, sabit $m$ üçün cavab:

(m - 1 n - 1)

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

Buna görə, son şərti nəzərə almadan toplam massivlərin sayı:

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

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

Biz bu sayını Ümumi adlandıracağıq.

İndi $max - min < k$ \max - \min < k olan massivləri çıxarmalıyıq, onlara PIS massivləri deyəcəyik.

Əgər $max - min < k$ \max - \min < k olarsa, onda massivdəki bütün elementlər ən çox $k - 1$ k-1 uzunluğunda bir intervallada yerləşir. Yəni, belə bir tam ədəd $L$ mövcuddur ki:

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)

Gəlin $m$ (massivin ölçüsü), $min$ (massivdəki minimum element) və $c$ (massivdə $min$ -ə bərabər olan elementlərin sayı) sabitləşdirək.

Görürük ki, sabit $m$ , $min$ və $c$ ilə PIS massivlərinin sayı:

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

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

Burada $f (x, y)$ f(x,y) ölçüsü $y$ və cəmi $x$ olan massivlərin sayıdır ki, bütün elementlər $[1, k - 1]$ [1,k-1] aralığındadır.

Biz $(c m)$ \displaystyle \binom{m}{c}-ni $O (1)$ -də bəzi əvvəlcədən hesablamalarla hesablaya bilərik.

Və biz dinamik proqramlaşdırma istifadə edərək bütün mümkün $f (x, y)$ f(x,y)-ni hesablaya bilərik:

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

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

d p [0] [0] = 1

dp[0][0]=1

Keçid:

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]

Hər bir vəziyyəti $O (1)$ -də hesablamaq üçün prefiks cəmlərindən istifadə edirik.

Dinamik proqramın toplam mürəkkəbliyi $O (n \cdot x)$ \mathcal{O}(n \cdot x)-dir, çünki $max i = n, max j = x$ \max i = n , \max j = x.

İndi cavab Ümumi minus PIS massivlərinin sayı olmalıdır.

Başqa sözlə:

an s = U ¨ mumi - 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{Ümumi} - \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}

Hər $m$ üçün ( $1 \leq m \leq x$ 1 \le m \le x) $\frac{n}{m}$ \frac{n}{m} fərqli $min$ dəyərləri və $m$ fərqli $c$ dəyərləri var, buna görə mürəkkəblik $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)-dir.

Beləliklə, kodun toplam mürəkkəbliyi $O (n \cdot x)$ \mathcal{O}(n \cdot x)-dir ki, bu da keçmək üçün kifayət qədər sürətlidir.

Aşağıda tətbiqetmə verilmişdir:


#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 << "BƏLİ" << "\n";
#define no cout << "XEYİR" << "\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;
}