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 second
const 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 long
const 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+1
struct 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 998244353
const 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);
}