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

ExFish · 2025-11-26 15:25:02 · 题解

我用的是神秘最劣 \mathcal O(n^3) 做法，直接冲过去了。少量打表可以得出结论：答案一定是一个 1\sim n^2 的排列。所以你考虑用链表维护然后直接暴力即可。因为 n 只开了 1000 所以随便冲。正解是用二次剩余，但是这题做法很多。

#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;
}