Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Automat & NN hình thức] Đếm số chuỗi độ dài n được chấp nhận

    Cho DFA M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F)M=(Q,Σ,δ,q0​,F) và số nguyên nnn. Hãy đếm số chuỗi w∈Σnw\in\Sigma^nw∈Σn (độ dài đúng nnn) mà MMM chấp nhận.

    Hình thức: tính ∣{w∈Σn:δ^(q0,w)∈F}∣\big|\{w\in\Sigma^n : \hat\delta(q_0,w)\in F\}\big|​{w∈Σn:δ^(q0​,w)∈F}​. Dùng quy hoạch động dpk[s]dp_k[s]dpk​[s] = số chuỗi độ dài kkk đưa DFA từ q0q_0q0​ tới trạng thái sss.

    Ví dụ: DFA chấp nhận chuỗi có số 111 chẵn, với n=2n=2n=2 có 222 chuỗi (00, 11).

    • Định dạng đầu vào:

      Dòng 1: số nguyên QQQ — số trạng thái (đánh số 0..Q−10..Q-10..Q−1). Dòng 2: các ký tự bảng chữ cái Σ\SigmaΣ, phân tách bởi dấu cách. Dòng 3: trạng thái bắt đầu q0q_0q0​. Dòng 4: số trạng thái chấp nhận FFF rồi danh sách các trạng thái chấp nhận (cùng dòng, cách nhau dấu cách). Tiếp theo Q×∣Σ∣Q\times|\Sigma|Q×∣Σ∣ dòng, mỗi dòng p a q nghĩa là δ(p,a)=q\delta(p,a)=qδ(p,a)=q. Dòng cuối: số nguyên nnn.

    • Ràng buộc đầu vào:

      1≤Q≤1001 \le Q \le 1001≤Q≤100, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26, 0≤n≤10000 \le n \le 10000≤n≤1000. Kết quả có thể rất lớn.

    • Định dạng đầu ra:

      In một số nguyên: số chuỗi độ dài nnn được chấp nhận.

    Ví dụ:

    Đầu vào:

    2
0 1
0
1 0
0 0 0
0 1 1
1 0 1
1 1 0
2

    Đầu ra:

    2

    Giải thích:

    Chuỗi độ dài 2 có số 1 chẵn: '00' và '11' -> đáp án 2.

    Đang tải editor...