数学相关模板-基础
反素数
求1-n以内约数最多的数
#include <iostream>
int p[16] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 };
unsigned long long n;
unsigned long long ans,
ans_num; // ans 为 n 以内的最大反素数（会持续更新），ans_sum 为
// ans的因子数。
// depth: 当前在枚举第几个素数
// temp: 当前因子数量为 num的时候的数值
// num: 当前因子数
// up：上一个素数的幂，这次应该小于等于这个幂次嘛
void dfs(int depth, unsigned long long temp, unsigned long long num, int up) {
if (depth >= 16 || temp > n) return;
if (num > ans_num) { // 更新答案
ans = temp;
ans_num = num;
}
if (num == ans_num && ans > temp) ans = temp; // 更新答案
for (int i = 1; i <= up; i++) {
if (temp * p[depth] > n)
break; // 剪枝：如果加一个这个乘数的结果比ans要大，则必不是最佳方案
dfs(depth + 1, temp *= p[depth], num * (i + 1),
i); // 取一个该乘数，进行对下一个乘数的搜索
}
return;
}
using std::cin;
using std::cout;
int main() {
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
cin >> n;
ans_num = 0;
dfs(0, 1, 1, 60);
cout << ans << " " << ans_num;
return 0;
}
(数，对应的约数个数)
- 1e5, 83160 128
- 1e7, 8648640 448
- 1e9, 735134400 1344
- 1e12, 963761198400 6720
[ABC248G] GCD cost on the tree
题目描述
给定一颗树有 \(n\) 个结点，每个结点上有一个权值 \(a_i\), 对于每条至少包含两个点的简单路径，它的贡献为 路径上点的数量(包括端点)\(\times\)路径上所有点的 \(a_i\)
的最大公约数(gcd)。
求所有简单路径的贡献之和，对 \(998244353\) 取模。
假设当前计算gcd为d的所有路径和长度，直接计算不好计算，我们可以计算所有d|x的路径长度和，然后再减掉d的倍数的影响即可。
因为1e5以内，约数最多的数只有128，因此每个数最多只会加入128次，那么我们对于每个d，我们完全可以将树建出来，然后利用统计sz计算每个点被经过多少次。
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define pi pair<ll,ll>
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define fi first
#define se second
using namespace std;
typedef long long ll;
const ll inf = 1ll << 60;
const int N = 5e5 + 10;
const ll mo = 998244353;
vector<int> tr[N];
ll n, a[N], x, y, f[N];
ll p[N], tot, v[N], num;
bool vis[N];
vector<int> t[N], d;
queue<int> q;
vector<int> e[N];
bool bz[N], in[N];
ll sz[N], g[N], sum, c[N], u[N], ans;
void work(int x, int pos) {
d.clear();
d.eb(1);
int z = v[x], l, r;
while (x != 1) {
z = v[x];
l = 0; r = d.size();
while (x % z == 0) {
x /= z;
fo(i, l, r - 1) d.eb(d[i] * z);
l = r; r = d.size();
}
}
for (auto x : d) t[x].eb(pos);
}
void ins(int x) {
q.push(x);
bz[x] = 1;
work(a[x], x);
}
void bfs() {
ins(1);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int v : tr[x]) {
if (!bz[v]) {
f[v] = x;
ins(v);
}
}
}
}
void add(ll& x, ll y) {
x = (x + y) % mo;
}
void dg(int x) {
add(num, (sum - sz[x]) * sz[x] % mo + g[x]);
for (int v : e[x]) dg(v);
}
void dfs(int x) {
sz[x] = 0;
ll s = 0;
for (int v : e[x]) {
dfs(v);
sz[x] += sz[v];
s += sz[v] * sz[v];
}
g[x] = sz[x] + (sz[x] * sz[x] - s) / 2;
sz[x]++;
}
void solve()
{
fo(i, 2, N - 1) {
if (!vis[i]) {
p[++tot] = i;
v[i] = i;
}
fo(j, 1, tot) {
if (i * p[j] >= N) break;
vis[i * p[j]] = 1;
if (i % p[j] == 0) {
v[i * p[j]] = p[j];
break;
}
else v[i * p[j]] = p[j];
}
}
cin >> n;
fo(i, 1, n) cin >> a[i];
fo(i, 1, n - 1) {
cin >> x >> y;
tr[x].eb(y);
tr[y].eb(x);
}
bfs();
// for (auto x : t[1]) cout << x << "\n";
// cout << "\n";
// fo(i, 1, n)cout << f[i] << "\n";
fd(i, 1e5, 1) {
for (auto x : t[i]) {
in[x] = 1;
if (in[f[x]]) e[f[x]].eb(x);
}
ll z = 0;
for (auto x : t[i]) {
if (!in[f[x]]) {
dfs(x);
sum = sz[x];
num = 0;
dg(x);
add(z, num);
}
}
fo(j, 2, 1e5 / i) {
z = (z - u[i * j]) % mo;
}
u[i] = z;
add(ans, z* i% mo);
for (auto x : t[i]) {
e[x].clear();
in[x] = 0;
}
}
ans = (ans % mo + mo) % mo;
cout << ans;
}
int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
欧拉定理
\((a,m)=1,a^{\varphi(m)} \equiv 1 \pmod m\)
扩展欧拉定理
当\((a,m)\neq 1\)时，
- \(b \lt \varphi(m),a^b \equiv a^b \pmod m\)
- \(b \ge \varphi(m),a^b \equiv {a^{b \,mod \, \varphi(m)+\varphi(m)}} \pmod m\)
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
#define pi pair<ll,ll>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
//typedef __int128 i128;
const int inf=1e9;
const ll mo1=1e9+9;
const ll mo2=1e9+7;
const ll P=131;
const ll Q=13331;
//const ll mo=1e9+7;
const int N=1e5+5;
char ch;
ll a,m,b;
ll power(ll a,ll b){
ll t=1,y=a;
while (b) {
if (b&1) t=t*y%m;
y=y*y%m;
b/=2;
}
return t;
}
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%lld %lld",&a,&m);
a%=m;
ll t=m,phi=m;
for (ll i=2;i*i<=m;i++) {
if (t%i==0) {
phi=phi/i*(i-1);
while (t%i==0) t/=i;
}
}
if (t!=1) phi=phi/t*(t-1);
bool flag=0;
char ch;
for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
for (;('0'<=ch && ch<='9');ch=getchar()) {
b=b*10+ch-'0';
if (b>=phi) {
b%=phi;
flag=1;
}
}
if (flag) printf("%lld\n",power(a,b+phi));
else printf("%lld\n",power(a,b));
return 0;
}
质因数分解
\(m[x]\)表示x的最小质因数
void work(int x){
e.clear();
e.push_back(1);
while (x!=1){
z=m[x];
l=0; r=e.size();
while (x%z==0) {
x/=z;
fo(i,l,r-1) e.push_back(e[i]*z);
l=r; r=e.size();
}
}
}
fwt相关
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
#define pi pair<ll,ll>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
typedef unsigned int uint;
//typedef __int128 i128;
const int inf = 1e9;
const ll mo1 = 1e9 + 9;
const ll mo2 = 1e9 + 7;
const ll P = 131;
const ll Q = 13331;
const ll mo = 998244353;
const int N = 1 << 20;
ll inv2, a[N], b[N], n, aa[N], bb[N], c[N];
void add(ll& x, ll y) {
x = (x + y) % mo;
}
void Or(ll* a, ll type) {
for (ll x = 2;x <= n;x <<= 1) {
ll k = x >> 1;
for (ll i = 0;i < n;i += x) {
for (ll j = 0;j < k;j++) {
add(a[i + j + k], a[i + j] * type);
}
}
}
}
void And(ll* a, ll type) {
for (ll x = 2;x <= n;x <<= 1) {
ll k = x >> 1;
for (ll i = 0;i < n;i += x) {
for (ll j = 0;j < k;j++) {
add(a[i + j], a[i + j + k] * type);
}
}
}
}
void Xor(ll* a, ll type) {
for (ll x = 2;x <= n;x <<= 1) {
ll k = x >> 1;
for (ll i = 0;i < n;i += x) {
for (ll j = 0;j < k;j++) {
add(a[i + j], a[i + j + k] % mo);
a[i + j + k] = (a[i + j] - 2ll * a[i + j + k] % mo) % mo;
a[i + j] = a[i + j] * type % mo;
a[i + j + k] = a[i + j + k] * type % mo;
}
}
}
}
int main() {
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
inv2 = -(mo / 2);
inv2 = (inv2 % mo + mo) % mo;
cin >> n;
n = 1 << n;
fo(i, 0, n - 1) cin >> a[i];
fo(i, 0, n - 1) cin >> b[i];
fo(i, 0, n - 1) aa[i] = a[i], bb[i] = b[i];
Or(aa, 1); Or(bb, 1);
fo(i, 0, n - 1) c[i] = aa[i] * bb[i] % mo;
Or(c, -1);
fo(i, 0, n - 1) cout << (c[i] % mo + mo) % mo << " ";
cout << "\n";
fo(i, 0, n - 1) aa[i] = a[i], bb[i] = b[i];
And(aa, 1); And(bb, 1);
fo(i, 0, n - 1) c[i] = aa[i] * bb[i] % mo;
And(c, -1);
fo(i, 0, n - 1) cout << (c[i] % mo + mo) % mo << " ";
cout << "\n";
fo(i, 0, n - 1) aa[i] = a[i], bb[i] = b[i];
Xor(aa, 1); Xor(bb, 1);
fo(i, 0, n - 1) c[i] = aa[i] * bb[i] % mo;
Xor(c, inv2);
fo(i, 0, n - 1) cout << (c[i] % mo + mo) % mo << " ";
cout << "\n";
return 0;
}
[TJOI2011] 01矩阵
题目描述
\(n\times m\) 的 \(01\) 矩阵，其中某些位置已经确定，为 '.' 的位置可以填 \(0\) 或 \(1\)，求相邻两个位置不同为 \(1\) 的矩阵方案数，答案模 \(10007\)。
首先预处理出哪些状态是合法的，假设这一行。的状态是s，那么能够由上一行转移来的t必定满足s|t=0,因此t是s补集中的子集，直接利用or卷积即可。
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
#define pi pair<ll,ll>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
typedef unsigned int uint;
//typedef __int128 i128;
const int inf = 1e9;
const ll mo1 = 1e9 + 9;
const ll mo2 = 1e9 + 7;
const ll P = 131;
const ll Q = 13331;
const ll mo = 10007;
const int N = 1 << 20;
int c[300][300];
ll inv2, a[N], b[N], n, aa[N], bb[N], m, f[N], g[N], st[N], one[N], zero[N];
string s;
bool bz[N];
void add(ll& x, ll y) {
x = (x + y) % mo;
}
void Or(ll* a, ll type) {
for (ll x = 2;x <= n;x <<= 1) {
ll k = x >> 1;
for (ll i = 0;i < n;i += x) {
for (ll j = 0;j < k;j++) {
add(a[i + j + k], a[i + j] * type);
}
}
}
}
void And(ll* a, ll type) {
for (ll x = 2;x <= n;x <<= 1) {
ll k = x >> 1;
for (ll i = 0;i < n;i += x) {
for (ll j = 0;j < k;j++) {
add(a[i + j], a[i + j + k] * type);
}
}
}
}
void Xor(ll* a, ll type) {
for (ll x = 2;x <= n;x <<= 1) {
ll k = x >> 1;
for (ll i = 0;i < n;i += x) {
for (ll j = 0;j < k;j++) {
add(a[i + j], a[i + j + k] % mo);
a[i + j + k] = (a[i + j] - 2ll * a[i + j + k] % mo) % mo;
a[i + j] = a[i + j] * type % mo;
a[i + j + k] = a[i + j + k] * type % mo;
}
}
}
}
int main() {
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
inv2 = -(mo / 2);
inv2 = (inv2 % mo + mo) % mo;
cin >> n >> m;
fo(i, 1, n) {
cin >> s;
fo(j, 1, m) {
if (s[j - 1] == '.') c[i][j] = -1;
else c[i][j] = s[j - 1] - '0';
}
}
if (n > 15) {
fo(i, 1, n) fo(j, i + 1, n) swap(c[i][j], c[j][i]);
swap(n, m);
}
fo(j, 1, m) {
fo(i, 0, n - 1) {
if (c[i + 1][j] == 0) zero[j] |= (1 << i);
if (c[i + 1][j] == 1) one[j] |= (1 << i);
}
}
int k = n;
n = 1 << n;
fo(s, 0, n - 1) {
fo(i, 0, k - 2) {
if ((s & (1 << i)) && (s & (1 << (i + 1)))) bz[s] = 1;
}
}
f[0] = 1;
fo(i, 1, m) {
Or(f, 1);
fo(j, 0, n - 1) {
if (bz[j] || (j & zero[i]) || ((j & one[i]) != one[i])) g[j] = 0;
else g[j] = f[j ^ (n - 1)];
}
fo(j, 0, n - 1) f[j] = g[j];
}
ll ans = 0;
fo(j, 0, n - 1) add(ans, g[j]);
ans = (ans % mo + mo) % mo;
cout << ans;
return 0;
}
[HAOI2015] 按位或
题目描述
刚开始你有一个数字 \(0\)，每一秒钟你会随机选择一个 \([0,2^n-1]\) 的数字，与你手上的数字进行或（C++,C 的 |，pascal 的 or）操作。选择数字 \(i\) 的概率是 \(p_i\)。保证 \(0\leq p_i \leq 1\)，\(\sum p_i=1\) 。问期望多少秒后，你手上的数字变成 \(2^n-1\)。
需要利用min-max容斥，\(E(max(S))=\sum_{T \in S} (-1)^{|T|+1}E(min(T))\)
考虑怎么求E(min(T))，假设选中T集合中的位置的概率为p，则\(E(min(T))=\frac{1}{p}\)，而p的计算为所有至少包含T中一个位的所有pi的和，那么我们减去跟t完全没有交集的集合的pi的和即可，也就是补集的子集，最后计算min-max容斥的式子再用一次计算子集的套路即可。
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define pi pair<ll,ll>
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
const ll inf = 1ll << 60;
const ll mo1 = 1e9 + 9;
const ll mo2 = 1e9 + 7;
const ll P = 131;
const ll Q = 13331;
const ll mo = 998244353;
const int N = 1 << 20;
const db eps = 1e-9;
ll n, st;
db a[N], p[N];
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
db sum = 0;
cin >> n;
int st = (1 << n) - 1;
fo(i, 0, st) cin >> p[i], sum += p[i];
fo(j, 0, n - 1) fo(i, 0, st) {
if ((i >> j) & 1) p[i] += p[i ^ (1 << j)];
}
fo(i, 0, st) a[i] = sum - p[st ^ i];
bool flag = 1;
fo(i, 1, st) if (a[i] < eps) flag = 0;
if (!flag) {
cout << "INF";
return 0;
}
a[0] = 0;
fo(i, 1, st) {
int cnt = 0;
fo(j, 0, n - 1) if ((i >> j) & 1) ++cnt;
a[i] = 1.0 / a[i];
if (cnt % 2 == 0) a[i] = -a[i];
}
fo(j, 0, n - 1) fo(i, 0, st) {
if ((i >> j) & 1) a[i] += a[i ^ (1 << j)];
}
cout << fixed << setprecision(10) << a[st];
return 0;
}
excrt
【模板】扩展中国剩余定理（EXCRT）
题目描述
给定 \(n\) 组非负整数 \(a_i, b_i\) ，求解关于 \(x\) 的方程组的最小非负整数解。
\[\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}
\]
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
#define pi pair<ll,ll>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
typedef unsigned int uint;
//typedef __int128 i128;
const int inf = 1e9;
const ll mo1 = 1e9 + 9;
const ll mo2 = 1e9 + 7;
const ll P = 131;
const ll Q = 13331;
//const ll mo=1e9+7;
const int N = 2e5 + 5;
struct node {
ll r, m;
bool flag;
};
node a[N];
ll n;
ll gcd(ll a, ll b) {
if (!b) return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
void exgcd(ll a, ll b, ll& d, ll& x, ll& y) {
if (!b) {
d = a;
x = 1;
y = 0;
return;
}
exgcd(b, a % b, d, y, x);
y -= (a / b) * x;
}
ll mul(ll a, ll b, ll mod) {
a %= mod;
b %= mod;
ll t = 0;
while (b) {
if (b & 1) t = (t + a) % mod;
a = (a + a) % mod;
b /= 2;
}
return t;
}
node merge(node a, node b) {
ll r1, r2, m1, m2, x, y, d, mm, rr;
if (!a.flag) return (node) { 0, 0, 0 };
r1 = a.r; m1 = a.m;
r2 = b.r; m2 = b.m;
exgcd(m1, -m2, d, x, y);
if ((r2 - r1) % d) return (node) { 0, 0, 0 };
mm = lcm(m1, m2);
x = mul((r2 - r1) / d, x, mm);
rr = (mul(x, m1, mm) + r1 % mm) % mm;
return (node) { rr, mm, 1 };
}
int main() {
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
fo(i, 1, n) cin >> a[i].m >> a[i].r, a[i].flag = 1;
node ans = a[1];
fo(i, 2, n) {
ans = merge(ans, a[i]);
}
ll r = ans.r, m = ans.m;
cout << (r % m + m) % m;
return 0;
}
矩阵乘法
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
using namespace std;
typedef long long ll;
const ll mo=998244353;
struct mat{
ll a[6][6];
mat(){
memset(a,0,sizeof(a));
}
};
mat operator* (mat a,mat b){
mat c;
fo(i,0,5) fo(j,0,5) fo(k,0,5) {
add(c.a[i][j], a.a[i][k]*b.a[k][j]%mo);
}
return c;
}
void power(ll b){
while (b) {
if (b&1) {
t=y*t;
}
y=y*y;
b/=2;
}
}