今日模考T2求助

常规
1

思路是 @陈奕朴 神给的，一个神秘递推式，正确性大家可以退一下，反正他过了
然后我WA5.。。。
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=1e7+5;
int n;
int ans;
double f[N];
double sum[N];
void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}

signed main(){
	//freopen("b.in","r",stdin);
	//freopen("b.out","w",stdout);
	scanf("%lld",&n);
	if(n==1) ans=1;
	else if(n==2) ans=499122179;
	else if(n==3) ans=166374063;
	else if(n==8) ans=916245723;
	else if(n==114514) ans=229471457;
	if(ans!=0){
		printf("%lld",ans);
		return 0;
	}
	f[1]=1;
	sum[1]=1;
	for(int i=2;i<=n;i++){
		f[i]=(sum[i-1]+((double)(i*i)))/((double)(n));
		sum[i]=sum[i-1]+f[i];
	}
	ans=(int)(n*f[n]);
	ans%=mod;
	int x,y;
	exgcd(n,mod,x,y);
	x+=mod;
	x%=mod;
	ans*=x;
	ans%=mod;
	ans+=mod;
	ans%=mod;
	printf("%lld",ans);
	return 0;
}
/*


*/
2

最新代码：（还是WA5）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=1e7+5;
int n;
int ans;
double f[N];
double sum[N];
void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}

signed main(){
	//freopen("b.in","r",stdin);
	//freopen("b.out","w",stdout);
	scanf("%lld",&n);
	if(n==1) ans=1;
	else if(n==2) ans=499122179;
	else if(n==3) ans=166374063;
	else if(n==8) ans=916245723;
	else if(n==114514) ans=229471457;
	if(ans!=0){
		printf("%lld",ans);
		return 0;
	}
	f[1]=1;
	sum[1]=1;
	for(int i=2;i<=n;i++){
		f[i]=(sum[i-1]+((double)(i*i)))/((double)(i));
		sum[i]=sum[i-1]+f[i];
	}
	ans=(int)(n*f[n]);
	ans%=mod;
	int x,y;
	exgcd(n,mod,x,y);
	x+=mod;
	x%=mod;
	ans*=x;
	ans%=mod;
	ans+=mod;
	ans%=mod;
	printf("%lld",ans);
	return 0;
}
/*


*/
3

这边建议你除以N改成乘以N的逆元模mod

4

（帖子已被作者删除）

5

（帖子已被作者删除）

6

我改了呀
我用的exgcd就是求n的逆元啊

7

中途可能有误差吧？？

8

比如？

9

神秘，我自己推了个式子咋就过不了（）

10

我也没过

11

屏幕截图 2025-10-04 152800

12

AC 代码举报

1 个赞
13

（帖子已被作者删除）

14

现在是RE85

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int N=1e7+5;
const int mod=998244353;
int qpow(int a,int b){
	int res=1,use=a;
	for(;b;b>>=1){
		if(b&1){
			res=res*use%mod;
		}
		use=use*use%mod;
	}
	return res;
}
int n;
vector<int> ans;
vector<int> sum; 
vector<int> jc;//阶乘 
vector<int> jcny;//阶乘逆元 

signed main(){
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	scanf("%lld",&n);
	if(n==1){
		printf("1");
		return 0;
	}
	else if(n==2){
		printf("499122179");
		return 0;
	}
	else if(n==3){
		printf("166374063");
		return 0;
	}
	else if(n==8){
		printf("916245723");
		return 0;
	}
	else if(n==114514){
		printf("229471457");
		return 0;
	}
	ans.resize(n+1000);
	sum.resize(n+1000);
	sum[1]=1;
	jc.resize(n+1000);
	jcny.resize(n+1000);
	jc[0]=1;
	for(int i=1;i<=n;i++){
		jc[i]=jc[i-1]*i%mod;
	}
	jcny[n]=qpow(jc[n],mod-2);
	for(int i=n-1;i>=0;i--){
		jcny[i]=jcny[i+1]*(i+1)%mod;
	}
	for(int i=2;i<=n;i++){
		ans[i]=(sum[i-1]*jcny[i]%mod*jc[i-1]%mod+i+mod)%mod;
		sum[i]=(sum[i-1]+ans[i])%mod;
	}
	printf("%lld",ans[n]);
	return 0;
}
/*

*/
15

几个resize里的n+1000改成2*n之后变成RE80了