赛时心态崩了，0pts遗憾离场……今天在学校冷静思考了下。发现B题思路其实很简单，不过A题怎么也没有想到，回来看了题解，其实思路也很简单，不过是自己思考方向错了。看来打比赛心态很重要，如果能冷静下来思考结果会好很多。
果然算法竞赛不能被常理所束缚（笑）
A - 01 Matrix Again
行列从\(0\)开始，以\((i+j)\ mod\ n\)的值给每个格子编号，就像这样：
我们发现任选其中\(m\)种编号的位置填上\(1\)，得到的矩阵一定满足条件。那么具体在哪些编号上填\(1\)呢？
- 首先，输入给定的格子所在的编号一定要填。
- 其次，只按照第\(1\)条，可能凑不够\(m\)种，这种情况，就要在非输入给定的格子编号中任意挑选若干个，能凑成\(m\)种编号就行。
赛后一直思考这道题没有头绪是因为我的方向错了。当时我一直纠结于行和列的规律，却没有想到斜向考虑会如此简单。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
cin>>n>>m;
vector<bool> vis(n);
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
x--,y--;
vis[(x+y)%n]=1;
}
vector<int> ans;
for(int i=0;i<n;i++) if(vis[i]) ans.push_back(i);
for(int i=0;i<n;i++) if(!vis[i]&&ans.size()<m) ans.push_back(i);
cout<<n*m<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int x=i,y=(ans[j]-i+n)%n;
cout<<x+1<<" "<<y+1<<endl;
}
}
return 0;
}
B - Simple Math 4
显然的结论：
\(2^N\ mod\ (2^M-2^K)=2^{N-M+K}\ mod\ (2^M-2^K)\)。
所以循环直到\(N<M\)即可。这一步骤可以通过除法在\(O(1)\)的时间复杂度下解决。
接下来答案就是\(2^N\ mod\ 10\)，根据\(N\ mod\ 4\)的结果有\(4\)种答案：\(2,4,8,6\)，同样是\(O(1)\)。
但是需要注意的是得特判一种情况：n==m-1&&m-k==1。这意味着原式等于\(2^N\ mod\ 2^{M-1}\)。而\(N=M-1\)，所以这种情况需要输出\(0\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,k;
int mo[4]={6,2,4,8};
signed main(){
cin>>t;
while(t--){
cin>>n>>m>>k;
if(n>=m) n-=((n-m)/(m-k)+1)*(m-k);
if(m-k==1&&n==m-1) cout<<"0\n";
else cout<<mo[n%4]<<"\n";
}
return 0;
}