\[\text{NOIP模拟赛-2023.10.13} \]
（牛客场）
T1 矩阵交换
一个 \(n\times m\) 的矩阵 \(A\)，\(A_{i,j}\in\{1,2,3\}\)。每次可以任意交换两行，问能否使每列单调不降
\(T,n\leq 100\)
签到题，写了 \(1.5\rm h\)，纯唐
code
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=110;
int T,n,m,a[N][N],cnt;
struct node{int id,val;}ans[N];
vector <pii> pos;
pii tmp[N];
void init()
{
memset(a,0,sizeof(a));
int len=pos.size();
for(int i=0; i<len; i++)
pos.pop_back();
}
void mian()
{
init();
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
ans[i].id=i;
for(int j=1; j<=m; j++)
scanf("%d",&a[i][j]);
}
pos.push_back({1,n});
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
ans[j].val=a[ans[j].id][i];
cnt=0;
for(auto v:pos)
{
sort(ans+v.first,ans+v.second+1,[](node x,node y){return x.val<y.val;});
int l=v.first,r=v.first;
for(int j=v.first+1; j<=v.second; j++)
{
r++;
if(a[ans[j].id][i]!=a[ans[j-1].id][i])
tmp[++cnt]={l,r-1},l=r;
}
tmp[++cnt]={l,r};
}
int len=pos.size();
for(int j=0; j<len; j++)
pos.pop_back();
for(int j=1; j<=cnt; j++)
pos.push_back(tmp[j]);
}
for(int i=1; i<=m; i++)
{
for(int j=2; j<=n; j++)
{
if(a[ans[j].id][i]<a[ans[j-1].id][i])
{
printf("NO\n");
return;
}
}
}
printf("YES\n");
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&T);
while(T--)
mian();
return 0;
}
T2 砖块摆放
原题？？[ARC117C] Tricolor Pyramid
好题
这个操作很难直接做，所以考虑将操作转化成一些数字上的操作
一个牛逼的转化是令 \(A,B,C\) 分别等于 \(0,1,2\)，每次操作即 \(2(x+y)\bmod 3\)
而我在考场上贺了 SError 的做法，令 \(A,B,C\) 分别等于 \(1,2,4\)，每次操作即求 \((xy)^{-1}\pmod 7\)
然后通过枚举与打表可以发现，对于第 \(i\) 个砖块来说，对顶上的贡献即 \(a_i^{\binom{n-1}{i-1}}\) 如果 \(n\) 是偶数的话还要再求一次逆元
记 \(x=\dbinom{n-1}{i-1}\)，因为 \(x\) 很大，所以欧拉降幂得 \(a_i^{x\bmod \varphi(7)}=a_i^{x\bmod 6}\)。所以即求 \(\dbinom{n-1}{i-1} \bmod 6\)。由于 \(6\) 不是质数，所以不能直接用 \(\rm Lucas\) 定理，但是我们可以先对 \(2\) 和 \(3\) 用 \(\rm Lucas\) 定理，再用中国剩余定理求出来
代码不难写
code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+10,MOD=7;
int T,n,a[N];
char s[N];
int c[5][5];
int ksm(int x,int y)
{
int res=1;
while(y)
{
if(y&1)
res=1LL*res*x%MOD;
x=1LL*x*x%MOD;
y>>=1;
}
return res;
}
void prework()
{
c[0][0]=1;
c[1][0]=c[1][1]=1;
c[2][0]=1; c[2][1]=2; c[2][2]=1;
c[3][0]=1; c[3][1]=c[3][2]=3; c[3][3]=1;
}
int C(int x,int y,int p)
{
return c[x][y];
}
int lucas(int x,int y,int p)
{
if(y==0)
return 1;
if(x<p && y<p)
return C(x%p,y%p,p);
return 1LL*C(x%p,y%p,p)*lucas(x/p,y/p,p)%p;
}
int crt(int a1,int a2)
{
int m=6,m1=2,m2=3;
int M1=3,M2=2;
int t1=ksm(M1,m1-2),t2=ksm(M2,m2-2);
int ans=1LL*(1LL*a1*M1%m*t1%m+1LL*a2*M2%m*t2%m)%m;
return ans;
}
void mian()
{
scanf("%d%s",&n,s+1);
for(int i=1; i<=n; i++)
{
if(s[i]=='A')
a[i]=1;
else if(s[i]=='B')
a[i]=2;
else
a[i]=4;
}
int ans=1;
for(int i=1; i<=n; i++)
{
int ind1=lucas(n-1,i-1,2),ind2=lucas(n-1,i-1,3),res=1;
int ind=crt(ind1,ind2);
res=ksm(a[i],ind);
if(n%2==0)
res=ksm(res,MOD-2);
ans=1LL*ans*res%MOD;
}
if(ans==1)
puts("A");
else if(ans==2)
puts("B");
else
puts("C");
}
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
prework();
scanf("%d",&T);
while(T--)
mian();
return 0;
}