Сума фіксованих перестановок#12308

Сума фіксованих перестановок (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редагував:	Хасан Салех (MathModel)

Рішення

Нам дано рядок $s$ з цифр довжини $n$ . Для кожної позиції $i$ ми фіксуємо $s_{i}$ s_i на позиції $i$ і переставляємо решту $n - 1$ n-1 цифр. Ми розглядаємо лише відмінні перестановки і визначаємо:

f_{i} = \sum (значення кожної перестановки) (mod M), M = 1 0^{9} + 7.

f_i=\sum (\text{значення кожної перестановки}) \pmod{M}, \qquad M=10^9+7.

Ключова ідея

Замість того, щоб безпосередньо підсумовувати цілі числа, ми підсумовуємо внески за позицією. Все зводиться до підрахунку перестановок мультимножин.

1) Основні факти

Нехай кількість цифр буде $c_{0}, \dots, c_{9}$ c_0,\dots,c_9.

Кількість відмінних перестановок $m$ цифр:
$\frac{m !}{\prod _{d = 0}^{9} c _{d} !} .$
\frac{m!}{\prod_{d=0}^9 c_d!}.
Десяткові ваги: позиція $i$ (нумерація зліва) має вагу
$1 0^{n - i} .$
10^{n-i}.
Визначимо
$T_{n} = k = 0 \sum n - 1 1 0^{k} .$
T_n=\sum_{k=0}^{n-1}10^k.
Отже, сума ваг усіх позицій, окрім $i$ , дорівнює
$T_{n} - 1 0^{n - i} .$
T_n-10^{n-i}.

2) Фіксація однієї позиції

Зафіксуємо індекс $i$ і нехай

v = s_{i} .

v=s_i.

Видалимо цю цифру з мультимножини.

Внесок фіксованої позиції

Цифра $v$ завжди знаходиться на позиції $i$ . Залишені $n - 1$ n-1 цифри можуть бути переставлені в

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

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

способів.

Отже, внесок фіксованої позиції дорівнює

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!}.

Внесок інших позицій

Тепер розглянемо залишені $n - 1$ n-1 позиції.

Виберемо значення цифри $j$ , яке ще доступне. Якщо ми помістимо $j$ в одну конкретну іншу позицію, залишені цифри можуть бути переставлені в

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

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

способів.

Це число не залежить від того, яку позицію ми вибираємо. Отже, підсумовуючи по всіх інших позиціях, ми просто множимо на суму їх ваг:

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

T_n-10^{n-i}.

Таким чином, загальний внесок цифри $j$ по всіх інших позиціях дорівнює

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}).

Підсумовуючи по всіх $j = 0 \dots 9$ j=0\dots9, отримуємо повний внесок незакріплених позицій.

3) Остаточна формула

Збираючи все разом:

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.

Це обчислюється незалежно для кожного $i$ .

4) Складність

Цифри варіюються лише від $0$ до $9$ , тому всі ділення факторіалів відбуваються над мультимножиною постійного розміру. Для кожної позиції ми перебираємо цифри $0..9$ .

Загальна складність: $O (n)$ .

з невеликим константним фактором.

Реалізація

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