[算法刷题题解笔记] 洛谷 P1011 [NOIP1998 提高组] 车站 [数学|斐波那契|推导]

// package luogu.orange;
import java.io.*;
/**
 * ClassName: P1011
 * Package: luogu.orange
 * Description:
 *
 * @Author tcw
 * @Create 2023-06-08 23:44
 * @Version 1.0
 */
public class Main {
    // 快读快写
    private static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) {
        // 始发站上车人数
        int a = readInt();
        // 车站数
        int n = readInt();
        // 终点站下车人数
        int m = readInt();
        // 所求站点编号
        int xi = readInt();
        // 根据推导，m = k1a + k2x
        // 其中k1 k2为a和x前的系数，a为始发站上车人数
        // x为第二站的上下车人数，m为终点站下车人数
        // k1_i = k1_(i-1) + k1_(i-2) - 1 从第四站开始为前两站系数之和-1
        // k2_i = k2_(i-1) + k2_(i-2) + 1 从第四站开始为前两站系数之和+1
        // 存储系数
        int[] k1 = new int[n];
        int[] k2 = new int[n];
        // 求解推导出的公式系数，并求解x
        // 由于最后一站下车人数等于前一站上下车后车上人数（最后一站全部下）
        for (int i = 1; i <= n - 1; i++) {
            if (i == 1) {
                k1[i] = 1;
                k2[i] = 0;
            } else if (i == 2) {
                k1[i] = 1;
                k2[i] = 0;
            } else if (i == 3) {
                k1[i] = 2;
                k2[i] = 0;
            } else {
                k1[i] = k1[i - 1] + k1[i - 2] - 1;
                k2[i] = k2[i - 1] + k2[i - 2] + 1;
            }
            // out.println(k1[i] +" " + k2[i]);
        }
        // 根据推导公式 m = k1a + k2x 求解x
        int x = (m - k1[n - 1] * a) / k2[n - 1];
        // 计算输出所求站点xi出发时的车上人数
        out.print(k1[xi] * a + k2[xi] * x);
        out.flush();
    }
    private static int readInt() {
        int in = 0;
        try {
            st.nextToken();
            in = (int) st.nval;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return in;
    }
}