【0】做题心得 - 2025 NOIP #69 - T1【构造】

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e3+10;
const ll P=4179340454199820289ll;
int n=1000;
bitset<N*N>mp;
ll s[N][N],a[N][N];
int nxt[N*N],prv[N*N],hd;
ll qp(ll a,ll b){
	ll res=1;
	for(;b;b>>=1,a=(__int128)a*a%P)
		if(b&1) res=((__int128)res*a)%P;
	return (res+P)%P;
}
int main(){
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	hd=0;
	for(int i=0;i<=1e6;i++)
		nxt[i]=i+1;
	for(int i=1;i<=1e6;i++)
		prv[i]=i-1;
	cout<<n<<"\n";
	for(int i=1;i<=n;i++,cout<<"\n"){
		for(int j=1;j<=n;j++){
			s[i][j]=(s[i-1][j]+s[i][j-1]-s[i-1][j-1])%P;
			for(ll k=hd;k<=1e6;k=nxt[k]){	
				if(qp((s[i][j]+k*k)%P,(P-1)/2)!=P-1){
					if(k==hd) hd=nxt[k];
					prv[nxt[k]]=prv[k];
					nxt[prv[k]]=nxt[k];
					s[i][j]=(s[i][j]+k*k)%P;
					cout<<k<<" ";
					break;
				}
			}
		}
	}
	return 0;
}