No.3435 [Cherry 8th Tune *] How Many Times Have I Rewritten the LOVE SONG?
Problem Visual
▶ Open to reveal the problem visual
Problem Statement
For a string $T$, let $\lvert T \rvert$ denote the length of $T$. Also, for $1 \leq k \leq \lvert T \rvert$, let $T_k$ denote the $k$-th character of $T$.
You are given a non-empty (not necessarily contiguous) subsequence $A$ of abcdefghijklmnopqrstuvwxyz.
For $1 \leq i \leq \lvert A \rvert, 1 \leq j \leq \lvert A \rvert$, you are given $d(A_i, A_j)$. Note that $d(A_i, A_i)=0$ for $1 \leq i \leq \lvert A \rvert$.
For strings $X, Y$ of length $M$ consisting of characters contained in $A$, define $h(X, Y)$ by $$h(X, Y) := \sum_{k = 1}^M d(X_k, Y_k)$$.
You are given $N$ strings $S_1, \dots, S_N$ of length $M$ consisting of characters contained in $A$. For each $i = 1, 2, \dots, N$, find $$H_i := \sum_{j=1}^N h(S_i, S_j)$$.
Constraints
- $A$ is a non-empty (not necessarily contiguous) subsequence of
abcdefghijklmnopqrstuvwxyz. - $0 \leq d(A_i, A_j) \leq 10^9 \quad (1 \leq i \leq \lvert A \rvert, 1 \leq j \leq \lvert A \rvert)$.
- $d(A_i, A_i) = 0 \quad (1 \leq i \leq \lvert A \rvert)$.
- $1 \leq N \leq 3000$.
- $1 \leq M \leq 3000$.
- $S_i$ is a string of length $M$ consisting of characters contained in $A$ $\quad (1 \leq i \leq N)$.
- All numbers given in the input are integers.
Input
The input is given from standard input in the following format.
$A$
$d(A_1, A_1)$ $\dots$ $d(A_1, A_{|A|})$
$\cdots$
$d(A_{|A|}, A_1)$ $\dots$ $d(A_{|A|}, A_{|A|})$
$N$ $M$
$S_1$
$\vdots$
$S_N$
Output
The output consists of $N$ lines. On line $i~(1 \leq i \leq N)$, print $H_i$ as an integer.
Do not forget the newline at the end.
Sample
Sample 1
Input
eglnosv 0 1 2 3 3 2 1 10 0 1 2 3 3 2 20 10 0 1 2 3 3 30 20 10 0 1 2 3 30 30 20 10 0 1 2 20 30 30 20 10 0 1 10 20 30 30 20 10 0 2 4 love song
Output
34 43
We explain $H_1$. We have $H_1 = h(S_1, S_1) + h(S_1, S_2)$, and $h(S_1, S_1) = 0$. Next, regarding $h(S_1, S_2)$, $$h(S_1, S_2) = d(S_{1,1}, S_{2,1}) + d(S_{1,2}, S_{2,2}) + d(S_{1,3}, S_{2,3}) + d(S_{1,4}, S_{2,4})$$ and
- $d(S_{1,1}, S_{2,1})=d($
l$,$s$)=3$ - $d(S_{1,2}, S_{2,2})=d($
o$,$o$)=0$ - $d(S_{1,3}, S_{2,3})=d($
v$,$n$)=30$ - $d(S_{1,4}, S_{2,4})=d($
e$,$g$)=1$
Sample 2
Input
a 0 4 7 aaaaaaa aaaaaaa aaaaaaa aaaaaaa
Output
0 0 0 0
For any string $X$, we have $h(X, X) = 0$, so $H_1 = H_2 = H_3 = H_4 = 0$.
Sample 3
Input
acehiloprtuvyz 0 314494608 104724885 5324504 549179606 19222002 399165599 695354275 408659881 597688443 151437226 179722653 689318127 252535978 957749869 0 801759730 739728337 237071606 234287808 554686708 637578559 71992222 918107705 979433550 76496183 440319858 644570458 66661340 93450065 0 475862350 903376449 340988748 706305207 218294620 346323197 134912188 994413106 932820420 505781092 328157233 146218811 176354549 60553290 0 144267582 334846732 490725233 40920057 65417082 578945121 981456425 633479575 397815292 18783118 825002511 356090725 998848647 568116998 0 890478876 943191726 549401055 595776247 405149204 758824525 642383908 95431741 644371087 915713687 186929986 314113107 528263664 298927204 0 113489116 673399424 38188983 97084667 940679166 85222889 665533552 964942712 195421351 612665014 954417694 949082177 850253552 147256370 0 488861602 816474455 856193523 711239546 188908168 900625962 60074082 378959009 151050984 965235187 531167527 609836474 140734379 949806587 0 857625614 139692863 471000173 971201171 120247550 2155306 295848986 759245119 186053967 171980837 285311461 462636598 83453294 143878101 0 825294886 878342132 691645764 229897982 49922258 86117240 638694452 889991764 242291364 108409007 301005333 526531009 765172383 162583483 0 176966146 655511689 646626472 251181735 687439211 540899795 385293593 17358602 326108284 919989675 630278171 129172143 312172450 815015133 0 956223026 962004929 583991752 457065515 985086035 426940730 487611304 951276505 562628038 785923576 915525767 676021391 109571350 917082766 0 167068892 765589634 379804366 315161108 940043755 856119466 281908333 626850934 974259999 49660758 458579431 906065751 288463731 517552865 0 932405754 860920155 196065801 785019749 614273106 739795623 396634158 251905109 744446007 312407690 380141988 377271676 979856128 222334810 0 3 6 cherry purple violet
Output
5993741923 3726581665 7933964062
Not all lowercase English letters contained in $A$ necessarily appear in $S_1, \dots, S_N$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun
kazuppa