题意: 线段树是这样一种数据结构：根节点表示区间 [1, n]；对于任意一个表示区间 [l, r] 的节点，若 l < r， 则取 mid = ⌊l+r/2⌋，该节点的左儿子为 [l, mid]，右儿子为 [mid + 1, r]；若 l = r，则它为叶子。 一棵树的匹配是指一个树边集合，满足任意两条边没有公共端点。一棵树的最大匹配是指所有合法 匹配方案中，所选树边最多的匹配方案。 给定一棵表示 [1, n] 的线段树，请求出它的最大匹配中有多少条边，并求出有多少种最大匹配的方 案。因为答案很大，请对 998244353 取模输出。 Input 第一行包含一个正整数 n(1 ≤ n ≤ 1018)。 Output 输出一行两个整数，第一个表示最大匹配中的边数，第二个表示方案数对 998244353 取模的结果。
f[n]表示大小为n的线段树的最大匹配数,g[n]表示方案数. 结论:线段树每一层的节点大小最多有两种. 如果上一层有2k,2k-1,那下一层就有k,k-1.如果上一层有2k,2k+1,那么下一层就有k,k+1.反正最多两种. 层数logn,那么有用状态2logn个,200不到,map开dp数组+记忆化搜索,完事.
#include<cstdio> #include<map> using namespace std; typedef long long ll; const ll mod=998244353; map<ll,ll> f0,f1; map<ll,ll> g0,g1; ll f(ll n){ if(n==1)return 0; if(f1[n])return 0; ll l=n/2,r=n-n/2; f(l);f(r); f0[n]=max(f0[l],f1[l])+max(f0[r],f1[r]); f1[n]=1+max(f0[l]+max(f0[r],f1[r]),f0[r]+max(f0[l],f1[l])); ll ans0=0,ans1=0; if(f0[l]==f1[l])ans0=g0[l]+g1[l]; else if(f0[l]<f1[l])ans0=g1[l]; else ans0=g0[l]; if(f0[r]==f1[r])ans1=g0[r]+g1[r]; else if(f0[r]<f1[r])ans1=g1[r]; else ans1=g0[r]; g0[n]=ans0*ans1%mod; g1[n]=0; if(f1[n]==f0[l]+max(f0[r],f1[r])+1)g1[n]+=g0[l]*1ll*ans1%mod; if(f1[n]==f0[r]+max(f0[l],f1[l])+1)g1[n]+=g0[r]*1ll*ans0%mod; g1[n]%=mod; return max(f0[n],f1[n]); } int main(){ ll n;scanf("%lld",&n); f0[1]=f1[1]=0; g0[1]=1;g1[1]=0; ll ans1=f(n); ll ans2=0; if(f0[n]==ans1)ans2=(ans2+g0[n])%mod; if(f1[n]==ans1)ans2=(ans2+g1[n])%mod; printf("%lld %lld\n",ans1,ans2); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/8426442.html
