题解：P12706 并非呃呃

fish_love_cat · 2025-06-08 02:46:11 · 题解

怎么秒了 /jy

容易想到均摊贡献。

发现一行大概要放 \sqrt n 个点。

考虑对序列分块，一个块里面放一个。

假设块长为 d。

于是想到如下构造：

将 d 个序列分为一大组，然后每对于一个序列 d 位分为一小组。

对于每一大组的每个第一小组，使其选择的点全部一致。

然后对于第 k 大组的第 i 个序列中的第 j 个小组，我们选择第 (k+i\times j) \bmod d 点。

尝试说明这样的构造是对的。

显然 j 不同的点肯定不重合。

若 i 相同 k 不同，后半部分出现的偏移一定会导致整个序列不重合。

若 k 相同 i 不同，构造成立当且仅当找不到 j 使得 i_1\times j \equiv i_2\times j\pmod d 成立。

若 i,k 均不同，构造成立当且仅当找不到两个 j 使得 i_1\times {j_1}-i_2\times {j_1} \equiv i_1\times {j_2}- i_2\times {j_2}\pmod d 成立。

这个式子可以改写成：

那就和前面一致了。

所以现在只需要找到一个 d 使得对于 a,b,c<d 不存在 a\times b\equiv a\times c \pmod d。

注意到当 d 是质数时，易证这个命题一定成立。于是钦定 d=47，答案数量为 d^3=103823，非常正确。

做完了。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n==4){// 小数据手搓验证规律
        cout<<"1100\n";
        cout<<"1001\n";
        cout<<"1010\n";
        cout<<"0011\n";
    }else if(n==10){
        cout<<"1001001000\n";
        cout<<"1000100100\n";
        cout<<"1000010010\n";
        cout<<"0101000100\n";
        cout<<"0100100010\n";
        cout<<"0100011000\n";
        cout<<"0011000010\n";
        cout<<"0010101000\n";
        cout<<"0010010100\n";
        cout<<"0000000001\n";
    }else{
        map<int,bool>mp[2405];
        for(int i=1;i<=47;i++){
            for(int j=1;j<=47;j++){
                mp[(i-1)*47+j][i]=1;
                for(int k=1,g=(i+j)%47+1;k<47;k++,g=(g+j)%47+1)
                    mp[(i-1)*47+j][k*47+g]=1;
            }
        }
        for(int i=1;i<=n;i++,cout<<"\n")
        for(int j=1;j<=n;j++)cout<<mp[i][j];
    }
}