信友题day2

概率取模+大数据读入处理

#include<bits/stdc++.h>
using namespace std;
#define rt register int 
#define ll long long  
const int p=998244353;
ll n,m;
inline int read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x*10%p+(ch^48))%p;ch=getchar();}
	return x*f;
}
inline ll qsm(ll a,ll b)
{
	ll x=a,res=1;
	while(b){
		if(b&1)res=res*x%p;
		b>>=1;x=x%p*(x%p)%p;
//		cout<<"res:"<<res<<endl;
	}
	return res%p;
}
int main()
{
	ios::sync_with_stdio(false);
	n=read();m=read();
//	cout<<endl;
//	cout<<n<<endl;
//	cout<<m<<endl;
//	cout<<(n*n%p-m)<<endl;
//	cout<<qsm(n*n,p-2)<<endl;
	cout<<(n*n%p+p-m)%p*qsm(n*n,p-2)%p<<endl;
	return 0;
}

点的二维离散（暴力）

#include<bits/stdc++.h>
using namespace std;
#define rt register int 
#define N 100005
struct node{
	int x,y;
}p[100005];
int a[N],b[N],c[N],d[N];
int n,cnt,x,y,mx,my;
long long dp[1005][1005];
int st[1005][1005];
inline bool cmp(node a,node b){
	if(a.y!=b.y)return a.y<b.y;
	return a.x<b.x;
}
inline void init(){
	sort(a + 1, a + cnt + 1);
	sort(c+1,c+cnt+1);
	x=unique(a+1,a+cnt+1)-a-1;
	y=unique(c+1,c+cnt+1)-c-1;
	for(int i=1;i<=cnt;++i){
		b[i]=lower_bound(a+1,a+x+1,b[i])-a;
		d[i]=lower_bound(c+1,c+y+1,d[i])-c;
	}
	for(int i=1;i<=cnt;++i)
	{
		if(mx<x)mx=x;
		if(my<y)my=y;
	}
	return;
}
int main()
{
	scanf("%d", &n);
	for(int i=1,x,y;i<=n;++i){
		scanf("%d%d", &x,&y);
		if(x>=0&&y>=0){
			++cnt;
			a[cnt]=b[cnt]=x;
			c[cnt]=d[cnt]=y;
		}
	}
	init();
	for(rt i=1;i<=cnt;++i){
			p[i].x=b[i];p[i].y=d[i];
		}
	for(rt i=1;i<=cnt;++i){
		++dp[p[i].x][p[i].y];
	}
	for(rt i=1;i<=mx;++i)
		for(rt j=1;j<=my;++j)
		{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])+dp[i][j];
		}
	printf("%lld",dp[mx][my]);
	return 0;
}