有没有做网站一次付费,专业网络推广方案,东莞网站制作购买,网站主办者有效证件电子件I-Increasing Subsequence fi,j,0/1f_{i,j,0/1}fi,j,0/1表示上一轮第一个人选了iii#xff0c;第二个人选了jjj#xff0c;并且当前是第1/2个人选择的概率。
转移考虑枚举k下一步往哪走 fi,k,1∑fi,j,0/cntf_{i,k,1}\sum f_{i,j,0}/ \text{cnt}fi,k,1∑fi,j,0/cnt fk,…I-Increasing Subsequence
fi,j,0/1f_{i,j,0/1}fi,j,0/1表示上一轮第一个人选了iii第二个人选了jjj并且当前是第1/2个人选择的概率。
转移考虑枚举k下一步往哪走 fi,k,1∑fi,j,0/cntf_{i,k,1}\sum f_{i,j,0}/ \text{cnt}fi,k,1∑fi,j,0/cnt
fk,j,0∑fi,j,1/cntf_{k,j,0}\sum f_{i,j,1}/ \text{cnt}fk,j,0∑fi,j,1/cnt
答案是所有数组之和每进一个新状态都意味着游戏多进行了一局因此把出现的概率全部累加就是期望局数。 显然的暴力~ 时间复杂度O(n3)O(n^3)O(n3)
Code1
#includebits/stdc.husing namespace std;
using lllong long;const int N5010;
const int mod998244353;ll f[N][N][2];
ll inv[N];
int a[N],n;
ll qmi(ll a,ll b)
{ll res1;while(b){if(b1) resres*a%mod;aa*a%mod;b1;}return res;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;for(int i1;in;i) inv[i]qmi(i,mod-2);for(int i1;in;i) cina[i];for(int i1;in;i)for(int j0;jn;j){if(j0) f[i][j][0]inv[n];int ct0;// 第一个人for(int kj1;kn;k)if(a[k]a[i]a[k]a[j]) ct;for(int kj1;kn;k)if(a[k]a[i]a[k]a[j]) f[i][k][1](f[i][k][1]inv[ct]*f[i][j][0])%mod;// 第二个人ct0;for(int ki1;kn;k)if(a[k]a[i]a[k]a[j]) ct;for(int ki1;kn;k)if(a[k]a[i]a[k]a[j]) f[k][j][0](f[k][j][0]inv[ct]*f[i][j][1])%mod;}ll ans0;for(int i1;in;i)for(int j0;jn;j) ansf[i][j][0]f[i][j][1],ans%mod;coutans\n;return 0;
}没听懂讲题人上述解法的优化询问了mrk大佬的思路。并且参考下面题解感觉更容易理解lalalzo题解
对于上述做法关键是我们需要区分这一步是谁走的而下面的做法考虑在所给序列的值域上从小到大走保证了所选必须比前面所有选的值要大还有一个限制就是对于每一个人的所选序号单增。
设计dp
状态表示fu,vf_{u,v}fu,v表示最后一个人选择vvv而倒数第二个人选择uuu值域从小到大走需要满足uvuvuv停下来的期望步数。
状态转移考虑移动一步fu,v→fv,kf_{u,v}\to f_{v,k}fu,v→fv,k需要满足uvkand posuposkuvk \text{ and } \text{pos}_u\text{pos}_kuvk and posuposk fu,v1cnt∑kfv,k1f_{u,v}\frac{1}{\text{cnt}}\sum_k f_{v,k}1fu,vcnt1k∑fv,k1 发现满足posuposk\text{pos}_u\text{pos}_kposuposk意味着每一个人的所选序号单增。非常巧妙啊~
于是有下面Code2常见的记忆化搜索写法我之前比较熟悉记忆化搜索
Code2
#includebits/stdc.h
using namespace std;
template class Tint T rd()
{T res0;char chgetchar();while(!isdigit(ch)) chgetchar();while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res;
}
const int N5010,mod998244353;
using lllong long;
int pos[N],n;
ll inv[N],f[N][N];
ll qmi(ll a,ll b)
{ll v1;while(b){if(b1) vv*a%mod;aa*a%mod;b1;}return v;
}
// uvk
ll dfs(int u,int v)
{if(f[u][v]!-1) return f[u][v];// f[u][v] - f[v][k] uvkpos[u]pos[k]int ct0;for(int kv1;kn;k) if(pos[u]pos[k]) ct;f[u][v](ct0?1:0);for(int kv1;kn;k) if(pos[u]pos[k]) f[u][v](f[u][v]dfs(v,k)*inv[ct])%mod;return f[u][v];
}
int main()
{nrd();for(int i1;in;i) pos[rd()]i;for(int i1;in;i) inv[i]qmi(i,mod-2);memset(f,-1,sizeof f);ll ans0;for(int i1;in;i) ans(ansdfs(0,i))%mod;ansans*inv[n]%mod;printf(%lld\n,ans);}Code3
把上面记忆化搜索代码转化为迭代考虑该状态会对哪些状态产生贡献就有了下面的Code3
#includebits/stdc.h
using namespace std;
template class Tint T rd()
{T res0;char chgetchar();while(!isdigit(ch)) chgetchar();while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res;
}
const int N5010,mod998244353;
using lllong long;
int pos[N],n;
ll inv[N],f[N][N];
ll qmi(ll a,ll b)
{ll v1;while(b){if(b1) vv*a%mod;aa*a%mod;b1;}return v;
}
int main()
{nrd();for(int i1;in;i) pos[rd()]i;for(int i1;in;i) inv[i]qmi(i,mod-2);// f[k][i] - f[i][j] kij pos[k]pos[j]// f[k][i] 1/ct f[i][j] 1for(int in;i1;i--){for(int k0;ki;k){int ct0;for(int ji1;jn;j) if(pos[j]pos[k]) ct;for(int ji1;jn;j)if(pos[j]pos[k])f[k][i](f[k][i]inv[ct]*f[i][j]%mod);if(ct) f[k][i](f[k][i]1)%mod;}}ll ans0;for(int i1;in;i) ans(ansf[0][i])%mod;ansans*inv[n]%mod;printf(%lld\n,ans);}Code4
不难发现每次我们想知道poskposj\text{pos}_k\text{pos}_jposkposj可以预处理前缀和优化。
#includebits/stdc.h
using namespace std;
template class Tint T rd()
{T res0;char chgetchar();while(!isdigit(ch)) chgetchar();while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res;
}
const int N5010,mod998244353;
using lllong long;
int pos[N],n;
ll sum[N],cnt[N],inv[N],f[N][N];
ll qmi(ll a,ll b)
{ll v1;while(b){if(b1) vv*a%mod;aa*a%mod;b1;}return v;
}
int main()
{nrd();for(int i1;in;i) pos[rd()]i;for(int i1;in;i) inv[i]qmi(i,mod-2);for(int in;i1;i--){memset(cnt,0,sizeof cnt);memset(sum,0,sizeof sum);for(int ji1;jn;j){cnt[pos[j]];sum[pos[j]]f[i][j];}for(int jn-1;j0;j--){cnt[j]cnt[j1];sum[j](sum[j]sum[j1])%mod;}for(int k0;ki;k) {int idpos[k];f[k][i](sum[id]*inv[cnt[id]]%mod1)%mod;}}ll ans0;for(int i1;in;i) ans(ansf[0][i])%mod;ansans*inv[n]%mod;printf(%lld\n,ans);
}总结
其实对于上述两种方法有本质的区别就是定义的状态一个是概率一个是期望步数需要注意如何定义状态~
要加油哦~
