省选模拟 19/10/02

省选模拟 19/10/02

#include#define N 6000#define M 500050using namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}typedef long long ll;int n, m, len;struct data{ int delta[4]; } d[2][55];ll c[32][32];int cnt = 0, ans = 0;int low[N], dfn[N], sign, sta[N], insta[N], top, sc[N], node;ll val[N], f[N];int id[32][32][32];struct Node{ int a, b, c, d; } pos[N];int first[N], nxt[M], to[M], tot;void add(int x, int y){ if(x == y) return; nxt[++tot] = first[x], first[x] = tot, to[tot] = y;}ll calc(int x){ Node now = pos[x]; return c[n][now.a + now.b] * c[now.a + now.b][now.a] * c[now.c + now.d][now.d];}void dfs(int u){ low[u] = dfn[u] = ++sign; sta[++top] = u; insta[u] = 1; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(!dfn[t]) dfs(t), low[u] = min(low[u], low[t]); else if(insta[t] && dfn[t] < low[u]) low[u] = dfn[t]; } if(low[u] == dfn[u]){ ++node; do{ insta[sta[top]] = 0; sc[sta[top]] = node; val[node] += calc(sta[top]); } while(sta[top--] != u); }}vector v[N], vv[N];int exi[N][N], du[N];int p[N], res;ll topsort(){ queue q; for(int i = 1; i <= node; i++) if(!du[i]) q.push(i); while(!q.empty()){ int x = q.front(); q.pop(); p[++res] = x; for(int i = 0; i < v[x].size(); i++){ int t = v[x][i]; if(--du[t] == 0) q.push(t); } } ll ans = 0; for(int i = res; i >= 1; i--){ f[p[i]] += val[p[i]]; ans = max(ans, f[p[i]]); for(int j = 0; j < vv[p[i]].size(); j++){ int t = vv[p[i]][j]; f[t] = max(f[t], f[p[i]]); } } return ans;}int main(){ n = read(), m = read(); c[0][0] = 1; for(int i = 1; i <= n; i++){ c[i][0] = 1; for(int j = 1; j <= i; j++) c[i][j] = c[i-1][j] + c[i-1][j-1]; } for(int i = 1; i <= m; i++){ string a, b; cin >> a >> b; int l = a.length(); for(int j = 0; j < l; j++) ++d[0][i].delta[a[j] - 'A'], ++d[1][i].delta[b[j] - 'A']; } for(int a = 0; a <= n; a++) for(int b = 0; a + b <= n; b++) for(int c = 0; a + b + c <= n; c++){ int d = n - a - b - c; id[a][b][c] = ++len; pos[len] = (Node){a, b, c, d}; } for(int i = 1; i <= len; i++){ for(int j = 1; j <= m; j++){ Node nxt = (Node){ pos[i].a - d[0][j].delta[0], pos[i].b - d[0][j].delta[1], pos[i].c - d[0][j].delta[2], pos[i].d - d[0][j].delta[3] }; if(nxt.a < 0 || nxt.b < 0 || nxt.c < 0 || nxt.d < 0) continue; add(i, id[nxt.a + d[1][j].delta[0]][nxt.b + d[1][j].delta[1]][nxt.c + d[1][j].delta[2]]); } } for(int i = 1; i <= len; i++) if(!dfn[i]) dfs(i); for(int i = 1; i <= len; i++){ for(int e = first[i]; e; e = nxt[e]){ int t = to[e]; if(sc[t] != sc[i] && !exi[sc[i]][sc[t]]) v[sc[i]].push_back(sc[t]), vv[sc[t]].push_back(sc[i]), exi[sc[i]][sc[t]] = 1, ++du[sc[t]]; } } cout << topsort(); return 0;}

#include#define N 2050using namespace std;typedef long long ll;const ll Base = 31, Mod = 1e9 + 7;ll seed[N];ll add(ll a, ll b){ return a + b >= Mod ? a + b - Mod : a + b;}ll mul(ll a, ll b){ return a * b % Mod;}void Add(int &a, int b){ a = add(a, b);}struct Hash{ ll h[N]; void make(int n, char *s){ for(int i = 1; i <= n; i++) h[i] = add(mul(h[i-1], Base), s[i]); } ll ask(int l, int r){ return add(h[r], Mod - mul(h[l-1], seed[r - l + 1]));}} pre[2], suf[2], S;int n, m;char a[2][N], s[N];int f[2][N][N];int Solve(int flg){ int sum = 0; memset(f, 0, sizeof(f)); for(int j = 1; j <= n; j++){ f[0][j][0] = f[1][j][0] = 1; for(int i = 0; i < 2; i++) for(int k = 2; k <= min(m/2, n - j + 1); k++) if(S.ask(m - k * 2 + 1, m - k) == pre[i].ask(j, j + k - 1) && S.ask(m - k + 1, m) == suf[i ^ 1].ask(n - (j + k - 1) + 1, n - j + 1)){ if(2 * k != m || flg) Add(sum, f[i][j][m - k * 2]); } for(int i = 0; i < 2; i++) for(int k = 2; k <= min(m/2, j); k++) if(S.ask(k + 1, k * 2) == pre[i].ask(j - k + 1, j) && S.ask(1, k) == suf[i^1].ask(n - j + 1, n - (j - k + 1) + 1)){ if(2 * k != m || flg) Add(f[i][j + 1][2 * k], 1); } for(int i = 0; i < 2; i++) for(int k = 0; k < m; k++) if(a[i][j] == s[k + 1]){ Add(f[i][j + 1][k + 1], f[i][j][k]); if(k + 2 <= m && a[i ^ 1][j] == s[k + 2]) Add(f[i ^ 1][j + 1][k + 2], f[i][j][k]); } for(int i = 0; i < 2; i++) Add(sum, f[i][j + 1][m]); } return sum;}int main(){ seed[0] = 1; for(int i = 1; i <= N-50; i++) seed[i] = mul(seed[i-1], Base); scanf("%s%s%s", a[0] + 1, a[1] + 1, s + 1); n = strlen(a[0] + 1); m = strlen(s + 1); for(int i = 0; i < 2; i++){ pre[i].make(n, a[i]); reverse(a[i] + 1, a[i] + n + 1); suf[i].make(n, a[i]); reverse(a[i] + 1, a[i] + n + 1); } S.make(m, s); int ans = 0; Add(ans, Solve(1)); if(m > 1){ reverse(s + 1, s + m + 1); S.make(m, s); Add(ans, Solve(0)); if(m == 2){ for(int i = 0; i < 2; i++) for(int j = 1; j <= n; j++) if(a[i][j] == s[1] && a[i ^ 1][j] == s[2]) Add(ans, Mod - 1); } } cout << ans; return 0;}

#include#define N 20000050using namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}const int Mod = 998244353;int add(int a, int b){ return (a + b) >= Mod ? a + b - Mod : a + b;}int mul(int a, int b){ return 1ll * a * b % Mod;}const int inv2 = (Mod+1)/2, inv3 = (Mod+1)/3, inv6 = mul(inv2, inv3), inv4 = mul(inv2, inv2);int power(int a, int b){ int ans = 1; for(;b;b>>=1){ if(b&1) ans = mul(ans, a); a = mul(a, a);} return ans;}int prim[N / 8], tot, f[N]; bool isp[N];int n, m;const int up = 20000000, M = 200050;int g[N], inv[M + 10];void prework(){ f[1] = 1; for(int i = 2; i <= up; i++){ if(!isp[i]) prim[++tot] = i, f[i] = Mod - power(i, m); for(int j = 1; j <= tot; j++){ if(prim[j] * i > up) break; isp[prim[j] * i] = 1; if(i % prim[j] == 0){ f[i * prim[j]] = 0; break; } f[i * prim[j]] = mul(f[i], f[prim[j]]); } } for(int i = 2; i <= up; i++) f[i] = add(f[i-1], f[i]); for(int i = 1; i <= up; i++) g[i] = add(g[i-1], power(i, m)); inv[0] = inv[1] = 1; for(int i = 2; i <= m + 5; i++) inv[i] = mul(Mod-Mod/i, inv[Mod%i]); for(int i = 2; i <= m + 5; i++) inv[i] = mul(inv[i], inv[i-1]);}map mp;int pre[M + 10], suf[M + 10];map G;int calc(int x){ if(x <= up) return g[x]; if(G[x]) return G[x]; pre[0] = suf[m + 5 + 1] = 1; for(int i = 1; i <= m + 5; i++) pre[i] = mul(pre[i-1], x - i); for(int i = m + 5; i >= 1; i--) suf[i] = mul(suf[i+1], x - i); int ans = 0; for(int i = 1; i <= m + 5; i++){ int tmp = mul(g[i], mul(mul(inv[i-1], inv[m+5-i]), mul(pre[i-1], suf[i+1]))); ans = ((M-i) & 1) ? add(ans, Mod - tmp) : add(ans, tmp); } return G[x] = ans;}int Solve(int n){ if(n <= up) return f[n]; if(mp[n]) return mp[n]; int ans = 1; int las = 1, nxt = 0; for(int l = 2, r; l <= n; l = r+1){ int v = n / l; r = n / v; int t = Solve(v); nxt = calc(r); ans = add(ans, Mod - mul(add(nxt, Mod - las), t)); las = nxt; } return mp[n] = ans;}int main(){ n = read(), m = read(); if(n <= 10000000){ int ans = 1; f[1] = 1; for(int i = 2; i <= n; i++){ if(!isp[i]) prim[++tot] = i, f[i] = Mod - power(i, m); for(int j = 1; j <= tot; j++){ if(prim[j] * i > n) break; isp[prim[j] * i] = 1; if(i % prim[j] == 0){ f[i * prim[j]] = 0; break; } f[i * prim[j]] = mul(f[i], f[prim[j]]); } ans = add(ans, f[i]); } cout << ans; } else{ prework(); cout << Solve(n); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。