Description

构造一个具有 \(n \le 2 \times 10^6\) 个三元环的无向图，需要保证 \(n \le 500\)。

Solution

不断构造若干个相互独立的完全图即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 505;

int a[N][N],n,ind,siz;

signed main()
{
    cin>>n;
    for(int i=500;i>2;i--) if(i*(i-1)*(i-2)/6<=n) 
    {
        n-=i*(i-1)*(i-2)/6;
        for(int j=ind+1;j<=ind+i;j++)
        {
            for(int k=ind+1;k<=ind+i;k++)
            {
                a[j][k]=1;
            }
        }
        ind+=i;
        i++;
    }
    
    cout<<ind<<endl;
    for(int i=1;i<=ind;i++) 
    {
        for(int j=1;j<=ind-i;j++) cout<<a[i][i+j]<<" ";
        cout<<endl;
    }
    return 0;
}`