Permutasiya Düzgün Cəmi#12308

Permutasiya Düzgün Cəmi (Həll təhlili)

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

Həll

Bizə uzunluğu $n$ olan rəqəmlərdən ibarət $s$ simli verilir. Hər bir $i$ mövqeyi üçün, biz $s_{i}$ s_i-ni $i$ mövqeyində düzəldirik və qalan $n - 1$ n-1 rəqəmi permutasiya edirik. Biz yalnız fərqli permutasiya nəzərə alırıq və aşağıdakıları müəyyən edirik:

f_{i} = \sum (hər permutasiya dəyəri) (mod M), M = 1 0^{9} + 7.

f_i=\sum (\text{hər permutasiya dəyəri}) \pmod{M}, \qquad M=10^9+7.

Əsas fikir

Tam ədədləri birbaşa toplamaq əvəzinə, biz mövqelərə görə töhfələri toplayırıq. Hər şey çoxluq permutasiyalarını saymağa endirilir.

1) Əsas faktlar

Rəqəm saylarını $c_{0}, \dots, c_{9}$ c_0,\dots,c_9 adlandıraq.

$m$ rəqəminin fərqli permutasiyalarının sayı:
$\frac{m !}{\prod _{d = 0}^{9} c _{d} !} .$
\frac{m!}{\prod_{d=0}^9 c_d!}.
Onluq çəkilər: $i$ mövqeyi (soldan 1-indeksli) çəkisi
$1 0^{n - i} .$
10^{n-i}.
Təyin edək
$T_{n} = k = 0 \sum n - 1 1 0^{k} .$
T_n=\sum_{k=0}^{n-1}10^k.
Beləliklə, $i$ -dən başqa bütün mövqelərin çəkilərinin cəmi
$T_{n} - 1 0^{n - i} .$
T_n-10^{n-i}.

2) Bir mövqeyi düzəltmək

İndeksi $i$ düzəldin və

v = s_{i} .

v=s_i.

Bu rəqəmi çoxluqdan çıxarın.

Düzəldilmiş mövqenin töhfəsi

Rəqəm $v$ həmişə $i$ mövqeyində oturur. Qalan $n - 1$ n-1 rəqəm

\frac{( n - 1 )!}{\prod c _{d}^{'} !}

\frac{(n-1)!}{\prod c'_d!}

şəkilində permutasiya edilə bilər.

Beləliklə, düzəldilmiş mövqenin töhfəsi

1 0^{n - i} \cdot v \cdot \frac{( n - 1 )!}{\prod c _{d}^{'} !} .

10^{n-i}\cdot v \cdot \frac{(n-1)!}{\prod c'_d!}.

Digər mövqelərin töhfəsi

İndi qalan $n - 1$ n-1 mövqeləri nəzərə alaq.

Hələ də mövcud olan bir rəqəm dəyəri $j$ seçin. Əgər $j$ -ni bir xüsusi digər mövqeyə yerləşdirsək, qalan rəqəmlər

\frac{( n - 2 )!}{( c _{j}^{'} - 1 )! \prod _{d \neq = j} c _{d}^{'} !}

\frac{(n-2)!}{(c'_j-1)!\prod_{d\neq j} c'_d!}

şəkilində permutasiya edilə bilər.

Bu say hansı mövqeyi seçməyimizdən asılı deyil. Beləliklə, bütün digər mövqelər üzrə toplama sadəcə onların çəkilərinin cəmi ilə vurulur:

T_{n} - 1 0^{n - i} .

T_n-10^{n-i}.

Buna görə, rəqəm $j$ -nin bütün digər mövqelər üzrə ümumi töhfəsi

j \cdot \frac{( n - 2 )!}{( c _{j}^{'} - 1 )! \prod _{d \neq = j} c _{d}^{'} !} \cdot (T_{n} - 1 0^{n - i}) .

j \cdot \frac{(n-2)!}{(c'_j-1)!\prod_{d\neq j} c'_d!} \cdot (T_n-10^{n-i}).

Bütün $j = 0 \dots 9$ j=0\dots9 üzrə toplama düzəldilməmiş mövqelərin tam töhfəsini verir.

3) Son formul

Hər şeyi bir araya gətirərək:

f_{i} = 1 0^{n - i} \cdot v \cdot \frac{( n - 1 )!}{\prod c _{d}^{'} !} + (T_{n} - 1 0^{n - i}) \cdot j = 0 \sum 9 j \cdot \frac{( n - 2 )!}{( c _{j}^{'} - 1 )! \prod _{d \neq = j} c _{d}^{'} !} (mod M) .

f_i = 10^{n-i}\cdot v \cdot \frac{(n-1)!}{\prod c'_d!} + (T_n-10^{n-i}) \cdot \sum_{j=0}^9 j \cdot \frac{(n-2)!}{(c'_j-1)!\prod_{d\neq j} c'_d!} \pmod M.

Bu, hər $i$ üçün müstəqil hesablanır.

4) Komplekslik

Rəqəmlər yalnız $0$ -dan $9$ -a qədərdir, buna görə də bütün faktorial bölmələr sabit ölçülü çoxluq üzərindədir. Hər mövqe üçün, biz $0..9$ rəqəmləri üzərində iterasiya edirik.

Ümumi komplekslik: $O (n)$ .

kiçik bir sabit amillə.

Tətbiq

mod=10**9+7
mx=10**6+5
pw=[0]*mx
fc=[0]*mx
iv=[0]*mx
c=[0]*10

def solve():
    s=input().strip()
    n=len(s)
    for i in range(10):c[i]=0
    for x in s:c[int(x)]+=1
    tp=0
    for i in range(n):tp=(tp+pw[i])%mod
    for i in range(n):
        v=int(s[i])
        tp2=(tp-pw[n-i-1])%mod
        c[v]-=1
        w=fc[n-1]
        for k in range(10):w=w*iv[c[k]]%mod
        ans=pw[n-i-1]*w%mod*v%mod
        for j in range(1,10):
            c[j]-=1
            w2=fc[n-2]
            for k in range(10):w2=w2*iv[c[k]]%mod
            c[j]+=1
            ans=(ans+w2*tp2%mod*j)%mod
        c[v]+=1
        print(ans,end=' ')
    print()

pw[0]=fc[0]=iv[0]=1
for i in range(1,1000001):
    pw[i]=pw[i-1]*10%mod
    fc[i]=fc[i-1]*i%mod
    iv[i]=pow(fc[i],mod-2,mod)

for _ in range(int(input())):solve()

Python