Genetyka

Dane jest $n$ słów o długości $m$ nad alfabetem 4-literowym. Należy znaleźć słowo (będzie dokładnie jedno takie), które różni się od każdego innego na dokładnie $K$ pozycjach.

Bardzo łatwo jest napisać rozwiązanie działające w czasie $O(n^{2}m)$, wystarczy bowiem sprawdzić dla każdej pary słów na ilu pozycjach się różnią.

Mnożenie macierzy

Zrobimy to jednak szybciej. Główny pomysł to wyrażenie zadania w terminach macierzowych i skorzystanie z pomysłowego triku.

Na początek skupimy się na podzadaniu 3, w którym alfabet jest ograniczony do dwóch liter. Niech $A_i$ oznacza wektor długości $m$, który koduje $i$-te słowo w ten sposób, że litery zamieniamy na liczby $1$ oraz $-1$. Przykładowo słowo ACCAC zostanie zakodowane przez $(1,-1,-1,1,-1)$.

Rozważmy dwa wektory $A_i$ oraz $A_j$ i obliczmy ich iloczyn skalarny: $$A_i\cdot A_j=\sum _{1\le k\le m}{A}_i[k]\cdot A_j[k].$$

Na każdej pozycji, która ma takie same litery, dostaniemy $1\cdot 1=(-1)\cdot (-1)=1$, a na pozycjach z różnymi literami dostaniemy $1\cdot (-1)=(-1)\cdot 1=-1$. Zatem wynik iloczynu to będzie liczba pozycji o takich samych literach minus liczba pozycji o różnych literach. Jeśli więc chcemy, żeby $i$-te słowo różniło się od $j$-tego na $K$ pozycjach, to musi być $$A_i\cdot A_j=(m-K)-K=m-2K.$$

Niech macierz $A$ będzie zawierać wszystkie słowa ułożone w wierszach (będzie zatem miała $n$ wierszy i $m$ kolumn). Przemnożenie macierzy $A$ przez pionowy wektor $V$ o długości $m$ daje w wyniku pionowy wektor długości $n$, zawierający na $i$-tej pozycji iloczyn skalarny $A_i\cdot V$.

Słowo $A_i$ jest tym, którego szukamy, jeśli przemnożenie macierzy $A$ przez pionowy wektor $A_i$ da nam w wyniku pionowy wektor $W_i$, w którym wszystkie wartości są równe $m-2K$, oprócz $i$-tej wartości, która jest oczywiście równa $m$ (bo oznacza $A_i\cdot A_i$).

Niestety, mnożenie macierzy $A$ przez wektor $V$ umiemy wykonać w czasie $O(nm)$, a potrzebujemy $n$ takich mnożeń (dla każdego wyboru $V$), zatem nadal daje to nam złożoność czasową $O(n^{2}m)$.

Sprytna sztuczka -- sprawdzanie wyniku mnożenia macierzy

Okazuje się jednak, że sprawdzenie, czy wynik mnożenia macierzy jest konkretną macierzą $W$ można zrobić szybciej niż obliczenie wyniku mnożenia od zera.

Chcemy sprawdzić, czy $A\cdot A_s$ daje w wyniku $W_s$. To sprowadza się do sprawdzenia układu $n$ równań (dla $1\le i\le n$): $$A_i\cdot A_s-W_s[i]=0.$$

Zrobimy to metodą probabilistyczną. Losujemy $n$ dużych liczb $p_i$ i sumujemy wszystkie równania (modulo duża liczba pierwsza $P$), przemnażając $i$-te z nich przez liczbę $p_i$:

$$\sum _i{p}_i(A_i\cdot A_s-W_s[i])=0.$$

Jeśli układ był prawidłowy, to powyższa suma da 0. Okazuje się jednak, że jeśli suma ta jest 0, to z dużym prawdopodobieństwem układ równań musi być prawidłowy.

Wynika to z lematu Schwartza--Zippela, który orzeka, że niezerowy wielomian $n$ zmiennych o stopniu $d$ nad ciałem $S$ ewaluuje się do 0 dla losowych wartości z prawdopodobieństwem $\le d/|S|$. Wykonywanie obliczeń modulo liczba pierwsza $P$ oznacza działania nad ciałem rozmiaru $|S|=P$.

Jeśli zatem weźmiemy wielomian $$\sum _i{x}_i(A_i\cdot A_s-W_s[i]),$$ to dla losowych $x_i=p_i$ jest bardzo mała szansa $1/P$, że będzie on 0, chyba że wielomian jest zerowy, czyli wszystkie $A_i\cdot A_s-W_s[i]$ są zerami. Biorąc $P={10}^9+7$ szansa pomyłki jest bardzo mała. W razie potrzeby możemy ją zwiększyć, przez wzięcie większej liczby $P$ lub wykonanie obliczenia niezależnie dla kilku różnych wartości $P$.

Zatem, wystarczy sprawdzić, czy

$$\sum _i{p}_i(A_i\cdot A_s)=\sum _i{p}_i{W}_s[i]$$

Po prawej stronie mamy po prostu $$(\sum _i{p}_i)(m-2K)+p_s\cdot 2K$$

a po lewej stronie mamy: $$\sum _i{p}_i(\sum _k{A}_i[k]\cdot A_s[k])=\sum _i\sum _k{p}_i\cdot A_i[k]\cdot A_s[k]=\sum _k(\sum _i{p}_i\cdot A_i[k])\cdot A_s[k]=\sum _k{B}_k\cdot A_s[k],$$

gdzie wartość $B_k$ jest po prostu sumą elementów $k$-tej kolumny macierzy $A$, przemnożonych przez kolejne liczby $p_i$.

Wyznaczyć wektory $B_k$ możemy w czasie $O(nm)$. Dzięki temu każde sprawdzenie wektora $A_s$ będzie działać w czasie $O(n)$. Ostatecznie, złożoność czasowa całego algorytmu wyniesie $O(nm)$.

const int N = 4110, P = 1000000007;
int n,m,K;
char w[N][N];
int a[N][N];
int p[N],sum_p;
int b[N];

int main() {
  scanf("%d%d%d",&n,&m,&K);
  REP(i,n) scanf("%s",w[i]);

  REP(i,n) REP(j,m) {
    a[i][j] = w[i][j] == 'A' ? 1 : P-1;
  }

  REP(i,n) {
    p[i] = rand() % P;
    sum_p = (sum_p + p[i]) % P;
  }
  sum_p = ll(sum_p) * (P + m - 2*K) % P;

  REP(i,n) REP(j,m) {
    b[j] = (b[j] + ll(a[i][j]) * p[i]) % P;
  }

  int ans = -1;
  REP(s,n) {
    int sum = 0;
    REP(i,m) {
      sum = (sum + ll(b[i]) * a[s][i]) % P;
    }
    if (sum == (sum_p + ll(p[s]) * (2*K)) % P) {
      ans = s+1;
    }
  }

  printf("%d\n", ans);
}

Dowolny alfabet

Zrobimy sztuczkę, dzięki której dla dowolnego alfabetu rozmiaru $A$, algorytm będzie działał w czasie $O(Anm)$. Każde słowo zamieniamy na słowo binarne o długości $Am$, przez zastąpienie $i$-tej litery alfabetu $A$-literowym słowem składającym się z liter A i jednej litery C na $i$-tej pozycji. Zatem dla $A=4$ litery zastępujemy przez ciągi CAAA, ACAA, AACA i AAAC. Ciągi odpowiadające różnym literom różnią się na dokładnie dwóch pozycjach. Zatem dobre słowo różni się od wszystkich pozostałych na dokładnie $2K$ pozycjach. Wystarczy zatem wprowadzić następującą poprawkę do poprzedniego algorytmu:

  code['A'] = 0;
  code['C'] = 1;
  code['G'] = 2;
  code['T'] = 3;

  REP(i,n) REP(j,4*m) {
    a[i][j] = P-1;
  }
  REP(i,n) REP(j,m) {
    a[i][4*j + code[w[i][j]]] = 1;
  }
  m *= 4;
  K *= 2;