题解：P10259 [COCI 2023/2024 #5] Piratski kod

· · 题解

思路分析

一看就差不多知道是 O(n^2) 的 DP 了。接下来就是去推一下转移式一类的东西。

首先，一个很自然的想法是令 dp_i 表示最后一段数字的海盗表示在 i 位置结束时的所有可能的正整数序列的和之和，并用 cnt_i 表示对应的不同的正整数序列的个数。

思考转移。显然 dp_i=\sum_{j<i}(dp_j\times a_{i-j}+cnt_j\times b_{i-j}),cnt_i=\sum_{j<i}(cnt_j\times a_{i-j})。其中 a,b 是转移系数。

我们思考一下这些转移系数是什么。对应到 dp 和 cnt 的状态设计上，显然 a_i 表示的是长度为 i 的单个数字的海盗表示的方案数，而 b_i 则表示的是这些数字的海盗表示的原数字之和。

于是现在我们思考怎么快速的求出 a_i,b_i。我们发现我们可以再进行一次 DP。具体的来说，我们令 c_{i,0/1} 表示长度为 i 的，最后一个数字为 0/1 的还没有结束的数字的海盗表示方案数，令 v_{i,0/1} 表示这些数字的海盗表示的原数字之和。

那么显然，只有在一个末尾为 1 的数字的海盗表示后面再加上一个 1 表示终止，才形成了一个完整的数字的海盗表示。于是 a_i=c_{i-1,1},b_i=v_{i-1,1}。

考虑 c,v 的转移式。非常显然，c_{i,1}=c_{i-1,0},c_{i,0}=c_{i-1,0}+c_{i-1,1},v_{i,0}=v_{i-1,1}+v_{i-1,0},v_{i,1}=v_{i-1,0}+c_{i-1,0}\times fib_{i+1}。其中 fib 是题目中描述的斐波那契数。

于是我们首先通过 O(n) 的递推式转移出 a,b，然后 O(n^2) 转移出 dp 和 cnt 的值。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr bool online=0;
constexpr int mod=1e9+7;
int n,fi[5005],dv[5005][2],dc[5005][2],va[5005],vc[5005],anv[5005],anc[5005];
signed main(){
    if(online)
        freopen("piratski.in","r",stdin),
        freopen("piratski.out","w",stdout);
    ios::sync_with_stdio(0); fi[0]=fi[1]=1;
    for(int i=2;i<=5000;++i) fi[i]=(fi[i-1]+fi[i-2])%mod;
    dv[1][1]=dc[1][1]=dc[1][0]=1; dv[1][0]=0;
    for(int i=2;i<=5000;++i){
        va[i]=dv[i-1][1]; vc[i]=dc[i-1][1];
        dv[i][1]=(dv[i-1][0]+dc[i-1][0]*fi[i])%mod;
        dv[i][0]=(dv[i-1][1]+dv[i-1][0])%mod;
        dc[i][0]=(dc[i-1][1]+dc[i-1][0])%mod;
        dc[i][1]=dc[i-1][0];
    }
    anc[0]=1; cin>>n; 
    for(int i=2;i<=5000;++i)
        for(int j=2;j<=i;++j)
            anv[i]=(anv[i]+anv[i-j]*vc[j]+anc[i-j]*va[j])%mod,
            anc[i]=(anc[i]+anc[i-j]*vc[j])%mod;
    for(int i=n;i>=1;i--)
        for(int j=1;j<=i;++j)
            anv[i]=(anv[i]+anv[i-j]*fi[j+1])%mod;
    for(int i=1;i<=n;++i) cout<<anv[i]<<" ";
    cout<<endl;
}