CF 1561

CF 1561 D. Up the Strip 是 Codeforces 网站上的一道算法题目，题目要求从一个格子跳到另一个格子，有两种跳跃方式：一种是减法跳跃，即选择一个数 ( k ) 使得 ( k \in [1, n) )，从 ( n ) 跳到 ( n-k )；另一种是除法跳跃，即选择一个数 ( k ) 使得 ( k \in (1, n] )，从 ( n ) 跳到 ( \lfloor \frac{n}{k} \rfloor )。题目要求计算从 ( n ) 号格子跳到 ( 1 ) 号格子的方案数，并且答案需要对给定的模数取模。

这个问题可以通过动态规划（DP）来解决。根据题目描述，可以设置状态 ( dp[i][j] ) 表示从 ( i ) 号格子出发，使用第 ( j ) 种跳跃方式的方案数。转移方程如下：

1. ( dp[i][1] = \sum_{j=1}^{i-1} (dp[j][1] + dp[j][2]) )，表示使用减法跳跃。
2. ( dp[i][2] = \sum_{j=2}^i (dp[\lfloor \frac{i}{j} \rfloor][1] + dp[\lfloor \frac{i}{j} \rfloor][2]) )，表示使用除法跳跃。

最终的答案为 ( dp[n][1] + dp[n][2] )。为了优化计算，可以使用数论分块的方法来减少时间复杂度，最终的时间复杂度可以达到 ( O(n \sqrt{n}) ) 。

#include <stdio.h>
typedef long long ll;
ll dp[200007][7], sum[200007][7];
int main(){
   
    int n, m;
    scanf("%d %d", &n, &m);
    for (register int i = 2; i <= n; i++){
   
        int half_i = i / 2;
        dp[i][1] = (sum[i - 1][1] + sum[i - 1][2] + 1) % m;
        dp[i][2] = i - half_i;
        for (register int j = 2, k; j <= half_i; j = k + 1){
   
            int ti = i / j;
            k = i / ti;
            dp[i][2] = (dp[i][2] + (dp[ti][1] + dp[ti][2]) * (k - j + 1) % m) % m;
        }
        sum[i][1] = (sum[i - 1][1] + dp[i][1]) % m;
        sum[i][2] = (sum[i - 1][2] + dp[i][2]) % m;
    }
    printf("%lld", (dp[n][1] + dp[n][2]) % m);
    return 0;
}