2024.10.08
P3251 JLOI2012 时间流逝
设 \(f(S)\) 为可重复集 \(S\) 进化的期望天数。
\[f(S)=pf(P)+\frac{1-p}{m}\sum_{i=1}^mf(T)+1
\]
\(P\) 为 \(S\) 除去最小值的集合，\(T\) 为 \(S\) 加上一个元素的集合。
不难发现，集合构成了一颗树的形态，根是空集，\(S\) 父亲为 \(P\)，\(T\) 父亲为 \(S\)。
假设所有 \(f(S)\) 满足 \(f(S)=kf(P)+b\)。
数学归纳法，叶子节点显然满足，对于非叶子节点：
\[f(S)=pf(P)+\frac{1-p}{m}\sum_{i=1}^mk_if(S)+b_i
\]
记：
\[t=\frac{1-p}{m},K=\sum_{i=1}^mk_i,B=\sum_{i=1}^mb_i
\]
有：
\[f(S)=\frac{p}{1-tK}f(P)+\frac{1+tB}{1-tK}
\]
#include<bits/stdc++.h>
using namespace std;#define db double
#define pdd pair<double,double>
#define fi first
#define se secondconst int maxn=55;int n,T;
double p;int a[maxn];inline pdd dfs(int s,int mn)
{if(s>T) return {0,0};db k=0,b=0,t=(1-p)/mn;pdd ret;for(int i=1;i<=mn;i++) ret=dfs(s+a[i],i),k+=ret.fi,b+=ret.se;if(!s) t=1.0/mn;return {p/(1-t*k),(1+t*b)/(1-t*k)};
}int main()
{while(~scanf("%lf%d%d",&p,&T,&n)){for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+n+1);printf("%.3lf",dfs(0,n).se);}
}
P5303 GXOI/GZOI2019 逼死强迫症
不难发现，如果确定为 \(1\times 1\) 的块放的区域的长度，仅有唯二的方案。
设 \(g_i\) 为 \(1\times 1\) 放置区域的长度为 \(i\) 的方案数，有：
\[g_i=g_{i-1}+g_{i-2}
\]
是斐波那契数列。
对于答案 \(F_i\)，类似的推出 \(F_i=F_{i-1}+F_{i-2}+2\times g_{i-1}-2\)。
使用矩阵加速，即可 AC。
#include<bits/stdc++.h>
using namespace std;#define ll long longconst ll mod=1e9+7;
const int maxn=8;struct Matrix
{int n,m;int a[maxn][maxn];Matrix(int x=0,int y=0){memset(a,0,sizeof(a));n=x,m=y;}inline void SetUnit(){for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=(i==j);}friend inline Matrix operator * (Matrix a,Matrix b){Matrix ret(a.n,b.m);for(int i=1;i<=ret.n;i++)for(int k=1;k<=a.m;k++)for(int j=1;j<=ret.m;j++){ret.a[i][j]=(ret.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;}return ret;}
}s;
inline Matrix ksm(Matrix x,int y)
{Matrix sum(5,5);sum.SetUnit();for(;y;y/=2,x=x*x) if(y&1) sum=sum*x;return sum;
}int main()
{s.n=5,s.m=5;s.a[1][1]=s.a[1][2]=s.a[2][1]=s.a[3][3]=s.a[3][4]=s.a[4][3]=s.a[5][5]=1;s.a[3][1]=2,s.a[5][1]=mod-2;int _;scanf("%d",&_);while(_--){int n;scanf("%d",&n);if(n<3){puts("0");continue;}Matrix A(1,5);A.a[1][3]=2,A.a[1][4]=A.a[1][5]=1;printf("%d\n",(A*ksm(s,n-2)).a[1][1]);}
}
P4229 某位歌姬的故事
见博客
P4647 IOI2007 sails 船帆
每次选择 \(k\) 个最少放置船帆的位置放帆，将 \(h\) 升序排序，船帆放置数量随高度至下向上数量递减，每次选择 \([h-k+1,h]\) 之间的位置放置，但对于与放置数量 \(h-k+1\) 高度相同的高度，需要将选择平移维护单调性。
#include<bits/stdc++.h>
using namespace std;const int maxn=100005;int n,ans;
struct node{int h,k;}a[maxn];inline bool cmp(node a,node b){return a.h<b.h;}namespace linetree
{#define lch(p) p*2#define rch(p) p*2+1struct treenode{int mx,mi,lazy;}tr[maxn*8];int lx,rx;inline void clr(){lx=maxn,rx=0;}inline void push_down(int p,int l,int r){if(l==r) {tr[p].lazy=0;return ;}tr[rch(p)].lazy+=tr[p].lazy;tr[rch(p)].mi+=tr[p].lazy,tr[rch(p)].mx+=tr[p].lazy;tr[lch(p)].lazy+=tr[p].lazy;tr[lch(p)].mi+=tr[p].lazy,tr[lch(p)].mx+=tr[p].lazy;tr[p].lazy=0;}inline void push_up(int p,int l,int r){if(l==r) return ;tr[p].mi=min(tr[lch(p)].mi,tr[rch(p)].mi);tr[p].mx=max(tr[lch(p)].mx,tr[rch(p)].mx);}inline void updata(int p,int l,int r,int lx,int rx,int val){if(rx<lx) return ;if(r<lx||l>rx) return ;push_down(p,l,r);if(lx<=l&&r<=rx){tr[p].lazy+=val;tr[p].mi+=val,tr[p].mx+=val;return ;}int mid=(l+r)>>1;updata(lch(p),l,mid,lx,rx,val);updata(rch(p),mid+1,r,lx,rx,val);push_up(p,l,r);}inline int qry1(int p,int l,int r,int x){push_down(p,l,r);if(r<x||l>x) return 0;if(l==r) return tr[p].mi;int mid=(l+r)>>1;return qry1(lch(p),l,mid,x)+qry1(rch(p),mid+1,r,x);}inline void qry2(int p,int l,int r,int x){push_down(p,l,r);if(tr[p].mx<x||tr[p].mi>x) return ;if(tr[p].mi==x) rx=max(rx,r);if(tr[p].mx==x) lx=min(lx,l);if(tr[p].mx==x&&tr[p].mi==x) return ;int mid=(l+r)>>1;qry2(lch(p),l,mid,x),qry2(rch(p),mid+1,r,x);}
}int main()
{int m=0;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&a[i].h,&a[i].k),m=max(a[i].h,m);sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){int p=linetree::qry1(1,1,m,a[i].h-a[i].k+1);linetree::clr();linetree::qry2(1,1,m,p);int l=max(linetree::lx,1),r=min(linetree::rx,a[i].h);linetree::updata(1,1,m,r+1,a[i].h,1);linetree::updata(1,1,m,l,l+a[i].k-(a[i].h-r)-1,1);}long long ans=0;for(int i=1;i<=m;i++){int p=linetree::qry1(1,1,m,i);ans+=1ll*p*(p-1)/2;}printf("%lld",ans);
}
P8321 『JROI-4』沈阳大街 2
将 \(a,b\) 合并为一个数组 \(c\) 后排序，然后将其中的 \(a,b\) 两两配对，记权值为较后点的权值。
设 \(f[i][j]\) 表示前 \(i\) 个配对了 \(j\) 对的总贡献，有转移：
\[f[i][j]=f[i-1][j-1]\times c[i]\times(tmp-(j-1))+f[i-1][j]
\]
其中 \(tmp\) 表示 \(c[1\sim i-1]\) 中与 \(i\) 颜色不同的数的个数。
#include<bits/stdc++.h>
using namespace std;#define ll long long
#define mod 998244353const int maxn=5005;struct node{int val,sub;}a[maxn*2];int n;
int cnt[2][maxn*2];ll f[maxn*2][maxn];inline ll ksm(ll x,ll y)
{ll sum=1;for(;y;y/=2,x=x*x%mod) if(y&1) sum=sum*x%mod;return sum;
}
inline bool cmp(node a,node b){return a.val>b.val;}int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].sub=0;for(int i=n+1;i<=2*n;i++) scanf("%d",&a[i].val),a[i].sub=1;sort(a+1,a+n*2+1,cmp);for(int i=1;i<=n*2;i++){cnt[0][i]=cnt[0][i-1],cnt[1][i]=cnt[1][i-1];cnt[a[i].sub][i]++;}f[0][0]=1;for(int i=1;i<=n*2;i++){ll tmp=cnt[!a[i].sub][i];f[i][0]=1;for(int j=1;j<=n;j++){if(j<=tmp)f[i][j]=(f[i-1][j-1]*a[i].val%mod*(tmp-(j-1))%mod)%mod;f[i][j]=(f[i][j]+f[i-1][j])%mod;}}ll res=1;for(int i=1;i<=n;i++) res=res*i%mod;printf("%lld",ksm(res,mod-2)*f[n*2][n]%mod);
}
