火车从始发站称为第 1 站开出在始发站上车的人数为 a然后到达第 2 站在第 2 站有人上、下车但上、下车的人数相同因此在第 2 站开出时即在到达第 3 站之前车上的人数保持为 a 人。从第 3 站起包括第 3 站上、下车的人数有一定规律上车的人数都是前两站上车人数之和而下车人数等于上一站上车人数一直到终点站的前一站第 n−1 站都满足此规律。现给出的条件是共有 n 个车站始发站上车的人数为 a最后一站下车的人数是 m全部下车。试问 x 站开出时车上的人数是多少输入格式输入只有一行四个整数分别表示始发站上车人数 a车站数 n终点站下车人数 m 和所求的站点编号 x。输出格式输出一行一个整数表示答案从 x 站开出时车上的人数。输入输出样例输入 #1复制5 7 32 4输出 #1复制13说明/提示对于全部的测试点保证 1≤a≤201≤x≤n≤201≤m≤2×104。NOIP1998 提高组 第一题这题推导就简单多了车站总数n第 n 站是终点站。 fₖ第 k 站上车人数 条件 f₁ a 设第 2 站上车人数为 t即 f₂ t第 2 站下车人数也是 t驶出 2 站人数 P₂a k≥3上车人数 fₖfₖ₋₁fₖ₋₂序列 f₁af₂tf₃atf₄a2tf₅2a3tf₆3a5t……下车规则到达第 k (k≥3) 站时下车人数 fₖ₋₁ Pₖ第 k 站开出时车上人数 递推 Pₖ Pₖ₋₁−fₖ₋₁fₖ 带入 fₖfₖ₋₁fₖ₋₂ PₖPₖ₋₁fₖ₋₂ (k≥3)初始 P₁a P₂a逐项展开 P₃P₂f₁aa2a P₄P₃f₂2at P₅P₄f₃2atat3a2t P₆P₅f₄3a2ta2t4a4t P₇P₆f₅4a4t2a3t6a7t边界条件终点站所有人下车 → 第 n−1 站开出人数 Pₙ₋₁m 也就是 Pₙ₋₁A・aB・tm A、B 是只由 n 决定的整数可以递推求出解得 t(m−Aa)/B要求第 x 站开出人数PₓC・aD・t C、D 是只由 x 决定的整数。合并成一条式子 PₓCaD×(m−Aa)/B所以只需要求出系数然后推导出t自然就出答案了上代码#includebits/stdc.husing namespace std;typedef long long ll;ll const MAXN200005;ll c[MAXN];ll d[MAXN];ll A[MAXN];ll B[MAXN];int main(){ll a,n,m,x;cinanmx;c[1]1,d[1]0;c[2]0,d[2]1;for(ll i3;in;i){c[i]c[i-1]c[i-2];d[i]d[i-1]d[i-2];}A[1]1,B[1]0;A[2]1,B[2]0;for(ll i3;in-1;i){A[i]A[i-1]c[i-2];B[i]B[i-1]d[i-2];}ll ans;if(B[n-1]0){//注意边界问题 当n3时除以会报警所以处理特殊情况ansa;}else{ll t(m-A[n-1]*a)/B[n-1];ansA[x]*aB[x]*t;}coutans;return 0;}
