专栏文章

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

CChenyichen0420
P10259题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min037hn
此快照首次捕获于
2025/12/01 18:22
3 个月前
此快照最后确认于
2025/12/01 18:22
3 个月前
查看原文

思路分析

一看就差不多知道是 O(n2)O(n^2) 的 DP 了。接下来就是去推一下转移式一类的东西。
首先，一个很自然的想法是令 dpidp_i 表示最后一段数字的海盗表示在 ii 位置结束时的所有可能的正整数序列的和之和，并用 cnticnt_i 表示对应的不同的正整数序列的个数。
思考转移。显然 dpi=∑j<i(dpj×ai−j+cntj×bi−j),cnti=∑j<i(cntj×ai−j)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,ba,b 是转移系数。
我们思考一下这些转移系数是什么。对应到 dpdp 和 cntcnt 的状态设计上，显然 aia_i 表示的是长度为 ii 的单个数字的海盗表示的方案数，而 bib_i 则表示的是这些数字的海盗表示的原数字之和。
于是现在我们思考怎么快速的求出 ai,bia_i,b_i。我们发现我们可以再进行一次 DP。具体的来说，我们令 ci,0/1c_{i,0/1} 表示长度为 ii 的，最后一个数字为 0/10/1 的还没有结束的数字的海盗表示方案数，令 vi,0/1v_{i,0/1} 表示这些数字的海盗表示的原数字之和。
那么显然，只有在一个末尾为 11 的数字的海盗表示后面再加上一个 11 表示终止，才形成了一个完整的数字的海盗表示。于是 ai=ci−1,1,bi=vi−1,1a_i=c_{i-1,1},b_i=v_{i-1,1}。
考虑 c,vc,v 的转移式。非常显然，ci,1=ci−1,0,ci,0=ci−1,0+ci−1,1,vi,0=vi−1,1+vi−1,0,vi,1=vi−1,0+ci−1,0×fibi+1c_{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}。其中 fibfib 是题目中描述的斐波那契数。
于是我们首先通过 O(n)O(n) 的递推式转移出 a,ba,b，然后 O(n2)O(n^2) 转移出 dpdp 和 cntcnt 的值。
代码如下：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...