A&B
随便做吧。
C
行列分开讨论。容易发现能交换这个条件具有传递性,那么找出连通块,每个连通块的贡献是块大小的阶乘,乘起来即可。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
const int N=60;
int a[N][N],c[N];
struct bcj
{
int f[N];
void init(int n){for(int i=1;i<=n;i++)f[i]=i;}
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
void merge(int x,int y){f[getf(y)]=getf(x);}
}t1,t2;
int p[N],c1[N],c2[N];
int main()
{
int n=read(),k=read();
p[0]=1;
for(int i=1;i<=n;i++)p[i]=(long long)p[i-1]*i%998244353;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=read();
t1.init(n),t2.init(n);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
bool f=1;
for(int l=1;l<=n;l++)f&=(a[i][l]+a[j][l]<=k);
if(f)t1.merge(i,j);
}
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
bool f=1;
for(int l=1;l<=n;l++)f&=(a[l][i]+a[l][j]<=k);
if(f)t2.merge(i,j);
}
}
for(int i=1;i<=n;i++)c1[t1.getf(i)]++,c2[t2.getf(i)]++;
int ans=1;
for(int i=1;i<=n;i++)ans=(long long)ans*p[c1[i]]%998244353,ans=(long long)ans*p[c2[i]]%998244353;
printf("%d",ans);
return 0;
}
*D
可以等价地看作这样一个操作:一个数初始为 \(0\),做 \(n\) 次操作,每次可以 \(x\gets x+1\) 然后任意除以一个 \(2^p\)(需要满足 \(2^p\mid x\)),问有多少种情况使得最后 \(x=n\)。这样就可以直接 dp 了。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
const int N=3010;
int f[N][N*2];
int main()
{
f[0][0]=1;
int n=read(),k=read();
for(int i=1;i<=n;i++)for(int j=i;j>=1;j--)f[i][j]=f[i-1][j-1]+f[i][j*2],f[i][j]%=998244353;
printf("%d",f[n][k]);
return 0;
}
E
打表找规律可以发现:当 \(\min\{i,j\}>4\) 时,\(a_{i,j}=a_{i-1,j-1}\),处理前四行、前四列即可。
//#pragma GCC optimize(3)
//#pragma GCC target("avx")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
const int N=3010;
int mex(int x,int y)
{
for(int i=0;i<=2;i++)
if(i!=x&&i!=y)return i;
return 0;
}
map<pair<int,int>,int> a;
#define mp make_pair
int b[N][N];
int main()
{
int n=read();
if(n<=3000)
{
int ans[3]={0,0,0};
for(int i=1;i<=n;i++)b[1][i]=read();
for(int i=2;i<=n;i++)b[i][1]=read();
for(int i=2;i<=n;i++)for(int j=2;j<=n;j++)b[i][j]=mex(b[i-1][j],b[i][j-1]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[b[i][j]]++;
printf("%d %d %d",ans[0],ans[1],ans[2]);
}
else
{
for(int i=1;i<=n;i++)a[mp(1,i)]=read();
for(int i=2;i<=n;i++)a[mp(i,1)]=read();
for(int i=2;i<=n;i++)a[mp(2,i)]=mex(a[mp(1,i)],a[mp(2,i-1)]);
for(int i=3;i<=n;i++)a[mp(i,2)]=mex(a[mp(i-1,2)],a[mp(i,1)]);
for(int i=3;i<=n;i++)a[mp(3,i)]=mex(a[mp(2,i)],a[mp(3,i-1)]);
for(int i=4;i<=n;i++)a[mp(i,3)]=mex(a[mp(i-1,3)],a[mp(i,2)]);
for(int i=4;i<=n;i++)a[mp(4,i)]=mex(a[mp(3,i)],a[mp(4,i-1)]);
for(int i=5;i<=n;i++)a[mp(i,4)]=mex(a[mp(i-1,4)],a[mp(i,3)]);
long long ans[3]={0,0,0};
for(int i=4;i<=n;i++)ans[a[mp(4,i)]]+=min(n-4,n-i);
for(int i=5;i<=n;i++)ans[a[mp(i,4)]]+=min(n-i,n-4);
for(map<pair<int,int>,int>::iterator it=a.begin();it!=a.end();it++)ans[it->second]++;
printf("%lld %lld %lld",ans[0],ans[1],ans[2]);
}
}
F
还没做。