{
// Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the
// same ids are connected.
// Example:
// "Print to console": {
// "prefix": "log",
// "body": [
// "console.log('$1');",
// "$2"
// ],
// "description": "Log output to console"
// }
"ACMinit": {
"prefix": "ACMINIT",
"body": [
"#include<bits/stdc++.h>",
"#define sc(x) scanf(\"%lld\", &(x))",
"#define pr(x) printf(\"%lld\\n\", (x))",
"#define rep(i, l, r) for (int i = l; i <= r; ++i)",
"using namespace std;",
"typedef long long ll;",
"const int N = 1e5 + 7;",
"const int mod = 1e9 + 7;",
"int main(){",
"\t$0\n\treturn 0;",
"}"
],
"description": "算法竞赛代码初始化"
},
"PI": {
"body": "const double PI = acos(-1);",
"description": "圆周率常量",
"prefix": "PI"
},
"ReadLL": {
"prefix": "read",
"body": [
"inline ll read() {",
" ll s = 0, f = 1;",
" char ch;",
" do {",
" ch = getchar();",
" if (ch == '-') f = -1;",
" } while (ch < 48 || ch > 57);",
" while (ch >= 48 && ch <= 57)",
" s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();",
" return s * f;",
"}\n",
],
"description": "快速读入ll"
},
"qkpow": {
"prefix": "QKPOWINIT",
"body": [
"ll qkpow(ll a, ll b) {",
" ll ans = 1;",
" while (b) {",
" if (b & 1) ans = ans * a % mod;",
" a = a * a % mod;",
" b >>= 1;",
" }",
" return ans;",
"}",
"ll getInv(ll a) { return qkpow(a, mod - 2); } //求一个数的逆元"
],
"description": "快速幂/逆元"
},
"matrixqkpow": {
"prefix": "QKPOWMAT",
"body": [
"#include <bits/stdc++.h>",
"using namespace std;",
"typedef long long ll;",
"const ll mod = 1e9 + 7;",
"struct node { //矩阵类",
"\tll matrix[2][2];",
"\tnode() { memset(matrix, 0, sizeof(matrix)); } //初始化",
"\tvoid one() {matrix[0][0] = 1;matrix[1][1] = 1;}//单位矩阵E",
"\tnode operator*(node other) {//对*重载 定义矩阵乘法",
"\tnode ans;//记录乘积",
"\tfor (int i = 0; i < 2; i++)",
"\t\tfor (int j = 0; j < 2; j++)",
"\t\t\tfor (int k = 0; k < 2; k++) {",
"\t\t\t\tans.matrix[i][j] += matrix[i][k] * other.matrix[k][j];",
"\t\t\t\tans.matrix[i][j] %= mod;",
"\t}",
"\treturn ans;",
"}",
"};",
"node power(node a, ll b) {//快速幂 矩阵a的b次方",
"\tnode res;",
"\tres.one(); //单位矩阵",
"\twhile (b) {",
"\t\tif (b & 1) res = res * a;",
"\t\ta = a * a;",
"\t\tb >>= 1;",
"\t}",
"\treturn res;",
"}",
"int main() {",
"\tnode temp;",
"\ttemp.matrix[0][0] = 3;",
"\ttemp.matrix[0][1] = 1;",
"\ttemp.matrix[1][0] = 1;",
"\ttemp.matrix[1][1] = 3;",
"\tll n, flag = 0;",
"\twhile (cin >> n) {",
"\t\tcout << power(temp, n).matrix[0][0] << endl;",
"}",
"return 0;",
"}"
],
"description": "矩阵快速幂"
},
"factor": {
"prefix": "FactorF",
"body": [
"int work(int num) {",
" int factor[1600], m = 0;",
" for (int i = 1; i <= num / i; i++) {",
" if (num % i == 0) {",
" factor[++m] = i;",
" if (i != num / i) factor[++m] = num / i;",
" }",
" }",
" return m;",
"}"
],
"description": "因数/个数"
},
"chaichai": {
"prefix": "chaichai",
"body": [
"/***",
"* ii. ;9ABH,",
"* SA391, .r9GG35&G",
"* &#ii13Gh; i3X31i;:,rB1",
"* iMs,:,i5895, .5G91:,:;:s1:8A",
"* 33::::,,;5G5, ,58Si,,:::,sHX;iH1",
"* Sr.,:;rs13BBX35hh11511h5Shhh5S3GAXS:.,,::,,1AG3i,GG",
"* .G51S511sr;;iiiishS8G89Shsrrsh59S;.,,,,,..5A85Si,h8",
"* :SB9s:,............................,,,.,,,SASh53h,1G.",
"* .r18S;..,,,,,,,,,,,,,,,,,,,,,,,,,,,,,....,,.1H315199,rX,",
"* ;S89s,..,,,,,,,,,,,,,,,,,,,,,,,....,,.......,,,;r1ShS8,;Xi",
"* i55s:.........,,,,,,,,,,,,,,,,.,,,......,.....,,....r9&5.:X1",
"* 59;.....,. .,,,,,,,,,,,... .............,..:1;.:&s",
"* s8,..;53S5S3s. .,,,,,,,.,.. i15S5h1:.........,,,..,,:99",
"* 93.:39s:rSGB@A; ..,,,,..... .SG3hhh9G&BGi..,,,,,,,,,,,,.,83",
"* G5.G8 9#@@@@@X. .,,,,,,..... iA9,.S&B###@@Mr...,,,,,,,,..,.;Xh",
"* Gs.X8 S@@@@@@@B:..,,,,,,,,,,. rA1 ,A@@@@@@@@@H:........,,,,,,.iX:",
"* ;9\\. ,8A#@@@@@@#5,.,,,,,,,,,... 9A. 8@@@@@@@@@@M; ....,,,,,,,,S8",
"* X3 iS8XAHH8s.,,,,,,,,,,...,..58hH@@@@@@@@@Hs ...,,,,,,,:Gs",
"* r8, ,,,...,,,,,,,,,,..... ,h8XABMMHX3r. .,,,,,,,.rX:",
"* :9, . .:,..,:;;;::,.,,,,,.. .,,. ..,,,,,,.59",
"* .Si ,:.i8HBMMMMMB&5,.... . .,,,,,.sMr",
"* SS :: h@@@@@@@@@@#; . ... . ..,,,,iM5",
"* 91 . ;:.,1&@@@@@@MXs. . .,,:,:&S",
"* hS .... .:;,,,i3MMS1;..,..... . . ... ..,:,.99",
"* ,8; ..... .,:,..,8Ms:;,,,... .,::.83",
"* s&: .... .sS553B@@HX3s;,. .,;13h. .:::&1",
"* SXr . ...;s3G99XA&X88Shss11155hi. ,;:h&,",
"* iH8: . .. ,;iiii;,::,,,,,. .;irHA",
"* ,8X5; . ....... ,;iihS8Gi",
"* 1831, .,;irrrrrs&@",
"* ;5A8r. .:;iiiiirrss1H",
"* :X@H3s....... .,:;iii;iiiiirsrh",
"* r#h:;,...,,.. .,,:;;;;;:::,... .:;;;;;;iiiirrss1",
"* ,M8 ..,....,.....,,::::::,,... . .,;;;iiiiiirss11h",
"* 8B;.,,,,,,,.,..... . .. .:;;;;iirrsss111h",
"* i@5,:::,,,,,,,,.... . . .:::;;;;;irrrss111111",
"* 9Bi,:,,,,...... ..r91;;;;;iirrsss1ss1111***/"
],
"description": "柴柴！",
},
"primefactory": {
"prefix": "primefact",
"body": [
"ll a[N];",
"int PrimeFactory(ll n) { //分解质因数 要求n>1 输出24=2*2*2*3",
" int cnt = 0;",
" for (; n % 2 == 0; a[cnt++] = 2) n /= 2;",
" for (ll i = 3; i * i <= n; i += 2)",
" for (; n % i == 0; a[cnt++] = i) n /= i;",
" if (n != 1) a[cnt++] = n;",
" sort(a, a + cnt);",
" return cnt;",
"} //输入：需要分解的数 非1的因子从小到大排列在数组里 数量为返回",
],
"description": "分解质因数"
},
"sscc": {
"prefix": "sscc",
"body": "ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);\n$0",
"description": "解除cin和scanf putchar的关联，加速输入输出"
},
"DisjointSet": {
"body": [
"int ht[N];",
"int fa[N];",
"int n; // point numers",
"void init_set() {",
" for (int i = 1; i <= n; ++i) fa[i] = i, ht[i] = 0;",
"}",
"int Find(int x) {",
" if (x != fa[x]) fa[x] = Find(fa[x]); //路径压缩",
" return fa[x];",
"}",
"int findC(int x) {",
" int r = x;",
" while (fa[r] != r) r = fa[r]; //找到根节点",
" for (int i = x, j; i != r; i = j)",
" j = fa[i], fa[i] = r; //把路径上的元素的集改为根节点",
" return r;",
"}",
"void merge(int x, int y) {",
" x = Find(x);",
" y = Find(y);",
" if (ht[x] == ht[y])",
" ht[x] = ht[x] + 1, fa[y] = x;",
" else if (ht[x] < ht[y])",
" fa[x] = y;",
" else",
" fa[y] = x;",
"}",
],
"prefix": "disjointset",
"description": "并查集"
},
"point": {
"prefix": "point",
"body": [
"struct point {double x, y;} a[N];",
"double getdis(point a, point b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}"
],
"description": "点/求距离"
},
"BigInt": {
"body": [
"struct BigInteger {",
" static const int BASE = 100000000; //和WIDTH保持一致",
" static const int WIDTH = 8; //八位一存储,如修改记得修改输出中的%08d",
" bool sign; //符号, 0表示负数",
" size_t length; //位数",
" vector<int> num; //反序存",
" //构造函数",
" BigInteger(long long x = 0) { *this = x; }",
" BigInteger(const string &x) { *this = x; }",
" BigInteger(const BigInteger &x) { *this = x; }",
" //剪掉前导0，并且求一下数的位数",
" void cutLeadingZero() {",
" while (num.back() == 0 && num.size() != 1) {",
" num.pop_back();",
" }",
" int tmp = num.back();",
" if (tmp == 0) {",
" length = 1;",
" } else {",
" length = (num.size() - 1) * WIDTH;",
" while (tmp > 0) {",
" length++;",
" tmp /= 10;",
" }",
" }",
" }",
" //赋值运算符",
" BigInteger &operator=(long long x) {",
" num.clear();",
" if (x >= 0) {",
" sign = true;",
" } else {",
" sign = false;",
" x = -x;",
" }",
" do {",
" num.push_back(x % BASE);",
" x /= BASE;",
" } while (x > 0);",
" cutLeadingZero();",
" return *this;",
" }",
" BigInteger &operator=(const string &str) {",
" num.clear();",
" sign = (str[0] != '-'); //设置符号",
" int x, len = (str.size() - 1 - (!sign)) / WIDTH + 1;",
" for (int i = 0; i < len; i++) {",
" int End = str.size() - i * WIDTH;",
" int start = max((int)(!sign), End - WIDTH); //防止越界",
" sscanf(str.substr(start, End - start).c_str(), \" % d \", &x);",
" num.push_back(x);",
" }",
" cutLeadingZero();",
" return *this;",
" }",
" BigInteger &operator=(const BigInteger &tmp) {",
" num = tmp.num;",
" sign = tmp.sign;",
" length = tmp.length;",
" return *this;",
" }",
" //绝对值",
" BigInteger abs() const {",
" BigInteger ans(*this);",
" ans.sign = true;",
" return ans;",
" }",
" //正号",
" const BigInteger &operator+() const { return *this; }",
" //负号",
" BigInteger operator-() const {",
" BigInteger ans(*this);",
" if (ans != 0) ans.sign = !ans.sign;",
" return ans;",
" }",
" // + 运算符",
" BigInteger operator+(const BigInteger &b) const {",
" if (!b.sign) {",
" return *this - (-b);",
" }",
" if (!sign) {",
" return b - (-*this);",
" }",
" BigInteger ans;",
" ans.num.clear();",
" for (int i = 0, g = 0;; i++) {",
" if (g == 0 && i >= num.size() && i >= b.num.size()) break;",
" int x = g;",
" if (i < num.size()) x += num[i];",
" if (i < b.num.size()) x += b.num[i];",
" ans.num.push_back(x % BASE);",
" g = x / BASE;",
" }",
" ans.cutLeadingZero();",
" return ans;",
" }",
" // - 运算符",
" BigInteger operator-(const BigInteger &b) const {",
" if (!b.sign) {",
" return *this + (-b);",
" }",
" if (!sign) {",
" return -((-*this) + b);",
" }",
" if (*this < b) {",
" return -(b - *this);",
" }",
" BigInteger ans;",
" ans.num.clear();",
" for (int i = 0, g = 0;; i++) {",
" if (g == 0 && i >= num.size() && i >= b.num.size()) break;",
" int x = g;",
" g = 0;",
" if (i < num.size()) x += num[i];",
" if (i < b.num.size()) x -= b.num[i];",
" if (x < 0) {",
" x += BASE;",
" g = -1;",
" }",
" ans.num.push_back(x);",
" }",
" ans.cutLeadingZero();",
" return ans;",
" }",
" // * 运算符",
" BigInteger operator*(const BigInteger &b) const {",
" int lena = num.size(), lenb = b.num.size();",
" BigInteger ans;",
" for (int i = 0; i < lena + lenb; i++) ans.num.push_back(0);",
" for (int i = 0, g = 0; i < lena; i++) {",
" g = 0;",
" for (int j = 0; j < lenb; j++) {",
" long long x = ans.num[i + j];",
" x += (long long)num[i] * (long long)b.num[j];",
" ans.num[i + j] = x % BASE;",
" g = x / BASE;",
" ans.num[i + j + 1] += g;",
" }",
" }",
" ans.cutLeadingZero();",
" ans.sign = (ans.length == 1 && ans.num[0] == 0) || (sign == b.sign);",
" return ans;",
" }",
" //*10^n 大数除大数中用到",
" BigInteger e(size_t n) const {",
" int tmp = n % WIDTH;",
" BigInteger ans;",
" ans.length = n + 1;",
" n /= WIDTH;",
" while (ans.num.size() <= n) ans.num.push_back(0);",
" ans.num[n] = 1;",
" while (tmp--) ans.num[n] *= 10;",
" return ans * (*this);",
" }",
" // /运算符 (大数除大数)",
" BigInteger operator/(const BigInteger &b) const {",
" BigInteger aa((*this).abs());",
" BigInteger bb(b.abs());",
" if (aa < bb) return 0;",
" char *str = new char[aa.length + 1];",
" memset(str, 0, sizeof(char) * (aa.length + 1));",
" BigInteger tmp;",
" int lena = aa.length, lenb = bb.length;",
" for (int i = 0; i <= lena - lenb; i++) {",
" tmp = bb.e(lena - lenb - i);",
" while (aa >= tmp) {",
" str[i]++;",
" aa = aa - tmp;",
" }",
" str[i] += '0';",
" }",
" BigInteger ans(str);",
" delete[] str;",
" ans.sign = (ans == 0 || sign == b.sign);",
" return ans;",
" }",
" // %运算符",
" BigInteger operator%(const BigInteger &b) const {",
" return *this - *this / b * b;",
" }",
" // ++ 运算符",
" BigInteger &operator++() {",
" *this = *this + 1;",
" return *this;",
" }",
" // -- 运算符",
" BigInteger &operator--() {",
" *this = *this - 1;",
" return *this;",
" }",
" // += 运算符",
" BigInteger &operator+=(const BigInteger &b) {",
" *this = *this + b;",
" return *this;",
" }",
" // -= 运算符",
" BigInteger &operator-=(const BigInteger &b) {",
" *this = *this - b;",
" return *this;",
" }",
" // *=运算符",
" BigInteger &operator*=(const BigInteger &b) {",
" *this = *this * b;",
" return *this;",
" }",
" // /= 运算符",
" BigInteger &operator/=(const BigInteger &b) {",
" *this = *this / b;",
" return *this;",
" }",
" // %=运算符",
" BigInteger &operator%=(const BigInteger &b) {",
" *this = *this % b;",
" return *this;",
" }",
" // < 运算符",
" bool operator<(const BigInteger &b) const {",
" if (sign != b.sign) //正负，负正",
" {",
" return !sign;",
" } else if (!sign && !b.sign) //负负",
" {",
" return -b < -*this;",
" }",
" //正正",
" if (num.size() != b.num.size()) return num.size() < b.num.size();",
" for (int i = num.size() - 1; i >= 0; i--)",
" if (num[i] != b.num[i]) return num[i] < b.num[i];",
" return false;",
" }",
" bool operator>(const BigInteger &b) const {",
" return b < *this;",
" } // > 运算符",
" bool operator<=(const BigInteger &b) const {",
" return !(b < *this);",
" } // <= 运算符",
" bool operator>=(const BigInteger &b) const {",
" return !(*this < b);",
" } // >= 运算符",
" bool operator!=(const BigInteger &b) const {",
" return b < *this || *this < b;",
" } // != 运算符",
" bool operator==(const BigInteger &b) const {",
" return !(b < *this) && !(*this < b);",
" } //==运算符",
" // 逻辑运算符",
" bool operator||(const BigInteger &b) const {",
" return *this != 0 || b != 0;",
" } // || 运算符",
" bool operator&&(const BigInteger &b) const {",
" return *this != 0 && b != 0;",
" } // && 运算符",
" bool operator!() { return (bool)(*this == 0); } // ！ 运算符",
"",
" //重载<<使得可以直接输出大数",
" friend ostream &operator<<(ostream &out, const BigInteger &x) {",
" if (!x.sign) out << '-';",
" out << x.num.back();",
" for (int i = x.num.size() - 2; i >= 0; i--) {",
" char buf[10];",
" //如WIDTH和BASR有变化,此处要修改为%0(WIDTH)d",
" sprintf(buf, \" % 08 d \", x.num[i]);",
" for (int j = 0; j < strlen(buf); j++) out << buf[j];",
" }",
" return out;",
" }",
" //重载>>使得可以直接输入大数",
" friend istream &operator>>(istream &in, BigInteger &x) {",
" string str;",
" in >> str;",
" size_t len = str.size();",
" int start = 0;",
" if (str[0] == '-') start = 1;",
" if (str[start] == '\\0') return in;",
" for (int i = start; i < len; i++) {",
" if (str[i] < '0' || str[i] > '9') return in;",
" }",
" x.sign = !start;",
" x = str.c_str();",
" return in;",
" }",
"};",
"",
"BigInteger ans[100][3][3];",
"BigInteger mpow(BigInteger a, BigInteger b) {",
" BigInteger res = 1;",
" for (BigInteger i = 0; i < b; i = i + 1) {",
" res *= a;",
" }",
" return res;",
"",
"}"
],
"prefix": "bigint",
"description": "大数类"
},
"GCCo2o3": {
"body": [
"#pragma GCC target(\"avx,sse2,sse3,sse4,popcnt\")",
"#pragma GCC optimize(\"O2,O3,Ofast,inline,unroll-all-loops,-ffast-math\")",
],
"description": "全部GCC编译选项",
"prefix": "o2o3"
},
"ComboNum": {
"body": [
"ll C(ll n, ll m) {//组合数 C(n,m)",
" if (m < 0) return 0;",
" if (n < m) return 0;",
" if (m > n - m) m = n - m;",
" ll up = 1, down = 1;",
" for (ll i = 0; i < m; i++) {",
" up = up * (n - i) % mod;",
" down = down * (i + 1) % mod;",
" }",
" return up * getInv(down) % mod;",
"}",
],
"description": "组合数 Cnm",
"prefix": "combo"
},
"DividIntoPrime": {
"body": [
"const int maxn = 1005;",
"ll prime_num[maxn], num; //质因数的个数",
"ll prime[maxn];",
"void divid(ll n){ //分解正整数n",
" num = 0;",
" if (n % 2 == 0) {",
" ll term = 0;",
" while (n % 2 == 0) {",
" term++;",
" n /= 2;",
" }",
" prime_num[num] = term;",
" prime[num++] = 2;",
" }",
" for (ll i = 3; i * i <= n; i += 2)",
" if (n % i == 0) {",
" ll term = 0;",
" while (n % i == 0) {",
" term++;",
" n /= i;",
" }",
" prime_num[num] = term;",
" prime[num++] = i;",
" }",
" if (n > 1) {",
" prime[num] = n;",
" prime_num[num++] = 1;",
" }",
"}",
],
"description": "分解质因数",
"prefix": "divid"
},
"AppleBox": {
"body": [
"const int maxn = 1005;",
"ll dp[maxn][maxn];",
"ll f(ll m, ll n){ // m个苹果 n个篮子",
" dp[0][0] = 1;",
" for (int i = 1; i <= n; ++i)",
" for (int j = 0; j <= m; ++j)",
" if (j >= i) dp[i][j] = (dp[i][j - i] + dp[i - 1][j]) % mod;",
" else dp[i][j] = dp[j][j];",
" return dp[n][m];",
"}",
],
"description": "拆分方式种数",
"prefix": "apple"
},
"CALC": {
"body": [
"namespace CALC{",
" inline ll add(ll x,ll y){return (x+y>=mod)?(x+y-mod):(x+y);}",
" inline ll mns(ll x,ll y){return (x-y<0)?(x-y+mod):(x-y);}",
" inline ll mul(ll x,ll y){return x*y%mod;}",
" inline void upd(ll &x,ll y){x=(x+y>=mod)?(x+y-mod):(x+y);}",
" inline void dec(ll &x,ll y){x=(x-y<0)?(x-y+mod):(x-y);}",
" inline ll qpow(ll x,ll sq){ll res=1;for(;sq;sq>>=1,x=mul(x,x))if(sq&1)res=mul(res,x);return res;}",
],
"description": "取模下的运算",
"prefix": "CALC"
},
"DuJiao": {
"body": [
"#include <bits/stdc++.h>",
"using namespace std;",
"#define rep(i, a, n) for (int i = a; i < n; i++)",
"#define pb push_back",
"typedef long long ll;",
"#define SZ(x) ((ll)(x).size())",
"typedef vector<ll> VI;",
"typedef pair<ll, ll> PII;",
"const ll mod = 1e9+7;",
"ll powmod(ll a, ll b) {",
" ll res = 1;",
" a %= mod;",
" assert(b >= 0);",
" for (; b; b >>= 1) {",
" if (b & 1)",
" res = res * a % mod;",
" a = a * a % mod;",
" }",
" return res;",
"}",
"// head",
"",
"ll _, n;",
"namespace linear_seq {",
"const ll N = 10010;",
"ll res[N], base[N], _c[N], _md[N];",
"",
"vector<ll> Md;",
"void mul(ll *a, ll *b, ll k) {",
" rep(i, 0, k + k) _c[i] = 0;",
" rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] =",
" (_c[i + j] + a[i] * b[j]) % mod;",
" for (ll i = k + k - 1; i >= k; i--)",
" if (_c[i])",
" rep(j, 0, SZ(Md)) _c[i - k + Md[j]] =",
" (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;",
" rep(i, 0, k) a[i] = _c[i];",
"}",
"ll solve(ll n, VI a, VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...",
" // printf(\" % d\\ n \",SZ(b));",
" ll ans = 0, pnt = 0;",
" ll k = SZ(a);",
" assert(SZ(a) == SZ(b));",
" rep(i, 0, k) _md[k - 1 - i] = -a[i];",
" _md[k] = 1;",
" Md.clear();",
" rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);",
" rep(i, 0, k) res[i] = base[i] = 0;",
" res[0] = 1;",
" while ((1ll << pnt) <= n)",
" pnt++;",
" for (ll p = pnt; p >= 0; p--) {",
" mul(res, res, k);",
" if ((n >> p) & 1) {",
" for (ll i = k - 1; i >= 0; i--)",
" res[i + 1] = res[i];",
" res[0] = 0;",
" rep(j, 0, SZ(Md)) res[Md[j]] =",
" (res[Md[j]] - res[k] * _md[Md[j]]) % mod;",
" }",
" }",
" rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;",
" if (ans < 0)",
" ans += mod;",
" return ans;",
"}",
"VI BM(VI s) {",
" VI C(1, 1), B(1, 1);",
" ll L = 0, m = 1, b = 1;",
" rep(n, 0, SZ(s)) {",
" ll d = 0;",
" rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;",
" if (d == 0)",
" ++m;",
" else if (2 * L <= n) {",
" VI T = C;",
" ll c = mod - d * powmod(b, mod - 2) % mod;",
" while (SZ(C) < SZ(B) + m)",
" C.pb(0);",
" rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;",
" L = n + 1 - L;",
" B = T;",
" b = d;",
" m = 1;",
" } else {",
" ll c = mod - d * powmod(b, mod - 2) % mod;",
" while (SZ(C) < SZ(B) + m)",
" C.pb(0);",
" rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;",
" ++m;",
" }",
" }",
" return C;",
"}",
"ll gao(VI a, ll n) {",
" VI c = BM(a);",
" c.erase(c.begin());",
" rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;",
" return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));",
"}",
"}; // namespace linear_seq",
"",
"inline ll read() {",
" ll s = 0, w = 1;",
" char ch = getchar();",
" while (ch < 48 || ch > 57) {",
" if (ch == '-')",
" w = -1;",
" ch = getchar();",
" }",
" while (ch >= 48 && ch <= 57)",
" s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();",
" return s * w;",
"}",
"int main() {",
" ll n = read();",
" VI a={ 1, 4, 10, 20, 35, 56, 84, 120, 165, 220};",
" printf(\"%lld\\n\", linear_seq::gao(a, n - 1));",
"}",
],
"prefix": "DuJiaoShai",
"description": "杜教筛"
},
"BIT": {
"body": [
"#define lowbit(x) ((x) & (-x))",
"ll tree[N];",
"inline void update(int i, ll x) {",
" for (int pos = i; pos < N; pos += lowbit(pos)) tree[pos] += x;",
"}",
"inline ll query(int n) {",
" ll ans = 0;",
" for (int pos = n; pos; pos -= lowbit(pos)) ans += tree[pos];",
" return ans;",
"}",
],
"description": "Binary Index Tree",
"prefix": "BIT"
},
"128INT": {
"body": [
"inline __int128 read() {",
" __int128 x = 0, f = 1;",
" char ch = getchar();",
" while (ch < '0' || ch > '9') {",
" if (ch == '-') f = -1;",
" ch = getchar();",
" }",
" while (ch >= '0' && ch <= '9') {",
" x = x * 10 + ch - '0';",
" ch = getchar();",
" }",
" return x * f;",
"}",
"inline void print(__int128 x) {",
" if (x < 0) {",
" putchar('-');",
" x = -x;",
" }",
" if (x > 9) print(x / 10);",
" putchar(x % 10 + '0');",
"}",
],
"description": "int128",
"prefix": "128INT"
},
"Graph": {
"body": [
"int to[N << 1], nxt[N << 1], head[N], wt[N << 1], tot;",
"inline void init() { memset(head, -1, sizeof(head)), tot = 0; }",
"inline void add(int u, int v, int val) {",
" to[++tot] = v;",
" nxt[tot] = head[u];",
" wt[tot] = val;",
" head[u] = tot;",
"}",
],
"prefix": "graph",
"description": "Build Graph"
},
"segment tree": {
"body": [
"#include <bits/stdc++.h>",
"#define sc(x) scanf(\"%lld\", &(x))",
"#define pr(x) printf(\"%lld\\n\", (x))",
"//线段树维护区间和",
"using namespace std;",
"typedef long long ll;",
"const int N = 1e5 + 7;",
"const ll mod = 1e9 + 7;",
"ll a[N], tree[N << 2], lazy[N << 2], n;",
"ll m, op, x, y, k;",
"#define ls (p << 1)",
"#define rs (p << 1 | 1)",
"#define mid (l + r >> 1)",
"void bulid(ll p = 1, ll l = 1, ll r = n) {",
" lazy[p] = 0;",
" if (l == r) {",
" tree[p] = a[l];",
" return;",
" }",
" bulid(ls, l, mid);",
" bulid(rs, mid + 1, r);",
" tree[p] = tree[ls] + tree[rs];",
"}",
"inline void PushDown(ll p, ll tot) {",
" lazy[ls] += lazy[p];",
" lazy[rs] += lazy[p];",
" tree[ls] += lazy[p] * (tot - tot / 2);",
" tree[rs] += lazy[p] * (tot / 2);",
" lazy[p] = 0;",
"}",
"void add(ll x, ll y, ll val, ll p = 1, ll l = 1, ll r = n) {",
" if (x <= l && r <= y) { //当前区间可被所求区间覆盖",
" lazy[p] += val;",
" tree[p] += val * ((ll)(r - l + 1));",
" return;",
" }",
" PushDown(p, r - l + 1);",
" if (x <= mid) add(x, y, val, ls, l, mid);",
" if (y > mid) add(x, y, val, rs, mid + 1, r);",
" tree[p] = tree[ls] + tree[rs];",
"}",
"ll query(ll x, ll y, ll p = 1, ll l = 1, ll r = n) {",
" if (x <= l && r <= y) return tree[p];",
" ll res = 0;",
" if (lazy[p]) PushDown(p, r - l + 1);",
" if (x <= mid) res += query(x, y, ls, l, mid);",
" if (y > mid) res += query(x, y, rs, mid + 1, r);",
" return res;",
"}",
"int main() {",
" sc(n), sc(m);",
" for (int i = 1; i <= n; ++i) sc(a[i]);",
" bulid();",
" while (m--) {",
" sc(op);",
" if (op & 1) {",
" sc(x), sc(y), sc(k);",
" add(x, y, k);",
" } else {",
" sc(x), sc(y);",
" pr(query(x, y));",
" }",
" }",
" return 0;",
"}",
],
"description": "线段树",
"prefix": "segment"
},
"netcontest": {
"body": [
"#pragma GCC target(\"avx,sse2,sse3,sse4,popcnt\")",
"#pragma GCC optimize(\"O2,O3,Ofast,inline,unroll-all-loops,-ffast-math\")",
"#include<bits/stdc++.h>",
"#define sc(x) scanf(\"%lld\", &(x))",
"#define pr(x) printf(\"%lld\\n\", (x))",
"using namespace std;",
"typedef long long ll;",
"const int N = 1e5 + 7;",
"const ll mod = 1e9 + 7;",
"inline ll read() ;",
"int main(){",
"\t$0\n\treturn 0;",
"}",
"inline ll read() {",
" ll s = 0, f = 1;",
" char ch;",
" do {",
" ch = getchar();",
" if (ch == '-') f = -1;",
" } while (ch < 48 || ch > 57);",
" while (ch >= 48 && ch <= 57)",
" s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();",
" return s * f;",
"}",
],
"prefix": "netcon",
"description": "网赛板子"
},
"Eular": {
"body": [
"ll eular(ll n){",
" ll ret=1,i;",
" for (i=2;i*i<=n;i++)",
" if (n%i==0){",
" n/=i,ret*=i-1;",
" while (n%i==0)",
" n/=i,ret*=i;",
" }",
" if (n>1)",
" ret*=n-1;",
" return ret;",
"}",
],
"description": "求一个数的欧拉函数O(sqrt(n))",
"prefix": "Eular",
},
"eular": {
"body": [
"//欧拉线性筛：在线性时间内筛素数的同时求出所有数的欧拉函数",
"int tot;",
"int phi[N];//保存各个数字的欧拉函数 ",
"int prime[N]; //按顺序保存素数",
"bool mark[N];//判断是否是素数",
"void pre(){",
" phi[1] = 1;",
" for(int i = 2; i <= N; i++){//相当于分解质因数的逆过程",
" if(!mark[i]){",
" prime[++tot] = i;",
" phi[i] = i-1;",
" }",
" for(int j = 1; j <= tot; j++){",
" if(i * prime[j] > N) break;",
" mark[i * prime[j]] = 1;//确定i*prime[j]不是素数",
" if(i % prime[j] == 0){//判断prime[j] 是否为 i的约数",
" phi[i * prime[j]] = phi[i] * prime[j];",
" break;",
" }",
" else{//prime[j] - 1 就是 phi[prime[j]],利用了欧拉函数的积性",
" phi[i * prime[j]] = phi[i] * (prime[j] - 1);",
" }",
" }",
" }",
"}",
],
"description": "筛欧拉函数 + 素数",
"prefix": "getphi",
},
"sieve": {
"body": [
"bool notprime[N];",
"int primes[N], pcnt = 0;",
"inline void pre() {",
" notprime[1] = 1;",
" for (int i = 2, n = sqrt(N) + 1; i <= n; ++i) {",
" if (!notprime[i]) {",
" for (int j = N / i; j >= i; --j) {",
" if (!notprime[j]) notprime[i * j] = 1;",
" }",
" }",
" }",
" primes[++pcnt] = 2;",
" for (int i = 3; i < N; ++i)",
" if (!notprime[i]) primes[++pcnt] = i;",
"}"
],
"description": "埃筛",
"prefix": "sieve"
}
} 
投递字节跳动等公司10个岗位 >
