题解：CF1835E Old Mobile
qqqaaazzz_qwq · · 题解
做出 3500 了。
首先去掉重复元素完全没有问题，因为我前面能打出来那么后面也一定可以打出来。
设
讨论我是否知道退格。
知道的话：
我直接随便打一个，
- 如果是我不想要的字符，就直接删掉，代价
2 。 - 如果是我想要的字符但是位置错了，我就删掉，并且在未来直接打出来，代价
3 。 - 如果正确，代价
1 。
不知道退格
如果目前打出的字符全部正确，并且打出字符
- 有概率还是对的，代价
1 - 否则进入错误时代。打出了想要的字符，等我拥有退格之后会删掉然后再打一遍，代价
3 - 打出了不想要的字符，等我拥有退格之后再删掉，代价
2 。
如果已经错了，并且打出字符
- 有概率打出想要的字符，代价
3 ，未来删掉重新打 - 有概率打出不想要的字符，代价
2 ，未来删掉
如果打出退格
- 这里一开始没有想清楚。因为有延迟钦定，所以代价有可能是
0 。 - 具体来说，如果目前什么都没有打出来，代价
1 。 - 如果目前字符全部正确，代价
2 （因为之前的字符没有想到居然会把自己给删掉） - 如果已经有错误的字符了，代价
0 （因为之前算了）
特殊考虑 i=0
- 这个步数并非是
0 ，因为有延迟钦定，可能我打不出退格就没法完成任务。 - 如果已经拥有退格了，或者全部正确，答案是
0 。 - 否则我必须努力直到打出退格，有可能打出不想要的字符得删掉，代价
2 。 - 如果我运气好打到退格了，那么代价为
0 。这里一开始我也想错了，因为已经存在错误，所以要全部删掉，所以我的代价为0 。
经过以上的分析，也说明重复字符的存在不会影响后两维
#include <bits/stdc++.h>
#define FAST ios::sync_with_stdio(false);cin.tie(0)
#define int long long
using namespace std;
/*
by qqqaaazzz
*/
int n,m;
int a[1000010];
int b[1000010];
int f[1010][1010][2][2];//目前还有 i 种颜色我想要，j 种颜色我不想要
const int p = 1000000007;
int fpm(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%p;
a=(a*a)%p;
b>>=1;
}
return res;
}
signed main()
{
cin>>n>>m;
int S=0;
for(int i=1;i<=n;i++){
cin>>a[i];
S+=(b[a[i]]==0);
b[a[i]]=1;
}
int ans=n-S;//这些直接加上就行
//想知道 f[S][m-S][0]
for(int i=0;i<=S;i++){
for(int j=0;j<=m-S;j++){
for(int A=1;A>=0;A--){
for(int B=1;B>=0;B--){
if(i==0){
if(A==1)f[i][j][A][B]=0;//赢了
else if(A==0&&B==0)f[i][j][A][B]=0;//给了，运气太好了
else{
int M=fpm(j+1,p-2);
//随便拿一个，知道拿到退格
if(j)f[i][j][A][B]=(f[i][j][A][B]+j*M%p*(f[i][j-1][A][B]+2))%p;
f[i][j][A][B]=(f[i][j][A][B]+1*M%p*(f[i][j][1][B]+0))%p;
}
//我一定要拿到心心念念的退格，或者不用拿到
continue;
}
//B
if(A){
int M=fpm(i+j,p-2);
//已经知道了退格，那么好说
//
if(j)f[i][j][A][B]=(f[i][j][A][B]+j%p*M%p*(f[i][j-1][A][B]+2))%p;
f[i][j][A][B]=(f[i][j][A][B]+(i-1)%p*M%p*(f[i-1][j][A][B]+3))%p;
f[i][j][A][B]=(f[i][j][A][B]+1%p*M%p*(f[i-1][j][A][B]+1))%p;
}
else{
int M=fpm(i+j+1,p-2);//这个比较奇怪。
//不知道退格，有可能误入歧途
if(B==0){
//有概率直接对了
f[i][j][A][B]=(f[i][j][A][B]+1*M%p*(f[i-1][j][A][B]+1))%p;//撞大运
//否则的话一定会错
f[i][j][A][B]=(f[i][j][A][B]+(i-1)%p*M%p*(f[i-1][j][A][1]+3))%p;//从此不可能获得好机会了
f[i][j][A][B]=(f[i][j][A][B]+j%p*M%p*(f[i][j-1][A][1]+2))%p;
//这个拿到退格
}
else{
//否则的话一定会错
f[i][j][A][B]=(f[i][j][A][B]+i%p*M%p*(f[i-1][j][A][1]+3))%p;//没有好机会了
f[i][j][A][B]=(f[i][j][A][B]+j%p*M%p*(f[i][j-1][A][1]+2))%p;
}
f[i][j][A][B]=(f[i][j][A][B]+1*M%p*(f[i][j][1][0]+(i==S&&j==m-S?1:(B==0?2:0))))%p;//这个纯纯好结局
}
}
}
}
}
cout<<(f[S][m-S][0][0]+ans)%p;
return 0;
}