1 solutions

  • 0
    @ 2026-10-22 18:20:38

    C :

    #include<stdio.h>
    #include<stdlib.h>
    
    
    int getPathCount(int allStair, int maxStep) {
    	int* reachStair = (int*)malloc(sizeof(int) * allStair + 1);
    	reachStair[0] = 1;
    
    
    	for (int i = 1; i <= allStair; i++) {
    		reachStair[i] = 0;
    
    		for (int j = 1; j <= maxStep; j++) {
    			if (i - j >= 0) {
    				reachStair[i] += reachStair[i - j];
    			}
    		}
    		reachStair[i] %= 100003;
    	}
    
    
    	int paths = reachStair[allStair];
    
    	free(reachStair);
    
    	return paths;
    }
    
    
    
    int main() {
    
    	int A = 0;
    	int B = 0;
    
    	scanf("%d", &A);
    	scanf("%d", &B);
    
    	int paths = getPathCount(A, B);
    
    	printf("%d", paths);
    
    
    	return 0;
    }
    

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e6 + 10;
    const int mod=100003;
    #define int long long
    #define endl '\n' 
    typedef pair<int,int> PII;
    int dp[N];
    
    void solve()
    {
        int n , k;
        cin >> n >> k;
    
        dp[0] = dp[1] = 1;
    
        for(int i = 2;i <= n;i ++)
    	{
    		for(int j = 1;j <= k;j ++)
    		{
    			if(i >= j)
    			{
    				dp[i] = (dp[i] + dp[i-j]) % mod;
    			}
    		}
    	}
    	cout<<dp[n] % mod;
    }
    
    signed main()
    {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
        int xiao_p;
        xiao_p = 1;
    
        while(xiao_p --)
        {
            solve();
        }
    
        return 0;
    }
    

    Java :

    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc  = new Scanner(System.in);
            int A = sc .nextInt();
            int B = sc .nextInt();
    
    
            long[] dp = new long[A + 1];
            dp[0] = 1;
    
    
            for (int i = 1; i <= A; i++) {
                for (int j = 1; j <= B && j <= i; j++) {
                    dp[i] += dp[i - j];
                }
            }
    
    
            System.out.println(dp[A]%100003);
        }
    }
    
    

    Python :

    # coding=utf-8
    def count_ways(A, B):
        MOD = 100003
        dp = [0] * (A + 1)
        dp[0] = 1 
        for i in range(1, A + 1):
            dp[i] = sum(dp[max(0, i - B):i]) % MOD
        return dp[A]
    A, B = map(int, input().split())
    print(count_ways(A, B))
    
    • 1

    Information

    ID
    348
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    (None)
    # Submissions
    0
    Accepted
    0
    Uploaded By