Mad，做这道题目的时候把某个定理想错了，想的既错误又复杂，笑死，根本不会做，后面发现想错了，就简单很多了，不久就知道怎么做了。
定理1：假如给每个 B 标号，那么最终的芯片排列中 B 的不同排列有 $(n-1)!$ 种，因为最底下的 B 是固定的，而且每个排列对应一种操作方式（指的是 B 的操作方式）。（这个定理解决了 B 的位置）
定理2：我们定义最终排列中 B 下面的 R 的数量为其的权值，那么前 $i$ 个 B 的权值不超过第 $i$ 个 B 前面的 R 的数量，且只要满足这个要求，就一定能够构造出来。（这个定理解决了 R 的位置）
定理2的构造方法是在放第 $i$ 个 B 之前提前把芯片放到他即将覆盖的 B 的上面就行了，不难发现，在第 $i$ 个 B 放之前一定能放，不管即将被覆盖的 B 怎么移动，同时覆盖了之后一定不能再放。
那么接下来就是怎么做的问题了，显然求出每个 $B$ 的权值然后排列就行了，不难发现，我们可以人为的规定权值非严格单调递增。
接下来我的 DP 是：$dp[i][j][k]$ 表示前 $i$ 个 B 被考虑过了，前面还有 $j$ 个 R ，同时第 $i$ 个芯片的权值为 $k$ 。
不难发现 $k->k+1$ 的更新最多跑 $\frac{n}{k+1}$ 步，然后就会触发无法放置然后终止后续的更新。
所以这里有个调和级数，时间复杂度： $O(n^3\log{n})$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
#define N 310
using namespace std;
typedef long long LL;
const LL mod=998244353;
LL nfc[N],fc[N];
LL dp[N][N][N];
int n,m,a[N];
char st[N];
LL C(int x,int y){return fc[x]*nfc[y]%mod*nfc[x-y]%mod;}
int main(){
scanf("%d%s",&n,st+1);
fc[0]=fc[1]=nfc[0]=nfc[1]=1;for(int i=2;i<=n;i++)nfc[i]=nfc[mod%i]*(mod-mod/i)%mod;
for(int i=1;i<=n;i++)nfc[i]=nfc[i-1]*nfc[i]%mod,fc[i]=fc[i-1]*i%mod;
for(int i=1;i<=n;i++){
if(st[i]=='B')m++;
else a[m+1]++;
}
for(int i=1;i<=m;i++)a[i]+=a[i-1];
for(int i=0;i<m;i++){
dp[i][a[i]][0]=C(m-1,i);
for(int j=0;j<=a[i];j++){
for(int k=1;k<=a[m-1];k++)dp[i][j][k]=(dp[i][j][k]+dp[i][j][k-1])%mod;
}
for(int j=0;j<=a[i];j++){
for(int k=a[m-1];k>=1;k--){
int t=k-1,now=j;
for(int q=i+1;q<m;q++){
now+=a[q]-a[q-1]-k;if(now<0)break;
dp[q][now][k]=(dp[q][now][k]+dp[i][j][t]*C(m-1-i,q-i))%mod;
}
}
}
}
LL ans=0;
for(int i=0;i<=a[m-1];i++)ans=(ans+dp[m-1][i][a[m-1]])%mod;
printf("%lld\n",ans);
return 0;
}
|
然而一翻题解，发现题解的复杂度没有 $\log$ ，于是我又去优化。
然后就改了一个地方，就是对于 $i$ ，实际上能够更新到答案的有效的 $i$ 只会到 $n-\frac{n}{k}$ 左右。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
#define N 310
using namespace std;
typedef long long LL;
const LL mod=998244353;
LL nfc[N],fc[N];
LL dp[N][N][N];
int n,m,a[N];
char st[N];
LL C(int x,int y){return fc[x]*nfc[y]%mod*nfc[x-y]%mod;}
int main(){
scanf("%d%s",&n,st+1);
fc[0]=fc[1]=nfc[0]=nfc[1]=1;for(int i=2;i<=n;i++)nfc[i]=nfc[mod%i]*(mod-mod/i)%mod;
for(int i=1;i<=n;i++)nfc[i]=nfc[i-1]*nfc[i]%mod,fc[i]=fc[i-1]*i%mod;
for(int i=1;i<=n;i++){
if(st[i]=='B')m++;
else a[m+1]++;
}
for(int i=1;i<=m;i++)a[i]+=a[i-1];
for(int i=0;i<m;i++){
dp[i][a[i]][0]=C(m-1,i);
for(int j=0;j<=a[i];j++){
for(int k=1;k<=a[m-1];k++)dp[i][j][k]=(dp[i][j][k]+dp[i][j][k-1])%mod;
}
if(i!=m-1){
for(int j=0;j<=a[i];j++){
for(int k=(a[m-1]-a[i]+j)/(m-1-i);k>=1;k--){
int t=k-1,now=j;
for(int q=i+1;q<m;q++){
now+=a[q]-a[q-1]-k;if(now<0)break;
dp[q][now][k]=(dp[q][now][k]+dp[i][j][t]*C(m-1-i,q-i))%mod;
}
}
}
}
}
LL ans=0;
for(int i=0;i<=a[m-1];i++)ans=(ans+dp[m-1][i][a[m-1]])%mod;
printf("%lld\n",ans);
return 0;
}
|
那么这个复杂度是多少呢？答案是 $O(n^3)$ 。
因为我们不妨考虑枚举 $k$ ，那么有效的 $i$ 有 $O(\frac{n}{k})$ 个，向后转移就平方 $O(n*(\sum\limits_{k=1}^n\frac{n^2}{k^2}))=O(n^3\sum\limits_{i=1}^n\frac{1}{i^2})=O(n^3)$ 。
奇妙吧，这就是时间复杂度分析的美妙之处，一个看似只改变常数的优化竟然能优化掉复杂度中的一个 $\log$ ，实在是奇妙无比。
