牛客周赛96补题 D F

D 数学

已知有两根，用韦达公式

• $x^2-px+q=0\to x_1+x_2=p,x_1{x}_2=q$
• $x_1+x_2+x_1{x}_2+1=p+q+1=k+1\to (x_1+1)(x_2+1)=k+1$

赛时舍近求远去推了一大堆求根公式…

void solve()
{int k;cin>>k;for(int i=1;i*i<=(k+1);i++){if((k+1)%i==0){int j=(k+1)/i;int a=i-1,b=j-1;if(a>0&&b>0){cout<<a+b<<' '<<a*b<<endl;return;}}}cout<<-1<<endl;
}

F 构造 异或和

• $a_{i,j}$在$R_2、L_2$都被异或进去了，所以$\underset{i=1}{\overset{m}{⨁}}{R}_i\oplus \underset{j=1}{\overset{n}{⨁}}{C}_j=0$
  
• R、C是n+m的排列，根据前缀异或和性质，下有打表
  • $p\%4=1,\underset{x=1}{\overset{p}{⨁}}x=1$
  • $p\%4=2,\underset{x=1}{\overset{p}{⨁}}x=p+1$
  • $p\%4=3,\underset{x=1}{\overset{p}{⨁}}x=0$
  • $p\%4=0,\underset{x=1}{\overset{p}{⨁}}x=p$
• 可以确定合法条件：(n+m)%4==3
  
• 构造：
  • $p\oplus 0=p$，先构造1~n-1，n+1~n+m-1部分
  • 对$a_{n,m}$，利用$p\oplus p=0$和$0=\underset{x=1}{\overset{p}{⨁}}x,p\%4=3$的性质，凑出$a_{n,m}$
    

void solve()
{//打表代码// int x=0;// forr(i,1,16){//     x^=i;//     cout<<i<<' '<<x<<endl;// }int n,m;cin>>n>>m;if((n+m)%4!=3)return cout<<-1<<endl,void();vector<vector<int> >a(n+1,vector<int>(m+1,0));forr(i,1,n-1){a[i][m]=i;}forr(j,1,m-1){a[n][j]=n+j;a[n][m]^=(n+j);}// cout<<a[n][m]<<endl;a[n][m]^=n;forr(i,1,n){forr(j,1,m)cout<<a[i][j]<<' ';cout<<endl;}
}