ML #2 – Cái máy nó học như thế nào

Giới thiệu

Lần đầu tiên nghe thấy khái niệm về Machine Learning tôi cũng không khỏi “hoang mang style” bởi cái thuật ngữ này và tôi biết có khá nhiều người mới bắt đầu cũng có cảm giác tương tự. Tôi cứ tưởng máy tính chỉ có thể bảo gì làm nấy thôi chứ sao có thể “học” được… Nếu các bạn cũng có những suy nghĩ như vậy thì bài viết này sẽ giải thích chi tiết cho bạn Làm thế nào máy có thể học và các bước cơ bản khi thực hiện một bài toán Machine Learning là như thế nào. OK chúng ta bắt đầu thôi

Vì sao máy tính có thể học

Có lẽ từ học không còn xa lạ gì đối với mỗi chúng ta nữa. Ngay từ khi sinh ra chúng ta đã phải học rất rất nhiều thứ như học ăn, học uống, học nói, học đọc, học viết… Nhớ lại những thời tôi đi học tôi thường sợ nhất là môn Lịch sử và không hiểu vì sao mà kiến thức lịch sử của tôi chỉ tồn tại trong đầu đúng từ tối hôm trước cho đến hết tiết Sử của ngày hôm sau, ngay sau khi cô giáo kiểm tra xong bài cũ là tôi cũng quên hết sạch. Rõ ràng đối với mỗi chúng ta người ta phân biệt hiện tượng học vẹt và sự thông minh thực sự. Và các bạn cũng sẽ thấy trong học máy cũng có những khái niệm như vậy.

vet-yeulaptrinh.pw

Machine Learning khác với if…else

Nếu bạn coi rằng người có trí nhớ tốt thì có khả năng học giỏi thì cũng có vẻ hợp lý vì với con người thì trí nhớ tốt đồng nghĩa với sự thông minh. Nhưng đừng nhầm lẫn với anh bạn máy tính nhé. Với những ổ SSD hàng Petabyte thì gần như trí nhớ của chúng là vô hạn tuy nhiên điều này chẳng liên quan gì đến việc một chiếc máy có thông minh thực sự hay không cả.

Hãy tưởng tượng bạn làm một chat bot nhắn tin cho người yêu bằng cách thu thập các đoạn hội thoại của các đôi tình nhân. Bộ nhớ của máy tính tầm vài TB đủ cho bạn lưu hàng tỉ cuộc hội thoại như thế. Tuy nhiên có hai hướng tiếp cận cho vấn đề này.

Cách 1

if Q in questions then print answer of Q else return Null

Cách này có nghĩa là bạn sẽ phải tìm kiếm chính xác câu hỏi của người hỏi trong tập dữ liệu và trả lời lại với answer tương ứng. Điều này chính là cách nghĩ cơ bản trong lập trình. Tuy nhiên nó hoàn toàn thất bại nếu như tập dữ liệu không đủ lớn, chưa kể rằng nó sẽ chẳng thể nào đem lại những cảm giác thú vị cho người dùng vì những câu trả lời bị lặp lại một cách nhàm chán. Giống y như việc mình học lịch sử hồi xưa vậy. Rõ ràng chiếc máy tính này đang học vẹt và không hề có một chút Machine Learning nào trong này cả. Một hệ thống chatbot thông minh sẽ không làm như thế.

Một hệ thống chatbot thông minh sẽ biết cách tự suy diễn xem với mỗi câu hỏi nào thì nên trả lời thế nào. Cũng giống như việc con người sẽ giải quyết được nhiều vấn đề hơn thông qua suy luận chứ không phải dựa trên sự học tủ, học vẹt nữa.

Cái máy nó học thế nào

Hãy tưởng tượng lại xem hồi bé chúng ta được bố mẹ dạy nhận biết đồ vật từ cái ca đến con bò con chó như thế nào. Ban đầu chúng ta còn ngập ngừng chưa biết được hết mặt các con vật nhưng sau đó chúng ta gặp lại càng nhiều lần thì không còn bỡ ngỡ nữa. Các trường mẫu giáo cũng hay sử dụng các Flash card để dạy trẻ con nhận biết đồ vật.

Mọi người thấy không, muốn học được một điều gì đó thì phải có người dạy và muốn máy có thể học thì chúng ta cũng cần phải dạy nó. Nhưng trước tiên muốn dạy được nó chúng ta cần phải có một tập dữ liệu, hiểu đơn giản giống như việc chúng ta phải có con bò, con chó thật hoặc có tranh ảnh về chúng thì mới có hi vọng dạy được đứa trẻ vậy. Khá dễ hiểu phải không bạn. Hãy nhớ rằng:

Không có dữ liệu thì sẽ không học được

Tuy nhiên việc có dữ liệu chuẩn rồi thì vấn đề tiếp theo đó chính là chọn một người thầy tốt. Rõ ràng rằng chúng ta sẽ không thể học được điều gì hay ho từ một ông thầy kém hiểu biết cả. Đối với máy cũng có những thầy giáo để dạy cho nó phải học cái gì từ tập dữ liệu của mình và những thầy giáo đó chính là các thuật toán học máy. Việc lựa chọn một ông thầy dạy cho con hay điều mà tôi muốn ám chỉ là việc lựa chọn một giải thuật tốt cho một bài toán học máy là một bước khá quan trọng. Có một lưu ý rằng:

Không phải cứ thuật toán phức tạp là hiệu quả sẽ cao

Việc lựa chọn thuật toán còn phụ thuộc vào bản thân của tập dữ liệu đối với những tập dữ liệu đơn giản, ít feature thì không cần phải training bằng một thuật toán quá phức tạp. Cũng giống như không ai lấy một giáo sư về Machine Learning để đi dạy trẻ con nhận biết đồ vật qua Flash card cả. Vậy nên trong Machine Learning không có khái niệm thuật toán này tốt, thuật toán kia không tốt. Mỗi thuật toán đều có cái ưu và nhược điểm riêng đối với từng tập dữ liệu. Việc áp dụng và phát huy nhó như thế nào là việc của mỗi chúng ta.

Machine Learning Workflow

Tôi đã thảo luận với các bạn cách dạy máy học như thế nào. Giờ tôi sẽ nói với các bạn về các bước thực hiện một bài toán Machine Learning. Tựu chung lại thì Machine Learning có thể được chia làm ba bước chính như sau:

  • Modeling: là bước mô hình hóa bài toán. Với mỗi một loại bài toán lại có một mô hình phù hợp như hồi quy hoặc phân lớp hoặc tuyến tính hoặc phi tuyến tính. Nhắc lại một lần nữa TÙY YÊU CẦU BÀI TOÁN. Sau bước này ta sẽ tìm ra được một số thuật toán phù hợp cho bước tiếp theo.
  • Learning: sau khi đã lựa chọn được thuật toán thì bước tiếp theo đó chính là bước học tức là sử dụng thuật toán đó để training trên tập dữ liệu đã cho. Sau bước này chúng ta thu được một bộ tham số được gọi là model
  • Predicting: sau khi có model chúng ta sử dụng nó để dự đoán các dữ liệu mới. Mọi người lưu ý rằng các dữ liệu mới này phải là các dữ liệu CHƯA ĐƯỢC TRAINING BAO GIỜ thì mới có thể sử dụng để đánh giá độ tốt của model thu được.

Đó là 3 bước chính, ngoài ra còn một số bước tiền xử lý dữ liệu được thực hiện giống như sơ đồ sau:

Nó có thể giải thích kĩ hơn như sau:

  • Từ người dùng ta thu thập được dữ liệu
  • Từ dữ liệu ta tiến hành tiền xử lý làm sạch dữ liệu
  • Sau khi tiền xử lý ta modeling lựa chọn giải thuật
  • Sau đó ta tiến hành tách dữ liệu thành hai tập traintest
  • Sau đó ta tiến hành thay đổi giải thuật cho đến khi có kết quả tốt nhất
  • Lựa chọn mô hình tốt nhất để trả lại feedback cho người dùng

Ví dụ minh họa

Chúng ta sẽ cùng tìm hiểu về các bước làm bài toán Machine Learning thông qua ví dụ minh họa cho bài toán phân loại hoa với ngôn ngữ Python. Và tôi cũng sẽ sử dụng Python làm ngôn ngữ chính cho tất cả các ví dụ trong blog này của tôi. Bây giờ chúng ta sẽ bắt đầu từng bước nhé

Giới thiệu bài toán

Dựa trên một tập dữ liệu về các đặc điểm của bông hoa, tôi sẽ sử dụng Machine Learning để dự đoán xem nó là loài hoa nào. Đây là một bài toán phân lớp hay trong tài liệu tiếng anh gọi là classification.

Tập dữ liệu

Do mục đích để minh họa nên tôi sử dụng một tập dữ liệu mẫu khá nổi tiếng cho bài toán này đó chính là tập dữ liệu hoa Iris

Tập dữ liệu này bao gồm 3 class tương ứng với số liệu của ba họ hoa iris được mô tả trong hình sau:

Chính vì tập dữ liệu đã được chuẩn hóa và được sử dụng nhiều cho mục đích nghiên cứu nên tôi bỏ qua bước tiền xử lý dữ liệu đối với tập dữ liệu này. Mặc dù trên thực tế thì quả thực là đời không như mơ. Thậm chí bước tiền xử lý dữ liệu là bước tốn nhiều thời gian và công sức nhất trong quá trính làm Machine Learning. Giờ đã xong bước tiền xử lý dữ liệu, chúng ta sẽ đến bước tiếp theo đó là lựa chọn thuật toán.

Lựa chọn thuật toán

Do bài toán này thuộc vào dạng classification nên chúng ta sẽ thử sử dụng một vài phương pháp thông dụng trong phân lớp như SVM hay Random Forest hay Naive Bayes hoặc cao siêu hơn một chút như Neural Network để áp dụng lên bài toán này. Giờ chúng ta sẽ tiến hành sử dụng Python để minh họa một số giải thuật nói trên

Minh họa bằng Python

Chúng ta đã định hướng trước sẽ sử dụng một số thuật toán trong classification để giải quyết bài toán phân loại hoa với bộ dữ liệu Iris. Bây giờ chúng ta sẽ học cách triên khai nó trên Python với bộ thư viên Sklearn vô cùng hữu ích. Trong bộ thư viện này bộ dữ liệu hoa iris đã được build-in sẵn rồi chúng ta chỉ việc lấy ra sử dụng thôi.

Đầu tiên là import nó vào

from sklearn.datasets import load_iris

Sau đó thì làm thế nào nhỉ. Chúng ta cùng thử xem nó hoạt động chưa bằng hàm main như sau:

if __name__ == "__main__":
    iris = load_iris()
    print "Size of data", iris.data.shape

Câu lệnh trên in ra kết quả là

Size of data (150, 4)

Có nghĩa là data của chúng ta bao gồm 150 bông hoa với 4 thuộc tính của mỗi bông hoa. Để in các class tương ứng với mỗi bông hoa chúng ta làm như sau:

print "Target", iris.target

Chúng ta sẽ thấy đươc các class tương ứng là [0, 1, 2] với ba loại hoa iris mô tả ở phần trên.

Bước tiếp theo chúng ta cần làm đó là tách tập dữ liệu thành hai phần trainingtesting. Chúng ta sử dụng thư viện train_test_split của sklearn như sau:

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2)

Đoạn code trên tách tập dữ liệu với ratio = 0.2 tức là 80% để training20% dùng để testing

Tiếp theo chúng ta sẽ áp dụng thử một thuật toán phân lớp đó là SVC với kernel tuyến tính thuộc bộ thư viện sklearn

from sklearn import svm
clf = svm.SVC(kernel='linear')
clf.fit(X_train, y_train)

Sau khi chạy xong đoạn code trên chúng ta đã lưu được một model sử dụng để dự đoán. Lưu ý là model này mới chỉ được sinh ra trên tập training. Chúng ta cần kiểm tra kết quả dự đoán với tập dữ liệu testing. Tôi hay sử dụng thư viện classification_report để in kết quả phân lớp. Xây dựng hàm in kêt quả như sau:

def evaluate_model(X_test, y_test):
    y_true, y_pred = y_test, clf.predict(X_test)
    print(classification_report(y_true, y_pred))

Và trong hàmmain chúng ta thêm vào đoạn code sau đoạn training như sau:

# Evaluate SVC
evaluate_model(X_test, y_test)

Tiến hành chạy thử model thu được kết quả:

Ở đây có hai chỉ số các bạn cân quan tâm đó chính là precisionrecall ta định nghĩa chúng như sau:

Precision bao nhiêu cái đúng được lấy ra

Một cách toán học thì

$$Precision=\frac{y_{true} \cap y_{selected}}{y_{selected}}$$

Recall bao nhiêu cái được lấy ra là đúng

Hay tức là

$$Recall=\frac{y_{true} \cap y_{selected}}{y_{true}}$$

Từ đó chỉ số thứ 3 ở trên f1-score được định nghĩa là:

$$2.\frac{Precision.Recall}{Precision+Recall}$$

Giờ chúng ta sẽ thử nghiệm mô hình với một số thuật toán khác trên cùng một tập dữ liệu để đánh giá được hiệu năng của từng thuật toán. Ở đây tôi sẽ so sánh với các thuật toán Random Forest, Naive Bayes còn về Neural Network xin hẹn các bạn một dịp sau.

Full Code

Các bạn có thể tham khảo Full code của bài viết này tại đây

Kết quả

Sau đây là kết quả chúng ta estimate sau khi training xong cả 3 model với cùng một tập dữ liệu

Chúng ta thấy rằng 3 model trên cùng một tập dữ liệu thì SVC cho kêt quả tốt nhất và Naive Bayes cho kết quả kém nhất. Bằng việc so sánh các phương pháp này chúng ta sẽ lựa chọn được model tốt hơn. Sau khi lựa chọn được model chúng ta sẽ lưu lại model tốt nhất để sử dụng cho lần sau.

Tổng kết

Qua bài viết này tôi đã cùng các bạn trao đổi về cách thực hiện một bài toán Machine Learning cơ bản. Rất hi vọng được các bạn ủng hộ để tôi có nhiều động lực viết thêm những chủ đề hay và bổ ích hơn.

Trân trọng

VKNIGHTS – spoj

Đề bài:


Thuật toán:


  • Quy hoạch động trạng thái

Code:


#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 200;
const int oo = (1 << 6) - 1;
 
int n, x, ans1, f[MAXN][oo+3], a[5][MAXN], z[MAXN];
ll ans2, t[MAXN][oo+3];
 
bool getbit(int state, int i) {
    return (state >> (6-i) ) & 1;
}
 
int tinh(int state) {
    int res = 0;
    FOR(i,1,6)
    if (getbit(state,i)) res++;
    return res;
}
 
int main() {
    	ios_base::sync_with_stdio(0); cin.tie(0);
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> n;
    FOR(i,1,n) {
        cin >> x;
        if (x) a[x][i] = 1;
    }
    FOR(i,1,3) {
        z[1] = z[1] * 2 + a[i][1];
    }
    FOR(i,2,n) {
        FOR(j,1,3) z[i] = z[i] * 2 + a[j][i-1];
        FOR(j,1,3) z[i] = z[i] * 2 + a[j][i];
    }
    f[0][0] = 0; t[0][0] = 1;
    FOR(j,0,(1<<3)-1)
    if ((z[1]&j)==0) {
        f[1][j] = tinh(j);
        t[1][j] = 1;
    }
    FOR(i,2,n) {
        FOR(state,0,oo)
        if ((z[i]&state)==0)
        FOR(j,0,oo)
        if ((z[i-2]&j)==0)
        if (t[i-2][j]>0)
        if ((i>3||(i==2&j==0))||(i==3&j<(1<<3)))
        {
            // check ma
            bool ok = 1;
            if (getbit(state,1)) {
                if (getbit(state,6)) ok = 0;
                if (getbit(j,6)) ok = 0;
                if (getbit(j,2)) ok = 0;
            }
            if (getbit(state,2)) {
                if (getbit(j,1)) ok = 0;
                if (getbit(j,3)) ok = 0;
            }
            if (getbit(state,3)) {
                if (getbit(state,4)) ok = 0;
                if (getbit(j,2)) ok = 0;
                if (getbit(j,4)) ok = 0;
            }
            if (getbit(state,4)) {
                if (getbit(state,3)) ok = 0;
                if (getbit(j,5)) ok = 0;
            }
            if (getbit(state,5)) {
                if (getbit(j,4)) ok = 0;
                if (getbit(j,6)) ok = 0;
            }
            if (getbit(state,6)) {
                if (getbit(j,5)) ok = 0;
                if (getbit(state,1)) ok = 0;
            }
            // qhd
            if (ok)
            if (f[i][state]<f[i-2][j]+tinh(state)) {
                f[i][state] = f[i-2][j] + tinh(state);
                t[i][state] = t[i-2][j];
            }
                else
            if (f[i][state]==f[i-2][j]+tinh(state)) {
                t[i][state] += t[i-2][j];
            }
        }
    }
    FOR(state,0,oo) ans1 = max(ans1,f[n][state]);
    FOR(state,0,oo)
    if (f[n][state]==ans1) ans2 += t[n][state];
    cout << ans1 << " " << ans2;
	return 0;
}

CROSS12 – spoj

Đề bài:


Thuật toán:


Đầu tiên ta cần tính thời gian qua cầu của mỗi người (khi đi một mình). Có thể tính bằng tham lam như cách được sử dụng trong code ở trên hoặc kết hợp quy hoạch động với deque để tìm min trên đoạn tịnh tiến.

Độ phức tạp khi tính là $O(m)$ cho mỗi người, vì $r$ chỉ dao động từ 1 đến 100 nên ta dùng một mảng phụ để cache giá trị đã tính lại.

Sau khi tính xong, gọi thời gian qua cầu của $n$ người là $A(n)$, ta sắp xếp $A$ tăng dần.

Gọi $F(i)$ là thời gian ít nhất để những người từ 1 đến i qua cầu, ta có công thức:

$ F(1) = A(1) \ F(2) = A(2) \ F(i) = min \begin{cases} F(i-2) + A(1) + 2A(2) + A(i) & \quad (1)\ F(i-1) + A(1) + A(i) & \quad (2)\ \end{cases} $

Trong trường hợp $(1)$, ta cho $A(2)$ quay về, sau đó $A(i)$ và $A(i-1)$ qua cầu, sau đó $A(1)$ từ bên kia cầu quay về, $A(1)$ và $A(2)$ cùng qua cầu.

Trong trường hợp $(2)$, $A(1)$ quay về sau đó cùng $A(i)$ qua cầu.

Code:


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int time(int r, int m, const char *bridge) {
    int i = 0, res = 1;
    while (i + r <= m) {
        res++;
        i += r;
        while (bridge[i] == '1') i--;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (auto &x: a) cin >> x;
    string bridge; cin >> bridge;
    bridge = '0' + bridge + '0';
    vector<int> cache(101, 0);
    for (auto &x: a) {
        if (!cache[x]) x = cache[x] = time(x, m, bridge.data());
        else x = cache[x];
    }
    sort(a.begin(), a.end());
    if (n == 1) cout << a[0];
    else if (n == 2) cout << a[1];
    else {
        int f0 = a[0], f1 = a[1];
        for (int i=2; i<n; i++) {
            int f2 = min(f0 + a[0] + 2*a[1] + a[i], f1 + a[0] + a[i]);
            f0 = f1, f1 = f2;
        }
        cout << f1;
    }
    return 0;
}

NKTICK – spoj

Đề bài:


Thuật toán:


  • Quy hoạch động

Code:


const   fi='';
        fo='';
        max=30000;
var n,i:longint;
t:array[1..60000] of integer;
f:array[-1..60000] of longint;
r:array[0..59999] of integer;
w:text;
function min(x,y:longint):longint;
begin
    if x>y then min:=y else min:=x;
end;
procedure nhap;
begin
    assign(w,fi);
    reset(w);
    readln(w,n);
    for i:=1 to n do read(w,t[i]);
    for i:=1 to n-1 do read(w,r[i]);
    close(w);
end;
procedure xuly;
begin
        f[0]:=0; f[-1]:=0; r[0]:=max;
        for i:=1 to n do
        f[i]:=min(f[i-1]+t[i],f[i-2]+r[i-1]);
end;
procedure inkq;
begin
        assign(w,fo);
        rewrite(w);
        writeln(w,f[n]);
        close(w);
end;
begin
    nhap;
    xuly;
    inkq;
end.

P152SUMI – ptit

Đề bài:


Thuật toán:


Tạo một mảng quy hoạch có dạng
xau[i]==xau[i+1]? arr[i+1]=arr[i]+1 : arr[i+1]=arr[i];
với arr[0]=0;
VD: #..###
ta có;
arr[0] = 0;
arr[1] = 0; (#.)
arr[2] = 1; #(..)
arr[3] = 1; #.(.#)
arr[4] = 2; #..(##)
arr[5] = 3; #..#(##)

arr[i+1] = số cặp kí tự giống nhau từ xâu[0 -> i];
-> Với mỗi truy vấn ta có:
Số cặp giống nhau từ l->r = arr[r-1] – arr[l-1];

Code:


#include <iostream>
#include <string>
using namespace std;
 
int main ()
{
	string xau;
	cin>>xau;
	int arr[100005];
	arr[0]=0;
	for (int i=0; i<xau.size()-1; i++)
	{
		if (xau[i]==xau[i+1])
			arr[i+1]=arr[i]+1;
		else
			arr[i+1]=arr[i];
	}
	int m;
	cin>>m;
	for (int i=1; i<=m; i++)
	{
		int l, r;
		cin>>l>>r;
		cout<<arr[r-1]-arr[l-1]<<endl;
	}
	return 0;
}

NKPATH – spoj

Đề bài:


Thuật toán:


Với mỗi ô (i,j) với  $i=1..m; j=1..n-1;$ kiểm tra xem ô (ii,jj) với $ii=1..i-1; jj=1..j;$ có đi được đến ô (i,j) không

  • Nếu có
    l[i,j]:=(l[i,j]+l[ii,jj]) mod base;
    

Kết quả: $\sum_{i=1}^{m}L[i][n]$

Code:


const   fi='';
        fo='';
        maxn=100;
        base=1000000000;
type    arra=array[1..maxn,1..maxn] of integer;
        arrl=array[1..maxn,1..maxn] of longint;
var     a:arra;
        i,j,m,n:byte;
        l:arrl;
        f:text;
        res:int64;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,m,n);
    for i:=1 to m do
        for j:=1 to n do read(f,a[i,j]);
    close(f);
end;
procedure init;
begin
    for i:=1 to m do l[i,1]:=1;
 
    res:=0;
end;
function kt(x,y:longint):boolean;
var     tmp:longint;
begin
        while y>0 do
        begin
            x:=x mod y;
            tmp:=x;
            x:=y;
            y:=tmp;
        end;
        if x=1 then exit(false) else exit(true);
end;
procedure xuly;
var     ii,jj:byte;
begin
    for i:=1 to m do
        for j:=1 to n-1 do
        begin
            for ii:=i-1 downto 1 do
                for jj:=j downto 1 do
                        if kt(a[i,j],a[ii,jj]) then l[i,j]:=(l[i,j]+l[ii,jj]) mod base;
            for jj:=j-1 downto 1 do
                if kt(a[i,j],a[i,jj]) then l[i,j]:=(l[i,j]+l[i,jj]) mod base;
        end;
 
    for i:=1 to m do
        for ii:=i downto 1 do
                for jj:=n-1 downto 1 do
                if kt(a[i,n],a[ii,jj]) then res:=(res+l[ii,jj]) mod base;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    init;
    xuly;
    xuat;
end.

C11BC1 – spoj

Đề bài:


Thuật toán:


  • (đang cập nhập)

Code:


uses math;
const
  fi='';
  fo='';
  maxn=trunc(1e5);
  maxk=50;
  base=790972;
var
  f : array[0..maxn,0..maxk] of int64;
  i,j,n,k,m : longint;
  kq : int64;
  a,b : array[1..maxn] of longint;
procedure enter;
begin
  assign(input,fi);reset(input);
  readln(n,k);
  for i:=1 to n do read(a[i],b[i]);
  close(input);
end;
procedure swap(var x,y: longint);
var tg : longint;
begin
  tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r : longint);
  var i,j,x : longint;
  begin
    i:=l;j:=r;
    x:=b[(l+r) div 2];
    repeat
      while x>b[i] do inc(i);
      while x<b[j] do dec(j);
      if i<=j then
        begin
          swap(b[i],b[j]);
          swap(a[i],a[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs(i,r);
    if j>l then qs(l,j);
  end;
function muk(x : longint) : int64;
  var i : longint;
  begin
    muk := 1;
    for i:=1 to k do muk:=muk*x;
  end;
function cnk(n,k : longint) : int64;
  begin
    cnk := 1;
    for i:=n-k+1 to n do cnk := cnk*i;
    for i:=1 to k do cnk := cnk div i;
  end;
function tinh : int64;
begin
  fillchar(f,sizeof(f),0);
  for i:=0 to m do f[i,0] := 1;
  for i:=1 to m do
    for j:=1 to min(k,i) do
      f[i,j] := (f[i-1,j] + f[i-1,j-1]*a[i]) mod base;
  exit(f[m,k]);
end;
procedure process;
var i,j,dem : longint;
    dau,cuoi : longint;
begin
  qs(1,n);
  m := n;
  kq := tinh;
  dau := 1;
  while (dau<=n) do
  begin
    cuoi := dau+1;
    m := 1; a[1] := a[dau];
    while (cuoi<=n) and (b[cuoi]=b[dau]) do
      begin
        m := m+1;
        a[m] := a[cuoi];
        inc(cuoi);
      end;
    if cuoi-dau>=k then
      kq := (kq - tinh + base + base) mod base;
    dau := cuoi;
  end;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(kq);
  close(output);
end;
begin
  enter;
  process;
  print;
end.