20210526模拟赛总结

T1

手玩如果有一个排列如何生成矩阵。发现最大值必不可能在矩阵中出现，次大值在左下半角只会出现一次。可以发现对于一个排列，将最大值与次大值交换位置所生成的矩阵相同，所以合法序列数一定是 2 。

然后就简单弄出排列，然后验证是否正确即可。

T2

不会搞，随便写了个暴力上去就过了……

T3

数位dp+状压思想。

使用unordered_map保存一下状态即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>

#define int long long

using namespace std;

int read()
{	int a = 0,x = 1;char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') x = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9') {a = a*10 + ch-'0';ch = getchar();}
	return a*x;
}
const int P=998244353;
int n,m,a[21],buc[11],g[30];
char s[30];
unordered_map<int,int>f,vis;
int calc()
{
	int ret = 0;
	for(int i = 0;i < 10;i ++) ret = ret*10 + buc[i];
	return ret;
}
int mp(int a,int b) {return a*m + b;}
void dfs(int u)
{
	if(vis[calc()]) return ;
	vis[calc()] = 1;
	for(int i = 0;i < 10;i ++) {
		if(!buc[i]) continue;
		buc[i] --;dfs(u-1);int tmp = calc();buc[i] ++;
		for(int j = 0;j < m;j ++) {
			(f[mp(calc(),j)] += f[mp(tmp,(g[u]*i%m+j)%m)]) %= P;
		}
	}
}

signed main()
{
	freopen("random.in","r",stdin);
	freopen("sol.out","w",stdout);
	scanf("%s",s+1);n = strlen(s+1);m = read();
	for(int i = 1;i <= n;i ++) ++ buc[a[i] = s[i] - '0'];
	g[1] = 1;for(int i = 2;i <= n;i ++) g[i] = g[i-1]*10%m;
	vis[0] = 1,f[0] = 1;
	for(int i = 1;i < 10;i ++) {
		if(!buc[i]) continue;
		buc[i] --;dfs(n-1);int tmp = calc();buc[i] ++;
		for(int j = 0;j < m;j ++) {
			(f[mp(calc(),j)] += f[mp(tmp,(g[n]*i%m+j)%m)]) %= P;
		}
	}
	printf("%lld
",f[mp(calc(),0)]);
}