NOI 2017 题目选做
蚯蚓排队
题目描述
点此看题
解法
做法是显然的，合并的时候把 \(k^2\) 个影响到的串暴力修改即可，使用 \(\tt hash\) 的话就很方便查询。
时间复杂度 \(O(n\cdot k^2+|s|)\) 好像过不去，但是注意到还有 \(c\leq 1000\) 这个限制。考虑没有分裂操作时，由于只有 \(O(nk)\) 个有效串，根据势能法时间复杂度 \(O(nk)\)，每次分裂操作最多让势能增加 \(O(k^2)\)，所以总时间复杂度 \(O(n\cdot k+c\cdot k^2+|s|)\)
但是突然发现我不会手写 \(\tt Hash\) 表（我好菜），于是问了 \(\tt dym\) 大佬。发现只需要对哈希值再哈希一遍，限制到一个较小的范围内（比如 \(10^7+7\)），然后用前向星维护，插入和查询都可以暴力扫描，期望单次时间复杂度就能做到 \(O(1)\)
#include
#include
#include
using namespace std;
const int M = 200005;
const int p = 1e7+7;
const int MOD = 998244353;
#define ull unsigned long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,tot,f[p+5],a[M],h1[M],H1[M],b1[M],pre[M],nxt[M];
ull h2[M],H2[M],b2[M];char s[p];
struct edge{ull h2;int c,L,next;}e[M*55];
void add(int L,int h1,ull h2,int c)
{
//printf(">> %d %d %u %d\n",L,h1,h2,c);
for(int i=f[h1];i;i=e[i].next) if(e[i].h2==h2)
{e[i].c+=c;return ;}
e[++tot]=edge{h2,c,L,f[h1]},f[h1]=tot;
}
int ask(int L,int h1,ull h2)
{
for(int i=f[h1];i;i=e[i].next)
if(e[i].L==L && e[i].h2==h2) return e[i].c;
return 0;
}
void work()
{
int op=read();
if(op==1 || op==2)
{
int x=read(),y=0,A=0,B=0,f=(op==1)?1:-1;
y=(op==1)?read():nxt[x];
for(int i=1,t=x;i<=50 && t;i++,t=pre[t],A++)
h1[i]=(h1[i-1]+a[t]*b1[i-1])%p,h2[i]=h2[i-1]+a[t]*b2[i-1];
for(int i=1,t=y;i<=50 && t;i++,t=nxt[t],B++)
H1[i]=(H1[i-1]*13+a[t])%p,H2[i]=H2[i-1]*371+a[t];
for(int l=2;l<=50 && l<=A+B;l++)
for(int i=1;i 泳池
题目描述
点此看题
解法
首先是一个简单的转化：我们可以求出最大游泳场 \(\leq k\) 的概率减去 \(
直接考虑 \(dp\)，设 \(f_i\) 表示第 \(i\) 列的第一行就有一个障碍物（称之为坏点），并且前 \(i\) 行满足条件的概率。那么转移可以直接枚举好点的长度，设 \(dp_{i,j}\) 表示长度为 \(i\) 的好点段，最低的高度为 \(j\)，并且，满足条件的概率：
\[f_i\leftarrow (1-p)\cdot \sum_{j=0}^{i-1}f_{i-j-1}\cdot\sum_{j=1}^{\lfloor\frac{k}{i}\rfloor} dp_{i,j} \]考虑 \(dp_{i,j}\) 的转移可以枚举第一个高度 \(=j\) 的点，那么会划分成两部分，需要提前判断整个是否合法，那么达到的效果就是嵌套判断合法，这样就可以满足最大游泳场 \(\leq k\) 的条件了：
\[dp_{i,j}\leftarrow [i\cdot j\leq k]\cdot (1-p)\cdot p^j\cdot \sum_{l=1}^i(\sum_{k>j}dp_{l-1,j+1})\cdot(\sum_{k\geq j}dp_{i-l,j}) \]显然可以使用前缀和优化，我们只保留合法状态的话那么时间复杂度 \(O(k^2\log k)\)
最后 \(f\) 的转移可以用常系数线性递推，求出 \(f_{n+1}\) 之后除以 \((1-p)\) 就得到了答案，时间复杂度 \(O(k^2\log n)\)
总结
概率期望问题中注意一些简单的前缀 \(/\) 差分技巧（总结了好多遍还是不会，以后我不会一次我就复读一次）
借用数学课上球哥的最值定义技巧，面对最大值不等式限制时，我们并不需要直接判断最大值是否满足限制，而是把这个限制融入所有可能值的判断中，就像本题我们把这个限制融入了 \(dp\) 的过程中。
#include
#include
const int M = 2005;
const int MOD = 998244353;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,k,x,y,p,q,dp[M][M],f[M],b[M],s[M],t[M],a[M],r[M];
void add(int &x,int y) {x=(x+y)%MOD;}
int qkpow(int a,int b)
{
int r=1;
while(b>0)
{
if(b&1) r=r*a%MOD;
a=a*a%MOD;
b>>=1;
}
return r;
}
int work(int k)
{
memset(a,0,sizeof a);
memset(b,0,sizeof b);
memset(f,0,sizeof f);
memset(s,0,sizeof s);
memset(t,0,sizeof t);
memset(r,0,sizeof r);
memset(dp,0,sizeof dp);
for(int i=0;i<=k+1;i++) dp[0][i]=1;
for(int j=k;j>=1;j--)
for(int i=1;i*j<=k;i++)
{
int r=0;
for(int k=1;k<=i;k++)
add(r,dp[k-1][j+1]*dp[i-k][j]);
dp[i][j]=r*qkpow(p,j)%MOD*q%MOD;
add(dp[i][j],dp[i][j+1]);
}
k++;
for(int i=0;i0)
{
if(m&1)
{
for(int i=0;i<=k;i++) t[i]=r[i],r[i]=0;
for(int i=0;i<=k;i++)
for(int j=0;j<=k;j++)
add(r[i+j],t[i]*a[j]%MOD);
for(int i=k<<1;i>=k;i--)
for(int j=k;j>=0;j--)
add(r[i-j],MOD-r[i]*b[j]%MOD);
}
for(int i=0;i<=k;i++) t[i]=a[i],a[i]=0;
for(int i=0;i<=k;i++)
for(int j=0;j<=k;j++)
add(a[i+j],t[i]*t[j]%MOD);
for(int i=k<<1;i>=k;i--)
for(int j=k;j>=0;j--)
add(a[i-j],MOD-a[i]*b[j]%MOD);
m>>=1;
}
for(int i=0;i