Up the Strip

题意

你现在在 \(n\) 号格子，你需要跳到 \(1\) 号格子，你可以有两种跳法：

你可以做减法，即选择一个数 \(k\in [1,n)\) ，从 \(n\) 跳到 \(n-k\)
你可以做除法，即选择一个数 \(k\in(1,n]\)，从 \(n\) 跳到 \(\lfloor\frac{n}{k}\rfloor\)

问你有多少种跳法，答案对给定模数取模。

题解

经典 \(dp\)。

很容易想到对做减法的部分求前缀和，对做除法的部分做整除分块。然而分块的复杂度是 \(\sqrt{n}\) 级别的，过不了 \(D2\) , 于是考虑优化。前缀和部分不能优化不了了，现优化整除分块。

经典套路：普通复杂度做法做不了就考虑算贡献。我们现在想知道，对于一个数 \(n\) ，他在除以 \(k\in(1,n]\) 里的数时，除出来的数分别出现了多少次。例如 \(10\) ，

9	8	7	6	5	4	3	2	10
1	1	1	1	2	2	3	5	1

可以看到 \(1\) 出现了五次， \(2\) 出现了两次，\(3,5\) 分别出现了一次。我尝试用公式来表达，对于一个数 \(i\) ，他出现的次数为 \(\frac{n}{i}-\frac{n}{i+1}\)（易证）。于是 \(dp\) 的式子就可以写成

\[f_n=\sum_{i=1}^{n-1}f_i+\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}f_i \times (\lfloor \frac{n}{i} \rfloor-\lfloor \frac{n}{i+1} \rfloor)
\]

第一部分可以用前缀和优化掉，第二部分怎么优化呢？单独考察 \(f_i\times \lfloor \frac{n}{i} \rfloor\) ，可以知道 \(n\) 只有在 \(i,2i,3i,...\) 的时候才会发生变化，于是我们考虑差分，开个数组 \(g\) 来存这个差分，更新到 \(f_i\) 时，我们就把 \(g_i,g_{2i},...\) 更新了。\(f_i\times \lfloor \frac{n}{i+1}\rfloor\) 同理。

AC代码

#include <bits/stdc++.h>

#define IO ios::sync_with_stdio(NULL)

#define sc(z) scanf("%lld", &(z))

#define _ff(i, a, b) for (int i = a; i <= b; ++i)

#define _rr(i, a, b) for (int i = b; i >= a; --i)

#define _f(i, a, b) for (int i = a; i < b; ++i)

#define _r(i, a, b) for (int i = b - 1; i >= a; --i)

#define mkp make_pair

#define endl "\n"

#define pii pair<int,int>

#define fi first

#define se second

#define lowbit(x) x&(-x)

#define pb push_back

using namespace std;

typedef double db;

typedef long long ll;

typedef long double ld;

const int N = 4e6 + 5;

const ll M = 1e5 + 5;

const ll mod = 998244353;

const int inf = 1e9;

const double eps = 1e-9;

const double PI = acos(-1.0);

const pii NIL = {0,0};

ll f[N],g[N];

void solve() {

    ll sum=0,sum2=0;f[1]=1;

    ll n,p;cin>>n>>p;

    _ff(i,1,n){

        f[i]=(f[i]+((sum+sum2)%p+g[i])%p)%p;

        for(int j=i;j<=n;j+=i)g[j]=(g[j]+f[i])%p;

        for(int j=i+1;j<=n;j+=i+1)g[j]=(g[j]-f[i]+p)%p;

        sum=(sum+f[i])%p;

        sum2=(sum2+g[i])%p;

    }

    cout<<f[n]<<endl;

}

int main() {

    IO;

    #ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    #endif // !ONLINE_JUDGE

    // ll T; cin>>T;

    // _f(i,0,T) {

    //     // cout<<"Case "<<i+1<<": ";

    //     solve();

    // }

    solve();

    return 0;

}

巴特西

CF1561D Up the Strip

Up the Strip

题意

题解

AC代码

最新文章

热门文章