A.digits 2
题意：给你一个n，要求输出一个每一位数字之和能整除n且其本身也能整除n的数。n不超过100，要求的数不超过10000位数。
题解：直接将n输出n次。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
int T,n;
for (scanf("%d",&T);T--;) {
scanf("%d",&n);
for (int i = ; i < n; i++)
printf("%d",n);
printf("\n");
}
return ;
}
B.generator 1
题意：已知x0,x1,a,b,n,mod，xi = a*xi-1 + b*xi-2，求xn%mod
题解：矩阵快速幂，把以二为单位倍增改为以十位单位
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 2
const int N = 1e6 + ;
struct Matrix {
ll ma[maxn][maxn];
Matrix() {
memset(ma,, sizeof(ma));
}
}A,E;
char s[N];
ll mod;
Matrix mul(Matrix A,Matrix B) {
Matrix C;
for(int i=;i<maxn;i++)
for(int j=;j<maxn;j++)
for(int k=;k<maxn;k++)
C.ma[i][j]=(C.ma[i][j]+(A.ma[i][k]*B.ma[k][j]+mod)%mod)%mod;
return C;
}
Matrix pow_mod() {
int len = strlen(s);
for (int i = len - ; i >= ; i--) {
Matrix C = E;
int a = s[i] - '';
for (int j = ; j <= ; j++) {
if (j == a) A = mul(E,A);
E = mul(E ,C);
}
}
return A;
}
int main() {
scanf("%lld%lld%lld%lld%s%lld",&A.ma[][],&A.ma[][],&E.ma[][],&E.ma[][],s,&mod);
E.ma[][] = ;
A = pow_mod();
printf("%lld\n", A.ma[][]);
return ;
}
G.subsequence 1
题意：告诉你两个由数字组成的字符串s,t，问s串中有多少个子序列所表示的数字比t所表示的数字大。（均不含前导0）
题解：当s的子序列长度比t长时，显然比t大；当子序列长度与t相等时，我们可以通过动态规划来求解。我们用dp[i][j]来表示s串的前i个和t串的前j个相同的方案数。用两层for循环来判断s串的第i为与t串的第j位的大小关系：前i-1个的情况包含在前i个的情况内，所以我们先把dp[i-1][j]赋值给dp[i][j]，当s[i] == t[j]时，s串的前i个和t串的前j个相同的方案数还要加上前i-1位和j-1位相同的情况dp[i-1][j-1]；当s[i]>t[j]时，前j-1位的选取情况为dp[i-1][j-1],第j位选i，最后m-j个显然在剩下的n-i个字符中任取m-j个都符合。最后我们再加上长度大于t的不包含前导零的子序列个数即可。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = + ;
const ll mod = ;
ll c[N][N],dp[N][N];
char s[N],t[N];
int main() {
int T,n,m;
c[][] = c[][] = c[][] = ;
for (int i = ; i <= ; i++) {
c[i][] = c[i][i] = ;
for (int j = ; j < i; j++)
c[i][j] = (c[i-][j-]+c[i-][j])%mod;
}
for (scanf("%d",&T);T--;) {
scanf("%d%d%s%s",&n,&m,s+,t+);
dp[][] = ;
ll ans = ;
for (int i = ; i <= n; i++) {
dp[i][] = ;
for (int j = ; j <= min(m,i); j++) {
dp[i][j] = dp[i-][j];
if (s[i] == t[j]) dp[i][j] = (dp[i][j]+dp[i-][j-])%mod;
else if (s[i] > t[j]) {
ans = (ans + c[n-i][m-j] * dp[i-][j-]%mod)%mod;
}
}
}
for (int i = ; i <= n; i++) {
if (s[i] == '') continue;
for (int j = m; j <= n-i; j++)
ans = (ans + c[n-i][j])%mod;
}
printf("%lld\n", ans);
}
return ;
}
H.subsequence 2
题意：有一个长度为n，由m个不同字符组成的字符串，给你m*(m-1)/2组数据，每组第一行给两个字符，给出这字符串中这两个字符一共有多少个，再按字符在字符串中出现的顺序输出。问是否能找到符合条件的字符串，不能的话输出-1，能的话随便输出一个符合条件的字符串。
题解：我们可以将这个字符串看成一个图，根据每个字符类型和它是第几个给它一个编号，再根据前后关系建边，最后通过拓扑序得到序列。要注意字符数量不等于n或者得到的拓扑序个数不等于n时输出-1。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4 + ;
char c[],s[N],t[N];
vector<int> V[N*];
int num[],du[N*];
int n,m,len;
bool topo() {
queue<int> q;
for (int i = ; i < ; i++)
if(num[i]> && du[i*+] == )
q.push(i*+);
int cnt = ;
while(q.size()){
int u = q.front();
q.pop();
s[cnt++] = (u-)/ + 'a';
if (cnt > n) return false;
for (int i = ; i < V[u].size(); i++)
if (--du[V[u][i]] == ) q.push(V[u][i]);
}
s[cnt] = '\0';
if (cnt == n) return true;
return false;
}
int main() {
scanf("%d%d",&n,&m);
m = m*(m-)/;
for (int i = ; i < m; i++) {
scanf("%s%d",c,&len);
if (len == ) continue;
scanf("%s",t);
int num0 = , num1 = ,fst = , id;
for (int j = ; j < len; j++) {
if (t[j] == c[]) {
num0++;
id = (t[j]-'a')* + num0;
}else {
num1++;
id = (t[j]-'a')* + num1;
}
if (fst) {
du[id]++;
V[fst].push_back(id);
}
fst = id;
}
if (!num[c[]-'a']) num[c[]-'a'] = num0;
if (!num[c[]-'a']) num[c[]-'a'] = num1;
}
int all = ;
for (int i = ; i < ; i++) all += num[i];
if (all != n) printf("-1\n");
else if (topo()) printf("%s\n", s);
else printf("-1\n");
return ;
}