比赛链接：https://ac.nowcoder.com/acm/contest/885#question
// 正式比赛我就A了一道水题，卡在B上，又卡在G上，最后去做立体几何又一直WA。等到队友过了一个G题的dp，然后集体自闭。
A - digits 2
题意：给定一个不超过100的正整数n，求一个不超过1e4位的能整除n且其数位和也整除n的数。
题解：直接输出n次n。
AC代码：略。
B - generator 1
题意：给定数列xn = a*xn-1 + b*xn-2，已知x1， x0， a，b， n， mod，求xn%mod。（ 1<=n<=10^(10^6) ）
题解：一看n这么大，就尝试求模mod的循环节，然后用矩阵快速幂求循环节以内即可。结果不熟悉模板调了很久样例都跑不出来。
直接用10进制的快速幂。官方题解说每位数要用2进制倍增计算，否则会T，我不信，A了。
AC代码：（注意n==1特判！！！pow()函数n==1返回单位矩阵是我自己弄错了）
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; ll x0, x1, a, b, mod; char n[1000100]; struct mat { ll m[2][2]; mat operator*(const mat& a) { mat b; b.m[0][0] = (m[0][0]*a.m[0][0] + m[0][1]*a.m[1][0])%mod; b.m[0][1] = (m[0][0]*a.m[0][1] + m[0][1]*a.m[1][1])%mod; b.m[1][0] = (m[1][0]*a.m[0][0] + m[1][1]*a.m[1][0])%mod; b.m[1][1] = (m[1][0]*a.m[0][1] + m[1][1]*a.m[1][1])%mod; return b; } }; const mat I = {1, 0, 0, 1}; mat pow() { // if(strlen(n)==1 && n[0]=='0') return I; A^0 == I mat A = {a, b, 1, 0}; mat res = I; for(int i=0;n[i];i++) { mat tmp = res*res; tmp = tmp*tmp; tmp = tmp*res; res = tmp*tmp; int t = n[i]-'0'; tmp = A; mat tmp2 = I; while(t) { if(t&1) tmp2 = tmp2*tmp; tmp = tmp*tmp; t >>= 1; } res = res*tmp2; // 用上面的计算快一点点 // for(int k=1;k<=t;k++) { // res = res*A; // } } return res; } int main() { cin>>x0>>x1>>a>>b; scanf("%s", n); cin>>mod; mat m = pow(); printf("%lld ", (m.m[1][0]*x1 + m.m[1][1]*x0)%mod); return 0; }
C - generator 2
题意：给定 n, x0, a, b, p，数列由递推式 xi = a*xi-1 + b 产生。有Q次询问，给定 v 求最小的 i 项使 xi = v % p;
思路：手算一下可得 xn = a^n*x0 + b(1+a+...+a^(n-1)) = a^n + b(a^n - 1)/( a - 1)
即求解 a^n * ( b / (a-1) + x0) = v + b / ( a - 1 ) % p
p 保证为素数，分别求逆元，问题变成了求解 a^x = b mod p 的裸题。
使用BSGS算法求对数，直接抄模板会T，需要改写一下（1. 增大baby step，减少查询复杂度 2. 并在同一组p下保留当前的map值）。
直接使用map会使复杂度乘上logn，手写map或采用unsorted_map才能过。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<cmath> using namespace std; typedef long long ll; ll n, x0, a, b, p; struct mymap { static const int N = (1<<22); int key[N], val[N]; int query(int x) { int i = x&(N-1); while(key[i]!=-1 && key[i]!=x) i = (i+1)&(N-1); return val[i]; } void update(int x, int v) { int i = x&(N-1); while(key[i]!=-1 && key[i]!=x) i = (i+1)&(N-1); key[i] = x, val[i] = v; } void clear() { memset(key, -1, sizeof(key)); memset(val, -1, sizeof(key)); } }; ll pow(ll a, ll n, ll p) { ll res = 1; while(n) { if(n&1) res = res * a % p; a = a * a % p; n >>= 1; } return res; } // a^x = b (mod p) // 输入a, b, p返回 x inline ll BSGS(ll a, ll b, ll p) { // inline 会优化300ms static ll lasta = -1; static mymap mp; ll m = min(p/2, (ll)sqrt(p*1000)); // 直接采用sqrt(p)会TLE，增大baby step，减少查询 ll v = 1; if(lasta!=a) { lasta = a; mp.clear(); for(int i=0;i<m;i++) { if(mp.query(v)==-1) mp.update(v, i); v = v * a % p; } } v = pow(a, p-1-m, p); for(ll i=0;i<p;i+=m) { // giant step int qr = mp.query(b); if(qr!=-1) return i + qr; b = b * v % p; } return -1; } int main() { int T; cin>>T; while(T--) { scanf("%lld %lld %lld %lld %lld", &n, &x0, &a, &b, &p); int q; scanf("%d", &q); while(q--) { ll v; scanf("%lld", &v); if(v==x0) { printf("0 "); continue; } if(a==0) { if(v==b) printf("1 "); else printf("-1 "); } else if(a==1) { if(b==0) printf("-1 "); ll invb = pow(b, p-2, p); v = (v-x0 + p)%p; ll ans = (v*invb)%p; printf("%lld ", ans<n?ans:-1); } else { ll ba_1 = b*pow(a-1, p-2, p) % p; ll inv = pow(ba_1+x0, p-2, p); ll ans = BSGS(a, (v+ba_1)*inv%p, p); printf("%lld ", ans<n?ans:-1); } } } return 0; }
D - generator 3
G - subsequence 1
注意组合数C[0][0]=1
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int maxn = 3010; const int mod = 998244353; ll dp[maxn]; // dp[j]表示前j个数都相等的方案数 int C[maxn][maxn]; char s[maxn], t[maxn]; int n, m; void init() { for(int i=0;i<maxn;i++) { C[i][i] = C[i][0] = 1; } for(int i=2;i<maxn;i++) { for(int j=1;j<i;j++) { C[i][j] = C[i-1][j] + C[i-1][j-1]; C[i][j] %= mod; } } } int main() { init(); int T; cin>>T; while(T--) { scanf("%d %d", &n, &m); scanf("%s%s", s+1, t+1); ll ans = 0; memset(dp, 0, sizeof(dp)); dp[0] = 1; for(int i=1;i<=n;i++) { if(s[i]!='0') { // 长度大于|t|的子序列 for(int j=m;j<=n-i;j++) ans = (ans + C[n-i][j]) % mod; } // 长度等于|t|, 在第j个字符上大于t的子序列数目 for(int j=1;j<=i&&j<=m;j++) if(s[i]>t[j]) ans = (ans + C[n-i][m-j]*dp[j-1]) % mod; // 注意倒序处理, 是因为前状态推得后状态 for(int j=min(i, m);j>=1;j--) { if(s[i]==t[j]) dp[j] = (dp[j] + dp[j-1]) % mod; } } printf("%lld ", ans); } return 0; }
H - subsequence 2
I - three points 1
题意：保证三边长度分别为a，b，c的三角形能放在长宽分别为w，h的矩形内，给出三角形的三点坐标。
题解：暴力枚举三角形三个端点是否放在原点，枚举三条边是否放在w和h边上。
WA代码：直接排序把最短边所对的顶点放在原点，然后尝试最长边在w和h边上。
AC代码：（注意精度！！！check函数)
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const double eps = 1e-8; int w, h; struct P { double x, y; }ans[4]; struct Edge { int l; int n1, n2; }e[4]; double coss[4]; bool check(double x, double y) { // 不写check直接与w，h比较就WA了 if(x<-eps || y<-eps) return false; if(x>w+eps) return false; if(y>h+eps) return false; return true; } int main() { int t; cin>>t; while(t--) { cin>>w>>h>>e[1].l>>e[2].l>>e[3].l; e[1].n1 = 1; e[1].n2 = 2; e[2].n1 = 1; e[2].n2 = 3; e[3].n1 = 2; e[3].n2 = 3; coss[1] = (e[1].l*e[1].l+e[2].l*e[2].l - e[3].l*e[3].l + 0.0)/(2*e[1].l*e[2].l); coss[2] = (e[1].l*e[1].l+e[3].l*e[3].l - e[2].l*e[2].l + 0.0)/(2*e[1].l*e[3].l); coss[3] = (e[2].l*e[2].l+e[3].l*e[3].l - e[1].l*e[1].l + 0.0)/(2*e[2].l*e[3].l); bool f = false; for(int i=1;i<=3 && !f;i++) { // 点i放在原点 ans[i].x = ans[i].y = 0; // 放在x轴方向上 for(int j=1;j<=3 && !f;j++) { // 取线段j if(i!=e[j].n1 && i!=e[j].n2) continue; int k = e[j].n1 + e[j].n2 - i; // 线段另一端点k if(e[j].l<=w) { ans[k].x = e[j].l; ans[k].y = 0; double x = e[4-k].l*coss[i]; double y = e[4-k].l*sin(acos(coss[i])); if(x>=0 && x<=w && y>=0 && y<=h) { ans[6-i-k].x = x; ans[6-i-k].y = y; f = true; } } else { ans[k].x = w; ans[k].y = sqrt(e[j].l*e[j].l - w*w); if(ans[k].y>h) continue; double ang = acos(coss[i]) + acos(1.0*w/e[j].l); double x = e[4-k].l*cos(ang); double y = e[4-k].l*sin(ang); if(check(x, y)) { ans[6-i-k].x = x; ans[6-i-k].y = y; f = true; } } } // 放在y轴方向上 for(int j=1;j<=3 && !f;j++) { // 取线段j if(i!=e[j].n1 && i!=e[j].n2) continue; int k = e[j].n1 + e[j].n2 - i; // 线段另一端点k if(e[j].l<=h) { ans[k].x = 0; ans[k].y = e[j].l; double y = e[4-k].l*coss[i]; double x = e[4-k].l*sin(acos(coss[i])); if(x>=0 && x<=w && y>=0 && y<=h) { ans[6-i-k].x = x; ans[6-i-k].y = y; f = true; } } else { ans[k].y = h; ans[k].x = sqrt(e[j].l*e[j].l - h*h); if(ans[k].x>w) continue; double ang = acos(coss[i]) + acos(1.0*h/e[j].l); double y = e[4-k].l*cos(ang); double x = e[4-k].l*sin(ang); if(check(x, y)) { ans[6-i-k].x = x; ans[6-i-k].y = y; f = true; } } } } for(int i=1;i<=3;i++) { printf("%.12lf %.12lf%c", ans[i].x, ans[i].y, i==3?' ':' '); } } return 0; }
（未完待补。。。）