99到家微网站什么做的,廉江网站开发公司,做网站的细节,西安seo网络优化公司https://ac.nowcoder.com/acm/contest/11166/I 思路#xff1a;dp[i][j] 是表示上上步走在i点#xff0c;上一步走在j点的期望。首先我们很容易想到n^3的做法#xff0c;那我们必须考虑去优化一维的时间复杂度。我们可以考虑使用前缀和优化dp转移。
我们枚举i点#xff0c…https://ac.nowcoder.com/acm/contest/11166/I 思路dp[i][j] 是表示上上步走在i点上一步走在j点的期望。首先我们很容易想到n^3的做法那我们必须考虑去优化一维的时间复杂度。我们可以考虑使用前缀和优化dp转移。
我们枚举i点那么j点必须是比i点要大的然后在他们的pos位置存入相应的值再计算后缀和那这些就是i点所有合法的情况了。
我们简单想一下我们转移时可以由dp[i][x1]-dp[x2][i]即转移去它的前一步可以知道x1是比i大然后x2是比i小的。根据我上面说的将dp[i][x1]的情况预处理一下然后转移的时候我们枚举x2然后取x2的pos的后缀和就是dp[x2][i]的答案。
最后统计答案的时候只需要将dp[0][i]全部相加然后除于n就是答案了。
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
#include cstdlib
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define sc second
#define pb push_back
#define endl \n
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairchar,ll pii;
int dx[8] {-1,1,0,0,1,1,-1,-1},dy[8] {0,0,1,-1,-1,1,-1,1};
const ll mod998244353;
const ll N 5e310;
const ll M 250000;
const double eps 1e-4;
//const double piacos(-1);
ll qk(ll a,ll b){ll ans1;while(b){if(b1) ansans*a%mod;aa*a%mod;b/2;}return ans;}
ll n,a[N];
ll sum[N],cnt[N],pos[N];
ll inv[N],dp[N][N];void sovle(){cinn;for(int i1;in;i){ cina[i];pos[a[i]]i;}for(int i1;in;i) inv[i]qk(i,mod-2);for(int in;i1;i--){FILL(cnt,0);FILL(sum,0);for(int ji1;jn;j){cnt[pos[j]];sum[pos[j]]dp[i][j];}for(int jn-1;j0;j--){cnt[j]cnt[j1];sum[j](sum[j]sum[j1])%mod;}for(int j0;ji;j){int idpos[j];dp[j][i](sum[id]*inv[cnt[id]]%mod1)%mod;}}ll ans0;for(int i1;in;i) ans(ansdp[0][i])%mod;ansans*inv[n]%mod;coutans%modendl;
}
int main()
{int t1;while(t--){sovle();}return 0;
}
