A. run --- 牛客2018多校（dp）

2022-11-28 57

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 笔记

A. run — 牛客2018多校

题意

白云每秒可以走 1步或跑 k 步，但是不能连续跑 2 次及以上，q个询问，从 l - r 可能有多少种到达的方案，

思路

dp[i][j] i ∈ [ 1 , 100000 ] , j ∈ { 0 , 1 } 表示到第 i 米的最后一步是走的 (0) 还是跑的 (1)的所有方案数。

那么转移方程为

dp[i][0] = dp[i - 1][0] + dp[i - 1][1] 表示如果到第 i 米的最后一步是走的，那么肯定是从 i - 1 米走过来，那么到第 i - 1 米有两种方式 ——走的或者跑的

dp[i][1] = dp[i - k][0] 如果到第 i 米是跑的，那么一定是从 i - k 跑的，那么到第 i - k 米就只能是走的

题目要求出白云从0移动 L - R 米的所有可能情况，而不是白云从 L 移动到 R的所有可能情况。

所以答案为 sum[r] - sum[l - 1] 而不是 dp[r][0] + dp[r][1] - dp[l - 1][0] - dp[l - 1][1]

代码

#include<bits/stdc++.h>
#include<unordered_map>
#pragma GCC optimize(2)
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
//template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 50010;
int q, k;
int dp[100010][2]; // 第一维距离 第二位表示 跑/走
int sum[100010];
void solve() {
    cin >> q >> k;
    dp[0][0] = 1;
    for (int i = 1; i <= 100000; ++i) {
        dp[i][0] = (dp[i][0] + dp[i - 1][0] + dp[i - 1][1]) % mod;
        if (i >= k)dp[i][1] = (dp[i][1] + dp[i - k][0]) % mod;
        sum[i] = (sum[i - 1] + dp[i][0] + dp[i][1]) % mod;
    }
    while (q--) {
        int l, r; cin >> l >> r;
        cout << (sum[r] - sum[l - 1] + mod) % mod << endl;
    }
}
signed main() {
    // int _; cin >> _;
    // while (_--)
    solve();
    return 0;
}