#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define GET (ch>='0'&&ch<='9')
#define MAXN 100100
using namespace std;
int n,d,k;
bool flag;
int a[MAXN][110],sum[MAXN],b[MAXN],c[MAXN],top,num[110][110];
int f,ans;
void in(int &x)
{
    x=0;char ch=getchar();int flag=1;
    while (!GET)    flag=ch=='-'?-1:1,ch=getchar();
    while (GET) x=x*10+ch-'0',ch=getchar();x*=flag;
}
bool check(int i,int j)
{
    int ret=0;
    for (int l=1;l<=d;l++)  ret+=a[i][l]*a[j][l],ret%=k;
    return !ret;
}
int main()
{
    in(n);in(d);in(k);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=d;j++)  in(a[i][j]),a[i][j]%=k,sum[i]+=a[i][j]*a[i][j],sum[i]%=k;
    /*for (int i=1;i<=n;i++)
        for (int j=1;j<=d;j++)  in(a[i][j]),a[i][j]%=k,sum[i]+=a[i][j]*a[i][j];
    for (int i=1;i<=n;i++)  sum[i]%=k;*/
    if (k==2)
    {
        for (int i=1;i<=n;i++)
            for (int j=1;j<=d;j++)  b[j]+=a[i][j],b[j]%=k;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=d;j++)  c[i]+=a[i][j]*b[j],c[i]%=k;
        for (int i=1;i<=n;i++)  c[i]=(c[i]-sum[i]+k)%k;f=(n-1)%k;
        /*for (int i=1;i<=n;i++)
            for (int j=1;j<=d;j++)  b[j]+=a[i][j];
        for (int i=1;i<=d;i++)  b[i]%=k;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=d;j++)  c[i]+=a[i][j]*b[j];
        for (int i=1;i<=n;i++)  c[i]=(c[i]%k-sum[i]+(k<<1))%k;f=(n-1)%k;*/
    }
    else
    {
        for (int i=1;i<=d;i++)
            for (int j=1;j<=d;j++)  num[i][j]=++top;
        /*for (int i=1;i<=n;i++)
            for (int j=1;j<=d;j++)
                for (int l=1;l<=d;l++)  b[num[j][l]]+=a[i][j]*a[i][l];
        for (int i=1;i<=top;i++)    b[i]%=k;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=d;j++)  
                for (int l=1;l<=d;l++)  c[i]+=a[i][j]*a[i][l]*b[num[j][l]];
        for (int i=1;i<=n;i++)  c[i]=(c[i]%k-sum[i]*sum[i]+(k<<1))%k;f=(n-1)%k;*/
        for (int i=1;i<=n;i++)
            for (int j=1;j<=d;j++)
                for (int l=1;l<=d;l++)  b[num[j][l]]+=a[i][j]*a[i][l],b[num[j][l]]%=k;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=d;j++)  
                for (int l=1;l<=d;l++)  c[i]+=a[i][j]*a[i][l]*b[num[j][l]],c[i]%=k;
        for (int i=1;i<=n;i++)  c[i]=(c[i]-sum[i]*sum[i]+k)%k;f=(n-1)%k;
    }
    for (int i=1;i<=n;i++)
    {
        if (flag)   break;
        if (f!=c[i])    flag=1,ans=i;
    }
    if (!flag)  {puts("-1 -1");return 0;}
    for (int i=1;i<=n;i++)
        if (ans!=i&&check(ans,i))   {printf("%d %d\n",min(ans,i),max(ans,i));return 0;}
}

• Re:前排提示：这道题不能使用字典树做 (1094) pipipapasha 2023-10-22 12:16:32