省选模拟 19/10/09

省选模拟 19/10/09

​​区间积​​​

#include#define N 205using 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 = 1000000007;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; }int power(int a, int b){ int ans = 1; for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a); return ans; }int n, a[N], Q;struct data{ int l, r, ans;} q[N];int b, f[N][N], g[N][N], fa[N], val[N], inv[N]; vector tmp;int ans;int find(int x){ if(x == fa[x]) return x; int t = find(fa[x]); val[x] = 1ll * val[fa[x]] * val[x] % b; return fa[x] = t;}bool merge(int x, int y, int z){ int fx = find(x), fy = find(y); if(fx ^ fy){ fa[fx] = fy; val[fx] = 1ll * val[y] * inv[val[x]] * inv[z] % b; return true; } else return 1ll * val[y] * inv[val[x]] % b == z;}int F(int l, int r, vector v){ int &res = f[l][r]; if(v.empty()) return res = power(b - 1, r - l + 1); if(~res) return res; for(int i = l - 1; i <= r; i++) fa[i] = i, val[i] = 1; for(int i = 0; i < v.size(); i++){ data now = v[i]; if(now.ans == 0) return res = 0; if(!merge(now.l - 1, now.r, now.ans)) return res = 0; } int cnt = 0; for(int i = l-1; i <= r; i++) if(fa[i] == i) cnt++; return power(b - 1, cnt - 1);}int G(int l, int r, vector v){ int &res = g[l][r]; if(v.empty()) return res = power(b, r - l + 1); if(~res) return res; res = F(l, r, v); for(int i = l; i <= r; i++){ bool flg = 0; vector L, R; for(int j = 0; j < v.size(); j++){ data now = v[j]; if(now.l <= i && i <= now.r) if(now.ans != 0) flg = 1; if(now.r < i) L.push_back(now); if(now.l > i) R.push_back(now); } if(flg) continue; res = add(res, mul(F(l, i-1, L), G(i+1, r, R))); } return res;}int main(){ n = read(); Q = read(); for(int i = 1; i<= Q; i++){ q[i].l = read() + 1; q[i].r = read() + 1; q[i].ans = read(); } b = 2; memset(f, -1, sizeof(f)); memset(g, -1, sizeof(g)); tmp.clear(); for(int i = 1; i <= Q; i++) tmp.push_back((data){q[i].l, q[i].r, q[i].ans % 2}); inv[1] = 1; ans = G(1, n, tmp); b = 5; memset(f, -1, sizeof(f)); memset(g, -1, sizeof(g)); tmp.clear(); for(int i = 1; i <= Q; i++) tmp.push_back((data){q[i].l, q[i].r, q[i].ans % 5}); inv[1] = 1; inv[2] = 3; inv[3] = 2; inv[4] = 4; ans = mul(ans, G(1, n, tmp)); cout << ans; return 0;}

​​最短路​​​

// 50 pts#include#define N 405using 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;}int n, p;const int Mod = 998244353, INF = 1e9;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;}void Add(int &a, int b){ a = add(a, b);}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 f[N][N][N]; // 有 i 个点，j 层，最后一层有 k 个 的概率 int fac[N], inv[N], pw[N], p1[N][N], p2[N][N];void prework(){ fac[0] = fac[1] = inv[0] = inv[1] = 1; for(int i = 2; i <= n; i++) fac[i] = mul(fac[i-1], i), inv[i] = mul(Mod-Mod/i, inv[Mod%i]); for(int i = 2; i <= n; i++) inv[i] = mul(inv[i], inv[i-1]); pw[0] = 1; for(int i = 1; i <= n; i++) pw[i] = mul(pw[i-1], p); for(int i = 1; i <= n; i++) for(int j = 0; j <= n; j++) p1[i][j] = power(add(1, Mod - pw[i]), j); // 至少联通 for(int i = 1; i <= n; i++) for(int j = 0; j <= n; j++) p2[i][j] = power(p, i * j); // 不连通 }int C(int n, int m){ if(n < 0 || m < 0 || n < m) return 0; return mul(fac[n], mul(inv[n-m], inv[m]));}int main(){ n = read(), p = read(); p = mul(1e6 - p, power(1e6, Mod - 2)); prework(); f[1][1][1] = 1; for(int i = 1; i <= n-1; i++){ for(int j = 1; j <= i; j++){ for(int k = 1; k <= i; k++){ if(f[i][j][k]){ for(int l = 1; l <= n - i - 1; l++){ int tmp = mul(p1[k][l], mul(p2[k][n-i-l], C(n-i-1, l))); Add(f[i + l][j + 1][l], mul(f[i][j][k], tmp)); } } } } } int ans = 0; for(int i = 1; i <= n-1; i++){ for(int j = 1; j <= i; j++){ for(int k = 1; k <= i; k++){ if(f[i][j][k]){ Add(ans, mul(j, mul(add(1, Mod - pw[k]), f[i][j][k]))); Add(ans, mul(mul(p2[n-i][k], f[i][j][k]), INF % Mod)); } } } } cout << mul(mul(ans, n-1), power(1e6, n*n)); return 0;}

// 100 pts#include#define N 405using 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;}int n, p;const int Mod = 998244353, INF = 1e9;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;}void Add(int &a, int b){ a = add(a, b);}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 f[N][N], e[N][N];int fac[N], inv[N], pw[N], p1[N][N], p2[N][N];void prework(){ fac[0] = fac[1] = inv[0] = inv[1] = 1; for(int i = 2; i <= n; i++) fac[i] = mul(fac[i-1], i), inv[i] = mul(Mod-Mod/i, inv[Mod%i]); for(int i = 2; i <= n; i++) inv[i] = mul(inv[i], inv[i-1]); pw[0] = 1; for(int i = 1; i <= n; i++) pw[i] = mul(pw[i-1], p); for(int i = 1; i <= n; i++) for(int j = 0; j <= n; j++) p1[i][j] = power(add(1, Mod - pw[i]), j); // 至少联通 for(int i = 1; i <= n; i++) for(int j = 0; j <= n; j++) p2[i][j] = power(p, i * j); // 不连通 }int C(int n, int m){ if(n < 0 || m < 0 || n < m) return 0; return mul(fac[n], mul(inv[n-m], inv[m]));}int main(){ n = read(), p = read(); p = mul(1e6 - p, power(1e6, Mod - 2)); prework(); f[1][1] = 1; e[1][1] = 0; for(int i = 1; i <= n-1; i++){ for(int j = 1; j <= i; j++){ if(f[i][j]){ for(int k = 1; k <= n - i - 1; k++){ int tmp = mul(p1[j][k], mul(p2[j][n-i-k], C(n-i-1, k))); Add(f[i + k][k], mul(f[i][j], tmp)); Add(e[i + k][k], mul(add(e[i][j], f[i][j]), tmp)); } } } } int ans = 0; for(int i = 1; i <= n-1; i++){ for(int j = 1; j <= i; j++){ if(f[i][j]){ Add(ans, mul(add(1, Mod - pw[j]), add(f[i][j], e[i][j]))); Add(ans, mul(mul(p2[n-i][j], f[i][j]), INF % Mod)); } } } cout << mul(mul(ans, n-1), power(1e6, n*n)); return 0;}

T3：Burnside，咕咕咕

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