梧州网站平台建设公司,凡科建站官网需要什么,深圳市建设工程招标网,百度推广管家登录2023牛客第七场补题报告C F L M
C-Beautiful Sequence_2023牛客暑期多校训练营7 (nowcoder.com)
思路
观察到数组一定是递增的#xff0c;所以从最高位往下考虑每位的1最多只有一个#xff0c;然后按位枚举贪心即可。
代码
#include bits/stdc.h
using namespac…2023牛客第七场补题报告C F L M
C-Beautiful Sequence_2023牛客暑期多校训练营7 (nowcoder.com)
思路
观察到数组一定是递增的所以从最高位往下考虑每位的1最多只有一个然后按位枚举贪心即可。
代码
#include bits/stdc.h
using namespace std;
#define int long long
void solve();
signed main(){cin.sync_with_stdio(0);cin.tie(0);int T 1;cin T;while(T--){solve();}return 0;
}const int N 1e6 5;
bool bit[N][32];
int nok[32][2];
void dfs(int l, int r, int d){//cout d l r \n;if(d 0 || l r)return;int conv 0;int id l - 1;for(int i l;i r;i){if(bit[i][d] ! bit[i 1][d]){id i;conv;}}if(conv 1){nok[d][0] 1;nok[d][1] 1;return;} else if(conv 1){if(bit[l][d] 0){nok[d][1] 1;}else{nok[d][0] 1;}dfs(l, id, d - 1);dfs(id 1, r, d - 1);}else{dfs(l, r, d - 1);}}
void solve(){int n,k;cin n k;vectorint b(n 1);for(int i 1;i n;i ) {cin b[i];} for(int i 0;i 30;i){nok[i][0] 0;nok[i][1] 0;}for(int i 1;i n;i ) {for(int j 0;j 30;j ) {if(i 1){bit[i][j] 0;}else{bit[i][j] (bit[i - 1][j] ^ ((b[i - 1] j) 1));}}}dfs(1, n, 30);for(int i 0;i 30;i){if(nok[i][0] 1 nok[i][1] 1){cout -1\n;return;}}long long rag 1;for(int i 0;i 30;i){if(nok[i][0] 0 nok[i][1] 0){rag 1;}}if(rag k){cout -1\n;}else{k--;long long ans 0;for(int i 0, kk 0;i 30;i){if(nok[i][0] 0 nok[i][1] 0){if((k kk) 1){ans | 1 i;}kk;}else if(nok[i][1] 0){ans | 1 i;}}if(ans (1ll 30)){cout -1\n;}else{cout ans ;for(int i 1;i n;i){ans ans ^ b[i];cout ans ;}cout \n;}}
}F-Counting Sequences_2023牛客暑期多校训练营7 (nowcoder.com)
思路
考虑到数据范围很大先想的dp会t可以使用多项式乘法n次幂乘以m次幂就可以变换为nm此时直接输出多项式幂次的第k项即可。
代码
#include bits/stdc.h
using namespace std;void solve();int main(){cin.sync_with_stdio(0);cin.tie(0);int T 1;//cin T;while(T--){solve();}return 0;
}constexpr int P 998244353;
using i64 long long;
// assume -P x 2P
int norm(int x) {if (x 0) {x P;}if (x P) {x - P;}return x;
}
templateclass T
T power(T a, int b) {T res 1;for (; b; b / 2, a * a) {if (b % 2) {res * a;}}return res;
}struct Z {int x;Z(int x 0) : x(norm(x)) {}int val() const {return x;}Z operator-() const {return Z(norm(P - x));}Z inv() const {assert(x ! 0);return power(*this, P - 2);}Z operator*(const Z rhs) {x i64(x) * rhs.x % P;return *this;}Z operator(const Z rhs) {x norm(x rhs.x);return *this;}Z operator-(const Z rhs) {x norm(x - rhs.x);return *this;}Z operator/(const Z rhs) {return *this * rhs.inv();}friend Z operator*(const Z lhs, const Z rhs) {Z res lhs;res * rhs;return res;}friend Z operator(const Z lhs, const Z rhs) {Z res lhs;res rhs;return res;}friend Z operator-(const Z lhs, const Z rhs) {Z res lhs;res - rhs;return res;}friend Z operator/(const Z lhs, const Z rhs) {Z res lhs;res / rhs;return res;}friend std::istream operator(std::istream is, Z a) {i64 v;is v;a Z(v);return is;}friend std::ostream operator(std::ostream os, const Z a) {return os a.val();}
};std::vectorint rev;
std::vectorZ roots{0, 1};
void dft(std::vectorZ a) {int n a.size();if (int(rev.size()) ! n) {int k __builtin_ctz(n) - 1;rev.resize(n);for (int i 0; i n; i) {rev[i] rev[i 1] 1 | (i 1) k;}}for (int i 0; i n; i) {if (rev[i] i) {std::swap(a[i], a[rev[i]]);}}if (int(roots.size()) n) {int k __builtin_ctz(roots.size());roots.resize(n);while ((1 k) n) {Z e power(Z(3), (P - 1) (k 1));for (int i 1 (k - 1); i (1 k); i) {roots[2 * i] roots[i];roots[2 * i 1] roots[i] * e;}k;}}for (int k 1; k n; k * 2) {for (int i 0; i n; i 2 * k) {for (int j 0; j k; j) {Z u a[i j];Z v a[i j k] * roots[k j];a[i j] u v;a[i j k] u - v;}}}
}
void idft(std::vectorZ a) {int n a.size();std::reverse(a.begin() 1, a.end());dft(a);Z inv (1 - P) / n;for (int i 0; i n; i) {a[i] * inv;}
}
struct Poly {std::vectorZ a;Poly() {}Poly(const std::vectorZ a) : a(a) {}Poly(const std::initializer_listZ a) : a(a) {}int size() const {return a.size();}void resize(int n) {a.resize(n);}Z operator[](int idx) const {if (idx size()) {return a[idx];} else {return 0;}}Z operator[](int idx) {return a[idx];}Poly mulxk(int k) const {auto b a;b.insert(b.begin(), k, 0);return Poly(b);}Poly modxk(int k) const {k std::min(k, size());return Poly(std::vectorZ(a.begin(), a.begin() k));}Poly divxk(int k) const {if (size() k) {return Poly();}return Poly(std::vectorZ(a.begin() k, a.end()));}friend Poly operator(const Poly a, const Poly b) {std::vectorZ res(std::max(a.size(), b.size()));for (int i 0; i int(res.size()); i) {res[i] a[i] b[i];}return Poly(res);}friend Poly operator-(const Poly a, const Poly b) {std::vectorZ res(std::max(a.size(), b.size()));for (int i 0; i int(res.size()); i) {res[i] a[i] - b[i];}return Poly(res);}friend Poly operator*(Poly a, Poly b) {if (a.size() 0 || b.size() 0) {return Poly();}int sz 1, tot a.size() b.size() - 1;while (sz tot) {sz * 2;}a.a.resize(sz);b.a.resize(sz);dft(a.a);dft(b.a);for (int i 0; i sz; i) {a.a[i] a[i] * b[i];}idft(a.a);a.resize(tot);return a;}friend Poly operator*(Z a, Poly b) {for (int i 0; i int(b.size()); i) {b[i] * a;}return b;}friend Poly operator*(Poly a, Z b) {for (int i 0; i int(a.size()); i) {a[i] * b;}return a;}Poly operator(Poly b) {return (*this) (*this) b;}Poly operator-(Poly b) {return (*this) (*this) - b;}Poly operator*(Poly b) {return (*this) (*this) * b;}Poly deriv() const {if (a.empty()) {return Poly();}std::vectorZ res(size() - 1);for (int i 0; i size() - 1; i) {res[i] (i 1) * a[i 1];}return Poly(res);}Poly integr() const {std::vectorZ res(size() 1);for (int i 0; i size(); i) {res[i 1] a[i] / (i 1);}return Poly(res);}Poly inv(int m) const {Poly x{a[0].inv()};int k 1;while (k m) {k * 2;x (x * (Poly{2} - modxk(k) * x)).modxk(k);}return x.modxk(m);}Poly log(int m) const {return (deriv() * inv(m)).integr().modxk(m);}Poly exp(int m) const {Poly x{1};int k 1;while (k m) {k * 2;x (x * (Poly{1} - x.log(k) modxk(k))).modxk(k);}return x.modxk(m);}Poly pow(int k, int m) const {int i 0;while (i size() a[i].val() 0) {i;}if (i size() || 1LL * i * k m) {return Poly(std::vectorZ(m));}Z v a[i];auto f divxk(i) * v.inv();return (f.log(m - i * k) * k).exp(m - i * k).mulxk(i * k) * power(v, k);}Poly sqrt(int m) const {Poly x{1};int k 1;while (k m) {k * 2;x (x (modxk(k) * x.inv(k)).modxk(k)) * ((P 1) / 2);}return x.modxk(m);}Poly mulT(Poly b) const {if (b.size() 0) {return Poly();}int n b.size(); // eb 1std::reverse(b.a.begin(), b.a.end());return ((*this) * b).divxk(n - 1); //保留系数(x ^ eb)及以上的}std::vectorZ eval(std::vectorZ x) const {if (size() 0) {return std::vectorZ(x.size(), 0);}const int n std::max(int(x.size()), size());std::vectorPoly q(4 * n);std::vectorZ ans(x.size());x.resize(n);std::functionvoid(int, int, int) build [](int p, int l, int r) {if (r - l 1) {q[p] Poly{1, -x[l]};} else {int m (l r) / 2;build(2 * p, l, m);build(2 * p 1, m, r);q[p] q[2 * p] * q[2 * p 1];}};build(1, 0, n);std::functionvoid(int, int, int, const Poly ) work [](int p, int l, int r, const Poly num) {if (r - l 1) {if (l int(ans.size())) {ans[l] num[0];}} else {int m (l r) / 2;work(2 * p, l, m, num.mulT(q[2 * p 1]).modxk(m - l));work(2 * p 1, m, r, num.mulT(q[2 * p]).modxk(r - m));}};work(1, 0, n, mulT(q[1].inv(n)));return ans;}
};void solve(){int n, m, k;cin n m k;vectorZ a(k 1);a[0] 1;int R min(n, k);for(int i 1;i R;i){a[i] a[i - 1] * (n - i 1) / i;}for(int i 1;i R;i2){a[i] 0;}for(int i 0;i R;i2){a[i] * 2;}auto c Poly(a).pow(m,k 1);cout c[k] \n;
}L-Misaka Mikoto’s Dynamic KMP Problem_2023牛客暑期多校训练营7 (nowcoder.com)
思路
注意到|s||t|时出现次数必定为0所以该询问的 x i × y i 0 x_i×y_i0 xi×yi0。而当 ∣ s ∣ ≤ ∣ t ∣ |s| \leq |t| ∣s∣≤∣t∣直接暴力跑KMP求出现次数和最长border即可。单轮复杂度O(t)。
代码
#include bits/stdc.h
using namespace std;
using ll long long;templateclass T
class KMP {int m;T p;public:vectorint nxt;KMP() {}KMP(const T _p) { init(_p); }void init(const T _p) {m _p.size() - 1;p _p;nxt.assign(m 1, 0);for (int i 2;i m;i) {nxt[i] nxt[i - 1];while (nxt[i] p[i] ! p[nxt[i] 1]) nxt[i] nxt[nxt[i]];nxt[i] p[i] p[nxt[i] 1];}}vectorint find(const T s) {int n s.size() - 1;vectorint pos;for (int i 1, j 0;i n;i) {while (j s[i] ! p[j 1]) j nxt[j];j s[i] p[j 1];if (j m) {pos.push_back(i - j 1);j nxt[j];}}return pos;}vectorint get_cycle_time() {vectorint res;int pos m;while (pos) {pos nxt[pos];res.push_back(m - pos);}return res;}vectorint get_cycle_loop() {vectorint res;for (auto val : get_cycle_time())if (!(m % val)) res.push_back(val);return res;}int min_cycle_loop() { return get_cycle_loop()[0]; }void debug() {for (int i 1;i m;i)cout nxt[i] \n[i m];}
};
/// KMP前缀函数O(|P|)、查找O(|S||P|)、循环相关O(|P|)维护字符串前缀函数int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, q, b, p;cin n q b p;vectorint s(n 1);for (int i 1;i n;i) cin s[i];ll z 0;int mul 1, ans 0;while (q--) {int op;cin op;if (op 1) {ll x, c;cin x c;x (x ^ z) % n 1;c ^ z;s[x] c;}else {int m;cin m;vectorint t(m 1);for (int i 1;i m;i) {ll val;cin val;t[i] val ^ z;}mul 1LL * mul * b % p;if (m n) z 0;else {KMPvectorint kmp(s);z 1LL * kmp.nxt[n] * kmp.find(t).size();}ans (ans z % p * mul % p) % p;}}cout ans \n;return 0;
}M-Writing Books_2023牛客暑期多校训练营7 (nowcoder.com)
思路
直接枚举位数。
代码
#include bits/stdc.h
#define int long long
#define endl \n
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define sc secondusing namespace std;
const int INF 0x3f3f3f3f3f3f3f3f;
const int N 1e6 10;
const int mod 1e9 7;
typedef pairint, int PII;
int n;
int a[N];void solve() {cin n;int tmp 1;int res 0;int cnt 1;while (n tmp) {int x tmp;tmp * 10;res (min(n, tmp - 1) - x 1) * cnt;cnt;}cout res \n;
}signed main() {IOS;int t 1;cin t;for (int i 1; i t; i) {solve();}
}
