1 solutions
-
0
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