Luogu8389 [ZJOI2022] 树
考虑容斥，每个点有三个状态：不钦定、钦定都是叶子、钦定都是非叶子。对于每一种钦定状态都计算答案，然后乘上对应容斥系数即可。
叶子的钦定是可做的，考虑非叶子的钦定，我们可以用“容斥套容斥”的思想理解：对于钦定都是非叶子的点 \(i\)，考虑用总方案数减去钦定其中之一是叶子的方案数，再加上两者都是叶子的方案数。
把非叶子的钦定放回原容斥里描述：减去总方案数，加上钦定第一棵树中是叶子的方案数、加上钦定第二棵树中是叶子的方案数、减去两棵树中都是叶子的方案数。
和不钦定、钦定叶子的方案加起来，相当于：加上钦定第一棵树中是叶子的方案数、加上钦定第二棵树中是叶子的方案数、减去 \(2\times\) 两棵树中都是叶子的方案数。
设 \(f[i,j,k]\) 表示考虑了前 \(i\) 个点，其中第一棵树中有 \(j\) 个没有被钦定是叶子的点，第二棵树中还剩 \(k\) 个没有被钦定是叶子的点。
转移容易。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn=510, M=1e9;
ll n,mod,f[2][maxn][maxn],ans;
int main(){
scanf("%lld%lld",&n,&mod);
for(ll i=1;i<n;i++) f[1][1][i]=i;
puts("1");
for(ll i=2;i<n;i++){
memset(f[i&1],0,sizeof f[i&1]);
for(ll j=1;j<=n;j++)
for(ll k=1;k<=n;k++){
if(!f[i&1^1][j][k]) continue;
f[i&1][j][k-1]=(f[i&1][j][k-1]+f[i&1^1][j][k]*j*(k-1))%mod;
f[i&1][j+1][k]=(f[i&1][j+1][k]+f[i&1^1][j][k]*j*k)%mod;
f[i&1][j][k]=(f[i&1][j][k]-2*f[i&1^1][j][k]*j*k)%mod;
}
ans=0;
for(ll j=1;j<=i;j++)
ans=(ans+f[i&1][j][1]*j)%mod;
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}
AGC036F Square Constraints
相当于有两个圆，每个位置的取值必须在两个圆中间，求方案数。
本质上还是 \(p_i\in[l_i,r_i]\) 的计数。考虑如果没有下面那个圆怎么做，把 \(r_i\) 从小到大排序，答案就是 \(\prod\limits_i (r_i-i+1)\)。
如果有下面的圆，因为钦定后本质上还是在一段前缀上取值，我们考虑容斥。
钦定取值在下面圆内的位置集合 \(S\)，不难发现 \(S\in \{0,2,...,n-1\}\)，考虑使用 dp 来综合所有的 \(S\)。
但是这样有个问题，我们难以计算方案数。尝试先排序：对于 \(i=n...2n-1\)，基准为 \(r_i\)；对于 \(i=0...n-1\)，基准为 \(l_i-1\)。按基准来排序。
对于未被钦定的位置 \(i\)，我们还要知道 \(r_i\) 前面有多少个比他小的数，发现我们只要知道了钦定的位置个数就能算出。因为对于每个钦定的位置 \(i(i<n)\)，\(l_i-1\) 总是不大于所有未钦定的位置 \(j(j<n)\) 的 \(r_j\)。
所以我们考虑 dp 开始前先枚举钦定的位置个数，便于计算。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn=510;
ll n,id[maxn],mod,f[maxn][maxn],ans,l[maxn],r[maxn];
bool cmp(ll x,ll y){ ll p=(r[x]<r[y]);
x=(x<n? l[x]-1:r[x]), y=(y<n? l[y]-1:r[y]);
return x^y? x<y:p;
}
int main(){
scanf("%lld%lld",&n,&mod);
for(ll i=0;i<(n<<1);i++){
if(i<n) l[i]=ceil(sqrt(n*n-i*i));
r[i]=sqrt(4*n*n-i*i); id[i+1]=i;
r[i]=min(r[i],(n<<1)-1);
} sort(id+1,id+1+(n<<1),cmp);
for(ll d=0;d<=n;d++){ //printf("d = %lld\n",d);
memset(f,0,sizeof f);
f[0][0]=1; ll cnt=0;
for(ll i=1;i<=(n<<1);i++){
for(ll j=0;j<=d&&j<=i-1-cnt;j++){
if(id[i]>=n){
if(cnt+j<=r[id[i]]) f[i][j]=(f[i][j]+f[i-1][j]*(r[id[i]]+1-cnt-j))%mod;
}
else{
if(n+d+(i-1-cnt-j)<=r[id[i]]) f[i][j]=(f[i][j]+f[i-1][j]*(r[id[i]]+1-n-d-(i-1-cnt-j)))%mod;
if(j<d&&cnt+j<l[id[i]]) f[i][j+1]=(f[i][j+1]+f[i-1][j]*(l[id[i]]-cnt-j))%mod;
}
} cnt+=(id[i]>=n);
}
ans=(ans+(d&1? mod-1:1)*f[n<<1][d])%mod;
} printf("%lld",ans);
return 0;
}
AGC040E Prefix Suffix Addition
考虑原问题的本质：将 \(x_i\) 分裂为 \(a_i+b_i\)，钦定 \(a_0=b_{n+1}=0\)，最小化 \(\sum\limits_{i=1}^n[a_{i-1}>a_i]+\sum\limits_{i=1}^n[b_i<b_{i+1}]\)。
挖掘问题的本质很重要，这样能转化模型。
我们暴力，设 \(f[i,j]\) 表示确定了 \(a_{1...i},b_{1...i}\)，并且 \(a_i=j\) 的答案。
转移很显然：
\[f[i,j]=\min_{0\le k\le x_{i-1}} \{[k>j]+[x_{i-1}-k<x_i-j]+f[i-1,k]\} \]- 一个 trick：注意每次转移最多加 \(2\)，并且都是全局贡献，那么 \(f[i,\_]\) 最多 \(3\) 段，直接维护。
设 \(val=\min\limits_{0\le k\le x_{i-1}} f[i-1,k]\)，且位置为 \(p\)，不难发现 \(f[i,\max(p,x_i-(x_{i-1}-p))...x_i]\) 都会变成 \(val\)。
接着处理 \(val+1\) 的段，是 \([\min(p,x_i-(x_{i-1}-p)),\max(p,x_i-(x_{i-1}-p)))\)。
剩下那段是前缀，等于 \(val+2\)。
顺便可以发现，我们的 \(p\) 是贪心取最小的位置，我们直接维护 \(p_1,p_2,p_3\) 表示三段的起点即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn=2e5+10, mod=998244353, iv=mod-mod/2;
ll n,a[maxn],p1,p2,p3,val;
int main(){
scanf("%lld",&n);
p1=p2=p3=val=0;
for(ll i=1;i<=n+1;i++){
if(i<=n) scanf("%lld",a+i);
ll q3=min(a[i]+1,max(p3,a[i]-(a[i-1]-p3))),
q2=max(0ll,min(min(p3,a[i]-(a[i-1]-p3)),max(p2,a[i]-(a[i-1]-p2)))), q1=0, v=val;
if(q3>a[i]) q3=q2, q2=q1, q1=0, ++v;
p1=q1, p2=q2, p3=q3, val=v;
} printf("%lld",val);
return 0;
}