Palindrome Subsequence Sum (Editorial)

Palindrome Subsequence Sum#12335

If array $a$ contains two elements that are equal, then $f (a) = 2$ f(a) = 2 otherwise $f (a) = 0$ f(a) = 0. The number of arrays $a$ where $f (a) = 0$ f(a) = 0 is $n!$ because this forces all elements to be distinct which means all arrangement of ${1, 2, 3, .., n}$ \{1,2,3,..,n\}.

count (a_{f (a) = 2}) = all - count (a_{f (a) = 0})

\text{count}(a_{f(a)=2})=\text{all}-\text{count}(a_{f(a)=0})

and since each element in the array holds $n$ choices then overall arrays count is $n^{n}$ n^n.

Therefore, the answer is

(n^{n} - n!) \cdot 2.

(n^n - n!) \cdot 2.

Complexity $O (1 0^{6} + \sum lo g_{2} (n))$ O(10^6+ \sum \log_2(n))

fact=[1]
cur=1
mod=10**9+7
for i in range(1,10**6+2):
    cur*=i
    cur%=mod
    fact.append(cur)
for _ in range(int(input())):
    n=int(input())
    ans=pow(n,n,mod)-fact[n]%mod
    ans%=mod
    print((2*ans)%mod)

Python