Đếm số cách đi hết cầu thang

[Tuan_Cris (tạch C++)]

mọi người giúp e câu này với ạ,code e làm gửi lên spoj sai,e cũng ko biết sai đâu
link code của e: https://ideone.com/syiAed
link đề spoj: https://vn.spoj.com/PTIT/problems/SSAM219A/

[Grevyalres_X (Pzanitor)]

Thuật như kia đảm bảo không chạy qua được Time limit.

[Tuan_Cris (tạch C++)]

a làm cho e xem với đc ko

[rogp10]

Số đã bị tràn vì bạn không modulo cả số đó nên nó cứ thêm vào thôi. Đúng ra thì nó kiểu ntn:

x = (x + t) % modulo;

Bài này có một cách pass là bù trừ (O(N)).

[Tuan_Cris (tạch C++)]

bù trừ như thế nào vậy anh

[rogp10]

Bạn viết hệ thức của F(n) và F(n+1), rồi rút ra kết luận

[Pham_Ngoc (Phạm Ngọc)]

Hi tạch C++.
Bạn hoàn toàn có thể tìm lời giải trên mạng. Mình thì chưa nghĩ ra nhưng một hướng là bạn chia N bậc thành 2 doạn (thường cầu thang có chiếu nghỉ). Sau đó tìm số cách đi trên mỗi đoạn rồi nhân lại với nhau nó sẽ giúp giảm số tổ hợp cần phải tính xuống.
CM: Giả sử chia N thành 2 đoạn và sau đó sẽ tìm được 3 cách đi cho đoạn thứ nhất là a, b, c và đoạn 2 là a’, b’ vậy sẽ có 6 cách đi là aa’, ab’, ba’, bb’, ca’, ab’ nhưng sẽ chỉ phải tìm 5 cách đi trên các đoạn nhỏ hơn chi phí tính toán sẽ ít hơn so với việc tìm 6 cách đi trên cả đoạn N. Cứ chia như vậy khi có các đoạn nhỏ hơn K thì thuật toán sẽ đạn giới hạn tối ưu.
P/S Đây chỉ là đoán mò thôi.

[phamvandung]

Không biết phiên bản này (đã bỏ phần quy hoạch động) có đúng không nhỉ :V

function count(n, k):

if n <= 1 {
    return 1;
}
let ways = 0;
for i from 1 to min(n, k) + 1 {
    ways += count(n - i, k);
}
return way%MOD

[Grevyalres_X (Pzanitor)]

Bài này đơn giản giải bằng QHĐ. tính trước mọi trường hợp f[n][k], lưu vào một mảng và xuất ra khi dùng.
Cách làm tối ưu hơn về bộ nhớ là dùng nhân ma trận. https://vnoi.info/wiki/algo/trick/matrix-multiplication

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 1;
const int K = 101;
const int M = 1e9 + 7;
int f[N][K];
int main() {
	f[0][0] = 1;
	for (int i = 1; i < N; ++i) f[i][0] = 0;
	for (int j = 1; j < K; ++j) {
		int ans = 1;
		f[0][j] = 1;
		for (int i = 1; i < j; ++i) {
			f[i][j] = ans;
			ans = (ans + f[i][j]) % M;
		}
		for (int i = j; i < N; ++i) {
			f[i][j] = ans;
			ans = (ans - f[i - j][j] + M) % M;
			ans = (ans + f[i][j]) % M;
		}
	}
	int t; cin >> t;
	while (t--) {
		int n, k; cin >> n >> k;
		cout << f[n][k] << '\n';
	}
	return 0;
}

[rogp10]

Code này chưa tối ưu mem

[Tuan_Cris (tạch C++)]

a cho e xem code tối ưu mà a làm đc ko ạ

[rogp10]

đây bạn

# pseudo

# bạn có thể dùng mảng 100 slot, cái này là demo thôi.
CirBuff = Class.new do
  attr_reader :cap
  def initialize(cap, buff = null):
   :cap = cap
   :words = buff ||= Array.new(:cap)
   :front = :rear = 0
  end
  def adjust(stuff): stuff if stuff+=1 < :cap else 0 end
  def front(): :words[:front]; end
  def back(): :words[:rear]; end
  def push(thing): :words[adjust :rear] = thing end
  def pop(): t = words[:front]; :front = adjust :front; t end
  def full?(): adjust(:rear) == :front; end
  def empty?(): :front == :rear; end
end

t = gets.chomp.to_i
a = Array.new(100)
t.times do
  n, k = gets.chomp.split.map(&:to_i)
  buff = CirBuff.new(k,a)
  tmp = 1
  buff.push(1)
  (k-1).times { buff.push (tmp = (tmp*2) % 1000000007) }
  (n-k).times { buff.push (2*buff.back() - buff.pop()) % 1000000007 }
  puts buff.back
end

[noz1995 (Trần Hoàn)]

long countWay(int N, int K, long[] listSolved)
{
    if(listSolved[N] > 0)
        return listSolved[N];
    if(N <= 1)
    {
        listSolved[N] = 1;
        return 1;
    }
    if(K > N)
        K = N;
    long count = 0;
    for(int i = 1; i <= K; i += 1)
        count += countWay(N - i, K);
    listSolved[N] = count;
    return count;
}

[Tuan_Cris (tạch C++)]

e chịu thôi nhìn ko hiểu gì ạ

[tntxtnt]

k=2 thì đây là dãy Fibonacci mà :V
k=3 thì là Tribonacci :V
k > 3 thì chắc là k-bonacci :V định nghĩa

• F(0,k) = 0
• F(1,k) = 1
• F(n,k) = F(n-1,k) + F(n-2,k) + … + F(1,k) + F(0,k) với n < k
• F(n,k) = F(n-1,k) + F(n-2,k) + … + F(n-k+1,k) + F(n-k,k) với n >= k

tính ko cần đệ quy cũng được :V Làm 1 mảng n hay n+1 phần tử rồi tính như tính dãy Fibonacci thôi :V

vector<int64_t> a(n+1); // int 64-bit cho khỏi tràn số khi cộng dồn a[0]..a[i-1]
a[1] = 1;
for (int i = 2; i <= n; ++i) {
    for (int j = 1; i >= j; ++j) a[i] += a[i - j];
    a[i] %= MOD; // cộng dồn xong thì lấy mod
}
return a[n];

thời gian chạy là O(kn), tốn O(n) bộ nhớ :V Nhân thêm t nữa thì cả bài tốn O(knt) ~ 1 tỷ chắc chạy vừa kịp :V :V

tiết kiệm dòng hơn với std::accumulate :V

vector<int64_t> a(n+1);
a[1] = 1;
for (int i = 2; i <= n; ++i)
    a[i] = accumulate(&a[max(0, i - k)], &a[i], 0LL) % MOD;
return a[n];

[rogp10]

Cái CirBuff đó là mảng vòng (dùng như hàng đợi) O(k) mem.

[Grevyalres_X (Pzanitor)]

Muốn tối ưu thêm mem thì xử lí từng test case với đpt O(n) mỗi test, ý tưởng vẫn như cũ. Mem O(k) mỗi test.

[907pqv (Violet)]

typedef long long ll;
const ll MOD = 1e9 + 7;

ll climbstair(int n, int k)
{
    vector<ll> result;
    result.push_back(1);
    ll sum = 0;
    for (int i = 1; i <= k; ++i)
    {
        sum = (sum + result.back()) % MOD;
        result.push_back(sum);
    }

    if (n <= k)
        return result[n];
    for (int i = k + 1; i <= n; ++i)
    {
        // Sliding window để tính tổng k phần tử phía trước
        result.push_back((2 * result.back() % MOD - result[i - k - 1] % MOD + MOD) % MOD);
    }
    return result.back();
}

O(T*max(N,K))