add abc401c.rs

rchaser53 · rchaser53 · commit 768decacfac0 · 2025-04-15T21:22:37.000+09:00
diff --git a/src/abc/abc401c.rs b/src/abc/abc401c.rs
@@ -0,0 +1,32 @@
+/** THIS IS AN OUTPUT FILE. NOT EDIT THIS FILE DIRECTLY. **/
+use proconio::input;
+use proconio::marker::*;
+use std::marker::PhantomData;
+use std::cmp::*;
+use std::collections::*;
+
+fn main() {
+  input! {
+    n:usize,
+    k:usize
+  }
+
+  let MOD = 1000000000usize;
+  let mut v = vec![0;n+1];
+  let t = if n+1 < k { n + 1 } else { k };
+  for i in 0..t {
+    v[i] = 1;
+  }
+
+  let mut s = 0;
+  for i in 0..t {
+    s = (s+v[i]) % MOD;
+  }
+
+  for i in k..=n {
+    v[i] = s;
+    s = (s+v[i]+MOD - v[i-k]) % MOD;
+  }
+
+  println!("{}", v[n]);
+}
