Permutation Fix Sum#12308

Permutation Fix Sum (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

We are given a string $s$ of digits of length $n$ . For each position $i$ , we fix $s_{i}$ s_i at position $i$ and permute the remaining $n - 1$ n-1 digits. We consider only distinct permutations and define:

f_{i} = \sum (value of each permutation) (mod M), M = 1 0^{9} + 7.

f_i=\sum (\text{value of each permutation}) \pmod{M}, \qquad M=10^9+7.

Key idea

Instead of summing whole numbers directly, we sum contributions per position. Everything reduces to counting multiset permutations.

1) Basic facts

Let the digit counts be $c_{0}, \dots, c_{9}$ c_0,\dots,c_9.

Number of distinct permutations of $m$ digits:
$\frac{m !}{\prod _{d = 0}^{9} c _{d} !} .$
\frac{m!}{\prod_{d=0}^9 c_d!}.
Decimal weights: position $i$ (1-indexed from left) has weight
$1 0^{n - i} .$
10^{n-i}.
Define
$T_{n} = k = 0 \sum n - 1 1 0^{k} .$
T_n=\sum_{k=0}^{n-1}10^k.
So the sum of weights of all positions except $i$ is
$T_{n} - 1 0^{n - i} .$
T_n-10^{n-i}.

2) Fixing one position

Fix index $i$ and let

v = s_{i} .

v=s_i.

Remove this digit from the multiset.

Fixed position contribution

The digit $v$ always sits at position $i$ . The remaining $n - 1$ n-1 digits can be permuted in

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

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

ways.

Thus the contribution of the fixed position is

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

Other positions contribution

Now consider the remaining $n - 1$ n-1 positions.

Pick a digit value $j$ still available. If we place $j$ in one specific other position, the remaining digits can be permuted in

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

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

ways.

This number does not depend on which position we choose. So summing over all other positions simply multiplies by the sum of their weights:

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

T_n-10^{n-i}.

Hence, the total contribution of digit $j$ over all other positions is

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

Summing over all $j = 0 \dots 9$ j=0\dots9 gives the full contribution of non-fixed positions.

3) Final formula

Putting everything together:

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.

This is computed independently for each $i$ .

4) Complexity

Digits range only from $0$ to $9$ , so all factorial divisions are over a constant-size multiset. For each position, we iterate over digits $0..9$ .

Overall complexity: $O (n)$ .

with a small constant factor.

Implementation

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