当前位置: 首页 > news >正文

Say 题选记 (10.19 - 10.25)

P3702 [SDOI2017] 序列计数

首先至少 1 个质数可以容斥成随便选 - 只选合数。然后注意到第二维很小,直接矩阵快速幂即可。

Code
#include <bits/stdc++.h>
using namespace std;
const int M = 2e7 + 5, K = 1e2 + 5, mod = 20170408;
typedef long long ll;
int n, m, p, pri[M], cnt;
ll num[K], npri[K];
bitset<M> vis;
void add(ll &x, ll y){ (x += y) %= mod;}
struct matrix{ll m[K][K];matrix(){ memset(m, 0, sizeof(m)); }  matrix operator * (const matrix &x){matrix ret;for(int i = 0; i < p; ++i){for(int j = 0; j < p; ++j){for(int k = 0; k < p; ++k){add(ret.m[i][j], m[i][k] * x.m[k][j]);}} } return ret;}
}a, b, f; 
void init(){vis[1] = 1;for(ll i = 2; i <= m; ++i){if(!vis[i]) pri[++cnt] = i;for(ll j = 1; j <= cnt; ++j){if(i * pri[j] > m) break;vis[i * pri[j]] = 1;if(i % pri[j] == 0) break;}}
}
matrix qpow(matrix a, int b){matrix ret;for(int i = 0; i < p; ++i) ret.m[i][i] = 1;for(; b; b >>= 1, a = a * a){if(b & 1) ret = ret * a;}return ret;
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);cin >> n >> m >> p;init();for(int i = 1; i <= m; ++i){num[i % p]++;if(vis[i]) npri[i % p]++;} for(int i = 0; i < p; ++i){for(int j = 0; j < p; ++j){a.m[i][j] = num[(j - i + p) % p];b.m[i][j] = npri[(j - i + p) % p];}}f.m[0][0] = 1;matrix A = f * qpow(a, n), B = f * qpow(b, n);cout << (A.m[0][0] - B.m[0][0] + mod) % mod;return 0;
}

P5358 [SDOI2019] 快速查询

注意一个细节。对于单点赋值,由于我们最后查单点的时候会带上标记,也就是 \(a_i \times mult + addt\)。而对这个点进行赋值的时候,以前的标记不应产生影响,因此应该把其赋为 \(\frac{v - addt}{mult}\)

Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e7 + 19;
unordered_map<int, int> a;
int val, sum, addt, mult = 1, n, q, t, inv[mod];
void assign(int k){k = (k % mod + mod) % mod;a.clear();val = k, sum = 0, addt = 0, mult = 1;
}
void mul(int k){k = (k % mod + mod) % mod;if(k == 0) return assign(0);(addt *= k) %= mod, (mult *= k) %= mod;(val *= k) %= mod, (sum *= k) %= mod; 
}
void add(int k){k = (k % mod + mod) % mod;(addt += k) %= mod;(val += k) %= mod;(sum += 1ll * a.size() * k) %= mod;
}
int qry(int x){if(!a.count(x)) return val;return (a[x] * mult % mod + addt) % mod;
}
int qry(){ return ((val * (n - 1ll * a.size()) % mod + sum) % mod + mod) % mod; }
void upd(int x, int k){k = (k % mod + mod) % mod;if(a.count(x)) (sum += k - qry(x) + mod) %= mod;else (sum += k) %= mod;mult = (mult % mod + mod) % mod;a[x] = ((k - addt + mod) % mod * inv[mult]) % mod;
}
struct op{int typ, x, k;
}Op[100005];
int x[105], y[105];
signed main(){cin.tie(nullptr)->sync_with_stdio(0);cin >> n >> q;inv[1] = 1;for(int i = 2; i < mod; ++i){inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;}for(int i = 1; i <= q; ++i){cin >> Op[i].typ;if(Op[i].typ != 6){cin >> Op[i].x;if(Op[i].typ == 1) cin >> Op[i].k;}}cin >> t;for(int i = 1; i <= t; ++i) cin >> x[i] >> y[i];int ans = 0;for(int i = 1; i <= t; ++i){for(int j = 1; j <= q; ++j){int idx = (x[i] + j * y[i]) % q + 1;switch(Op[idx].typ){case 1: upd(Op[idx].x, Op[idx].k); break;case 2: add(Op[idx].x); break;case 3: mul(Op[idx].x); break;case 4: assign(Op[idx].x); break;case 5: (ans += qry(Op[idx].x)) %= mod; break;case 6: (ans += qry()) %= mod; break;} }}cout << (ans % mod + mod) % mod;return 0;
}

P3230 [HNOI2013] 比赛

比较人类智慧的爆搜题。当比赛人数固定并且给定最终分数时,最终的方案数是固定的。因此可以考虑记忆化,边搜边把这个存下来。具体来说我们把最终分数进制哈希一下(由于一个人最多 27 分,30进制就行),然后注意还要把不同人数的区分开来,对于 0 的情况我们要进行占位,解决方法是全体 +1,避免出现 0。复杂度玄学。

Code
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef unsigned long long ull;
map<ull, int> f;
int n, b[15];
int dfs(int x, int y){if(x == n){ return b[x] == 0; }if(y > n){ if(b[x] != 0) return 0; vector<int> tmp;for(int i = x + 1; i <= n; ++i) tmp.emplace_back(b[i]);sort(tmp.begin(), tmp.end());ull hsh = 0;for(int i = 0; i < tmp.size(); ++i) hsh = hsh * 29 + tmp[i] + 1; if(f.find(hsh) == f.end()) f[hsh] = dfs(x + 1, x + 2); return f[hsh];}if(b[x] > (n - y + 1) * 3) return 0;int ret = 0;if(b[x] >= 3){b[x] -= 3;(ret += dfs(x, y + 1)) %= mod;b[x] += 3;}if(b[y] >= 3){b[y] -= 3;(ret += dfs(x, y + 1)) %= mod;b[y] += 3;}if(b[x] >= 1 && b[y] >= 1){b[x]--, b[y]--;(ret += dfs(x, y + 1)) %= mod;b[x]++, b[y]++;}return ret;
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> b[i];cout << dfs(1, 2);return 0;
}
http://www.hskmm.com/?act=detail&tid=36133

相关文章:

  • 宝塔面板
  • React Native 启动流程 (Android版)
  • 以TrustedInstaller/System用户运行软件
  • 10月21号
  • 机器学习基础 -- 线性回归模型
  • 泰勒展开
  • MySQL 创建和授权用户
  • 因果机器学习算法新进展解析
  • 软件工程作业三
  • CF2127 Atto Round 1 (Codeforces Round 1041, Div. 1 + Div. 2) 游记(VP)
  • 一键生成爆款文章,并自动发布!
  • 机器学习到深度学习发展历程
  • Java数据类型
  • [CF 516 E] Drazil and His Happy Friends
  • NVIDIA Triton服务器漏洞危机:攻击者可远程执行代码,AI模型最高权限告急
  • 2025-10-21
  • 个人骗分导论
  • Java三大特性
  • 高级程序设计第二次作业
  • 10月21日日记
  • home-assistant.-Adding integrations
  • Windows系统内存占用过高,且任务管理器找不到对应进程
  • NOIP 二十五
  • 理想婚姻
  • equal和hashcode
  • Ancestral Problem 题解
  • AWS IAM角色最佳实践:构建云安全的核心防线
  • 正睿 2025 NOIP 20连测 Day6
  • Hetao P5593 删 题解 [ 蓝 ] [ 线性 DP ] [ DFS 序 ] [ 虚树 ]
  • o(N^2)找出所有回文子串