牛客 197C 期望操作数

大意: 给定$x,q$, 每步操作$x$等概率变为$[x,q]$中任意一个数, 求变为$q$的期望操作数.

很容易可以得到$f(x,q)=\frac{\sum\limits_{i=x+1}^qf(i,q)+q-x+1}{q-x}$, 边界条件$f(q,q)=0$.

每次询问复杂度是$O(q)$的, 但是可以发现答案只与$x$和$q$的差有关, 所以预处理出$q=N-1$时的结果即可.

#include <iostream>

#include <cstdio>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

using namespace std;

typedef long long ll;

const int P = 998244353;

const int N = 1e7+10;

int dp[N], inv[N];

int main() {

	inv[0]=inv[1]=1;

	REP(i,2,N-1) inv[i]=(ll)inv[P%i]*(P-P/i)%P;

	int sum = 0;

	PER(i,0,N-2) {

		dp[i] = (ll)(sum+N-i)*inv[N-1-i]%P;

		(sum += dp[i]) %= P;

	}

	int t;

	scanf("%d", &t);

	while (t--) {

		int x, q;

		scanf("%d%d", &x, &q);

		printf("%d\n",dp[N-1-q+x]);

	}

}

巴特西

牛客 197C 期望操作数

最新文章

热门文章