周三
F - The Answer to the Ultimate Question of Life, The Universe, and Everything. （打表）
求a ^ 3 + b ^ 3 + c ^ 3 = x 有无解 有则输出
a b c 的绝对值小于5000 x在0到200
我看到x范围比较小就觉得可以打表
问题是怎么写一个比较快的打表程序
一开始想的是c^3用map存，然后对于每一个x枚举a b
但这样太慢了
其实很接近了
应该是a ^ 3 + b ^ 3用map存，然后每次枚举c
这样打表的就很快了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(ll i = (a); i <= (b); i++)
using namespace std;int ans[250][3] =
{
0,5000,-5000,
1,5000,-5000,
-486,4375,-4373,
4,4,-5,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-205,644,-637,
44,168,-169,
2,5000,-5000,
-52,217,-216,
-353,683,-650,
-641,843,-695,
7,10,-11,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-262,332,-265,
-588,4118,-4114,
2195,2977,-3331,
-1276,1671,-1373,
47,91,-95,
-741,2833,-2816,
-287,445,-401,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
8,8,-10,
1839,2357,-2683,
237,2106,-2107,
3,5000,-5000,
-249,2269,-2268,
-69,235,-233,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-244,1557,-1555,
-509,1154,-1120,
2358,2731,-3223,
-84,445,-444,
16,25,-27,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-307,837,-823,
-5,8,-7,
1709,2025,-2369,
-473,815,-758,
49,139,-141,
-1247,3991,-3950,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
602,659,-796,
1000000000,1000000000,1000000000,
1518,2141,-2370,
-648,3891,-3885,
1837,3131,-3329,
505,559,-672,
361,982,-998,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-163,1202,-1201,
668,845,-966,
-1561,2903,-2744,
102,146,-161,
4,5000,-5000,
403,903,-929,
1,4,1,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
134,398,-403,
824,2325,-2359,
401,443,-533,
-104,434,-432,
-146,344,-335,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-829,2123,-2080,
-196,711,-706,
-706,1366,-1300,
-1719,2638,-2368,
847,1188,-1317,
1315,3651,-3707,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-1972,4271,-4126,
-1282,1686,-1390,
1953,2036,-2514,
365,1798,-1803,
-2912,3992,-3389,
861,4039,-4052,
-98,253,-248,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
14,20,-22,
-991,3200,-3168,
-1638,2391,-2101,
-622,984,-893,
-903,1870,-1797,
319,2325,-2327,
118,229,-239,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-4,8,-7,
-1165,2760,-2689,
947,1117,-1309,
-948,1345,-1165,
853,2924,-2948,
1000000000,1000000000,1000000000,
-2312,4966,-4793,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
8,11,-12,
-757,1945,-1906,
-555,962,-896,
383,4327,-4328,
-1673,3789,-3677,
1219,2725,-2804,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-16,38,-37,
0,5,-1,
5,5000,-5000,
-419,2217,-2212,
-3881,4988,-4034,
-726,3997,-3989,
-1238,1801,-1580,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
2,5,-1,
167,389,-399,
-1766,3203,-3013,
-629,1395,-1351,
816,946,-1116,
-428,801,-758,
-77,103,-86,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
104,116,-139,
-3,8,-7,
1000000000,1000000000,1000000000,
-2552,3342,-2746,
-7,10,-8,
-263,376,-327,
1528,2131,-2366,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
260,317,-367,
215,447,-463,
486,741,-805,
-695,3744,-3736,
-516,2145,-2135,
-1049,3721,-3693,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
383,1526,-1534,
-1654,3972,-3874,
-2476,4980,-4767,
-1417,4180,-4125,
-2943,4033,-3423,
-59,79,-66,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-574,890,-802,
-1012,1521,-1354,
-2149,4047,-3834,
891,1178,-1328,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-170,349,-335,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-160,1169,-1168,
-10,15,-13,
1503,2691,-2839,
1000000000,1000000000,1000000000,
974,4861,-4874,
-29,91,-90,
976,4876,-4889,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
5,5,-4,
-1092,2000,-1885,
318,1635,-1639,
-1403,1974,-1702,
-593,4815,-4812,
-215,399,-377,
16,16,-20,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,
-579,1112,-1057,
-1606,3026,-2867,
-1347,3809,-3752,
508,2199,-2208,
-638,2334,-2318,
};int main()
{int T; scanf("%d", &T);while(T--){int x; scanf("%d", &x);if(ans[x][0] == 1e9) puts("impossible");else printf("%d %d %d\n", ans[x][0], ans[x][1], ans[x][2]);}return 0;
}C - <3 numbers
很容易想到质数的分布是比较稀疏的
所以大范围是肯定小于1 / 3的
小范围暴力
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int check(int x)
{if(x == 1) return true;for(int i = 2; i * i <= x; i++)if(x % i == 0)return false;return true;
}int main()
{int T; scanf("%d", &T);while(T--){int l, r;scanf("%d%d", &l, &r);if(r - l > 1e3) puts("Yes");else{int cnt = 0;_for(i, l, r)cnt += check(i);if(3 * cnt < (r - l + 1)) puts("Yes");else puts("No");}}return 0;
}E - Multiply （大数质数判定与分解质因数）
套了kuangbin的模板
但一直WA
其实思路完全正确，就是小细节没弄好
一个是计算因数出现了多少次的时候确实会爆long long 因为是阶乘的因子数不是一个数的因子数
一个是有个地方会爆long long 我意识到了但没处理好
应该反过来写，用除法 就可以避免这个问题
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
const int S = 8;
ll x, y, a[N];
int m;ll factor[100];
int tol;ll gcd(ll a, ll b)
{ ll t;while(b){t = a;a = b;b = t % b;}if(a >= 0) return a;return -a;
}ll binpow(ll a, ll b, ll c)
{a %= c;b %= c;ll ret = 0, tmp = a;while(b){if(b & 1){ret += tmp;if(ret > c) ret -= c;}tmp <<= 1;if(tmp > c) tmp -= c;b >>= 1;}return ret;
}ll pow_mod(ll a, ll n, ll mod)
{ll ret = 1;ll temp = a % mod;while(n){if(n & 1) ret = binpow(ret, temp, mod);temp = binpow(temp, temp, mod);n >>= 1;}return ret;
}bool check(ll a, ll n, ll x, ll t)
{ll ret = pow_mod(a, x, n);ll last = ret;_for(i, 1, t){ret = binpow(ret, ret, n);if(ret == 1 && last != 1 && last != n - 1) return true;last = ret;}if(ret != 1) return true;return false;
}bool Miller_Rabin(ll n)
{if(n < 2) return false;if(n == 2) return true;if((n & 1) == 0) return false;ll x = n - 1, t = 0;while((x & 1) == 0) x >>= 1, t++;srand(time(0));for(int i = 0; i < S; i++){ll a = rand() % (n - 1) + 1;if(check(a, n, x, t)) return false;}return true;
}ll rho(ll x, ll c)
{ll i = 1, k = 2;srand(time(0));ll x0 = rand() % (x - 1) + 1;ll y = x0;while(1){i++;x0 = (binpow(x0, x0, x) + c) % x;ll d = gcd(y - x0, x);if(d != 1 && d != x) return d;if(y == x0) return x;if(i == k) { y = x0; k += k; }}
}void findfac(ll n, int k)
{if(n == 1) return;if(Miller_Rabin(n)){factor[tol++] = n;return;}ll p = n;int c = k;while(p >= n) p = rho(p, c--);findfac(p, k);findfac(n / p, k);
}vector<pair<ll, int>> p;
map<ll, int> mp;
ll cnta[100], cnty[100];void add(ll cur, ll cnt[])
{rep(i, 0, p.size()){ll now = p[i].first, t = cur;while(t){cnt[i] += t / now;t /= now;}}
}int main()
{int T; scanf("%d", &T);while(T--){tol = 0;scanf("%d%lld%lld", &m, &x, &y);_for(i, 1, m) scanf("%lld", &a[i]);findfac(x, 107);mp.clear(); p.clear();rep(i, 0, tol) mp[factor[i]]++;for(auto t: mp) p.push_back({t.first, t.second});memset(cnta, 0, sizeof cnta);memset(cnty, 0, sizeof cnty);add(y, cnty);_for(i, 1, m) add(a[i], cnta);ll ans = 1e18;rep(i, 0, p.size()) ans = min(ans, (cnty[i] - cnta[i]) / p[i].second);printf("%lld\n", ans);}return 0;
}M - Kill the tree (树的重心)
这道题把树的重心考到极致
先复习一下
1.树的重心指的是以重心为根的树，所有子树的节点数的最大值最小。
要求重心可以处理出子树节点数，算出以每个节点为根的树的子树节点最大值，然后比较就行
2.树的重心到所有节点的距离和最小
3.树的重心最多也两个，若有两个一定相邻
4.两个树合并时，新的重心一定在两个重心连的链上
这道题问题其实就是合并重心，在dfs的过程中不断合并
首先重心在两个重心的链上
一个重心移动时，可以计算一下这个移动所影响的距离和的值，根据子树节点可得
这个值变小就可以移动，一直移动到极值
可以发现其中一个节点会移动到根，一个节点不会。没到根的那个就是重心
可以根据深度来区分
最后注意一下两个重心的情况就好了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
vector<int> g[N];
int f[N], d[N], siz[N], ans[N], n;void init(int u, int fa)
{f[u] = fa;d[u] = d[fa] + 1;for(int v: g[u]){if(v == fa) continue;init(v, u);}
}void dfs(int u, int fa)
{siz[u] = 1;ans[u] = u;for(int v: g[u]){if(v == fa) continue;dfs(v, u);siz[u] += siz[v];int a = ans[u], b = ans[v];while(siz[a] < siz[u] - siz[a]) a = f[a];while(siz[b] < siz[u] - siz[b]) b = f[b];ans[u] = d[a] > d[b] ? a: b;}
}int main()
{scanf("%d", &n);_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}init(1, 0);dfs(1, 0);_for(i, 1, n){int u = ans[i];if(siz[u] != siz[i] - siz[u]) printf("%d\n", u);else{int v = f[u];if(u > v) swap(u, v);printf("%d %d\n", u, v);} }return 0;
}D. Bag of mice(概率dp)
用dp解决概率问题
分类讨论就行
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
double dp[N][N];
int w, b;double cal(int a, int b) { return (double)a / b; }int main()
{scanf("%d%d", &w, &b);_for(j, 0, b) dp[0][j] = 0;_for(i, 1, w) dp[i][0] = 1;_for(i, 1, w)_for(j, 1, b){dp[i][j] += cal(i, i + j);if(j >= 3) dp[i][j] += cal(j, i + j) * cal(j - 1, i + j - 1) * cal(j - 2, i + j - 2) * dp[i][j - 3];if(j >= 2 && i >= 1) dp[i][j] += cal(j, i + j) * cal(j - 1, i + j - 1) * cal(i, i + j - 2) * dp[i - 1][j - 2];}printf("%.12f\n", dp[w][b]);return 0;
}周四
Collecting Bugs（期望dp）
期望dp推公式就可以了
注意几个地方
1.概率dp设计状态是顺推，期望dp是逆推
2.期望dp推公式的时候可能等式右边会出现自己，移到左边即可
3.注意期望的含义
一般是dpij = Σpi (当前步的花费 + dp……)
可以理解为dpij = Σpi * dp…… + 当前步的花费
#include <cstdio>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
double dp[N][N];
int n, s;int main()
{scanf("%d%d", &n, &s);for(int i = n; i >= 0; i--)for(int j = s; j >= 0; j--){if(i == n && j == s) continue;double k1 = (double)i / n, k2 = (double)j / s;dp[i][j] = (1 + k1 * (1 - k2) * dp[i][j + 1] + (1 - k1) * k2 * dp[i + 1][j] + (1 - k1) * (1 - k2) * dp[i + 1][j + 1]) / (1 - k1 * k2);}printf("%.6f\n", dp[0][0]);return 0;
}HDU 3853 (期望dp)
和上一题类似
期望dp逆推就行
注意可能停在当前地方的概率为百分百，要特判一下
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
double dp[N][N], a[N][N], b[N][N], c[N][N];
int n, m;int main()
{while(~scanf("%d%d", &n, &m)){_for(i, 1, n)_for(j, 1, m)scanf("%lf%lf%lf", &a[i][j], &b[i][j], &c[i][j]);memset(dp, 0, sizeof dp);for(int i = n; i >= 1; i--)for(int j = m; j >= 1; j--){if(i == n && j == m) continue;if(a[i][j] == 1) continue;dp[i][j] = (b[i][j] * dp[i][j + 1] + c[i][j] * dp[i + 1][j] + 2) / (1 - a[i][j]);}printf("%.3f\n", dp[1][1]);}return 0;
}周五
F - Honeycomb
把输入处理一下bfs即可
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
const int M = 1e6 + 10;
char s[4 * N][6 * N];
int d[M], n, m, st, t;
vector<int> g[M];int id(int i, int j) { return (i - 1) * m + j; }int bfs()
{_for(i, 1, n)_for(j, 1, m)d[id(i, j)] = 0;queue<int> q;q.push(st);d[st] = 1;while(!q.empty()){int u = q.front(); q.pop();for(int v: g[u]){if(d[v]) continue;d[v] = d[u] + 1;if(v == t) return d[v];q.push(v);}}return -1;
}int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);getchar();_for(i, 1, 4 * n + 3) gets(s[i] + 1);_for(i, 1, n * m) g[i].clear();_for(i, 1, n)_for(j, 1, m){int x, y;if(j % 2 == 1) x = 4 * i - 1;else x = 4 * i + 1;y = 6 * j - 1;if(s[x][y] == 'S') st = id(i, j);if(s[x][y] == 'T') t = id(i, j);if(j % 2 == 0){if(s[x + 1][y + 3] == ' ') g[id(i, j)].push_back(id(i + 1, j + 1));if(s[x + 1][y - 3] == ' ') g[id(i, j)].push_back(id(i + 1, j - 1));if(s[x - 1][y + 3] == ' ') g[id(i, j)].push_back(id(i, j + 1));if(s[x - 1][y - 3] == ' ') g[id(i, j)].push_back(id(i, j - 1));if(s[x + 2][y] == ' ') g[id(i, j)].push_back(id(i + 1, j));if(s[x - 2][y] == ' ') g[id(i, j)].push_back(id(i - 1, j));}else{if(s[x + 1][y + 3] == ' ') g[id(i, j)].push_back(id(i, j + 1));if(s[x + 1][y - 3] == ' ') g[id(i, j)].push_back(id(i, j - 1));if(s[x - 1][y + 3] == ' ') g[id(i, j)].push_back(id(i - 1, j + 1));if(s[x - 1][y - 3] == ' ') g[id(i, j)].push_back(id(i - 1, j - 1));if(s[x + 2][y] == ' ') g[id(i, j)].push_back(id(i + 1, j));if(s[x - 2][y] == ' ') g[id(i, j)].push_back(id(i - 1, j));}}printf("%d\n", bfs());}return 0;
}E - Resistors in Parallel （数学 + 高精度）
打表可以看出来
但比赛时还是推出来的
首先题目说了没有平方因子
那对于一个数，肯定是它的所有因子选0此方或者1此方
那么肯定是前几个质数
代入公式可得答案为 n除以一个求和
n是当前要选的数
求和是因子之和
发现这个值可以递推
每次多一个质数就是乘以质数加1，因为是在前面的结果之下这个值选或者不选
那么就还剩下一个怎么约分的问题
每次分子乘一个p，分母乘p + 1
分子要和分母约分，要满足pi = pj + 1
也就是相邻的质数差1，可以发现只有2 和 3 这个可以特判一下
p + 1要和分子约分，这个可以暴力枚举p + 1的因子，看是不是分母的因子，是的话就约分
要用高精度
高精度乘以低精，除以低精度，模低精度
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;struct bignum
{int s[10000], len;bignum() { memset(s, 0, sizeof s); len = 0; }void print(){for(int i = len; i >= 1; i--) printf("%d", s[i]);}
};bignum mul(bignum a, int t)
{_for(i, 1, a.len) a.s[i] *= t;_for(i, 1, a.len){a.s[i + 1] += a.s[i] / 10;a.s[i] %= 10;}while(a.s[a.len + 1]){a.len++;a.s[a.len + 1] += a.s[a.len] / 10;a.s[a.len] %= 10;}return a;
}bignum div(bignum a, int t)
{int& len = a.len;for(int i = len; i >= 1; i--){if(i - 1 >= 1) a.s[i - 1] += (a.s[i] % t) * 10;a.s[i] /= t;}while(len && !a.s[len]) len--;return a;
}int mol(bignum a, int t)
{int d = 0;for(int i = a.len; i >= 1; i--)d = (d * 10 + a.s[i]) % t;return d;
}bool check(int x)
{if(x == 1 || x == 0) return false;for(int i = 2; i * i <= x; i++)if(x % i == 0)return false;return true;
}
vector<int> p;int main()
{_for(i, 2, 300)if(check(i))p.push_back(i);int T; scanf("%d", &T);while(T--){string s;cin >> s;int len = s.size();if(s == "1"){puts("1/1");continue;}bignum x; int t = 0;x.len = len;for(int i = len - 1; i >= 0; i--)x.s[++t] = s[i] - '0';int pos;rep(i, 0, p.size()){x = div(x, p[i]);if(!x.len) break;pos = i;}vector<int> ans;_for(i, 0, pos) ans.push_back(p[i]);if(ans.size() == 1) {puts("2/3");continue;}else if(ans.size() == 2){puts("1/2");continue;}bignum up; up.len = 1; up.s[1] = 1;bignum down; down.len = 1; down.s[1] = 2;rep(i, 2, ans.size()){int now = p[i] + 1;for(int j = now - 1; j >= 1; j--)if(now % j == 0 && mol(up, j) == 0){now /= j;up = div(up, j);break;}up = mul(up, p[i]);down = mul(down, now);}up.print();putchar('/');down.print();puts("");}return 0;
}
网络流建模技巧
总结了一下 写在这篇博客
网络流建模技巧_Keep going, don't settle.-CSDN博客
CF16E Fish （概率+状压dp）
n只有18那果断状压dp
注意每次转移的时候，两条鱼相遇还要乘上一个概率，即1 / C(m, 2) m为当前存活的鱼的数目
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;double dp[1 << 18], a[20][20];
int n;int main()
{scanf("%d", &n);rep(i, 0, n)rep(j, 0, n)scanf("%lf", &a[i][j]);dp[0] = 1;rep(S, 0, 1 << n){rep(i, 0, n)if(S & (1 << i)){int cnt = 1;double sum = 0;rep(j, 0, n)if(j != i && !(S & (1 << j)))sum += a[j][i], cnt++;if(cnt) dp[S] += dp[S ^ (1 << i)] * 2 / cnt / (cnt - 1) * sum;}}int all = (1 << n) - 1;rep(i, 0, n) printf("%.6f ", dp[all ^ (1 << i)]);return 0;
}CF621E Wet Shark and Blocks（矩阵快速幂优化动态规划）
看到b有1e9一下子懵逼了
但是考虑的时候我先不考虑1e9，先想dp
dp[i][j]表示前i位余数为j的方案数
一开始我想的是从低位开始，发现不好弄
然后我就从高位开始，就好处理很多，每次余数乘以10加上当前的数即可
可以发现每次转移都是类似的，固定的i都转移到固定的一些j
那问题来了，dp方程都写好了，怎么处理1e9
很快想到矩阵快速幂，但是之前都是优化递推式，手算矩阵的，这个是不定的，我这道题就卡在这里
看了题解后发现，构造一个矩阵A,如果余数i转化为j，那就Aij++
这样子，乘上这个矩阵就恰好完成了一次转移
我验证了一下，恰好是这样
dp的初始状态是dp[0][0] = 1
也就是这样一个矩阵[1, 0, 0, 0……]
手算可得，dp[b][k]显然就是A^b矩阵的[0][k]这个位置
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int mod = 1e9 + 7;
const int N = 150;
struct node
{ll s[N][N];node() { memset(s, 0, sizeof s); }
}A;
int n, b, k, x;node mul(node a, node b)
{node c;rep(i, 0, x)rep(j, 0, x)rep(t, 0, x)c.s[i][j] = (c.s[i][j] + a.s[i][t] * b.s[t][j]) % mod;return c;
}int main()
{scanf("%d%d%d%d", &n, &b, &k, &x);_for(i, 1, n){int cur; scanf("%d", &cur);rep(j, 0, x)A.s[j][(j * 10 + cur) % x]++;}node res;rep(i, 0, x) res.s[i][i] = 1;for(; b; b >>= 1){if(b & 1) res = mul(res, A);A = mul(A, A);}printf("%lld\n", res.s[0][k]);return 0;
}E. Number With The Given Amount Of Divisors（因数个数 + 搜索）
独立做出
一个数为p1 ^ k1 * p2 ^ k2……
因数个数为(k1 + 1) (k2 + 1) ……
因此可以暴力将n分解成很多个因子
要使数最小，显然选前几个质数
把这些因子分配到前几个因子就可以了
注意longlong如果爆了就变成负数了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long LL;
LL ans = 1e18;int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43};LL cal(LL a, int b)
{LL res = 1;_for(i, 1, b) {res *= a;if(res < 0) return -1;}return res;
}void dfs(int n, LL cur, int pos)
{if(cur < 0 || cur > ans) return;if(n == 1) {ans = min(ans, cur);return;}for(int i = 2; i <= n; i++)if(n % i == 0)dfs(n / i, cur * cal(p[pos], i - 1), pos + 1);
}int main()
{int n;scanf("%d", &n);dfs(n, 1, 0);printf("%lld\n", ans);return 0;
}今天兴致很高刷了很多题还做了网络流总结
最近一个感悟是，做你该做的，然后对结果不报期望
太多报很大期望结果事与愿违了。还是不报期望吧。不报期望反而没什么压力，内心平静