zhyDaDa的个人站点studyCPP高级操作___2023-09-29
zhyDaDa的个人站点studyCPP高级操作___2023-09-29
zhyDaDa的个人站点

CPP高级操作___2023-09-29

zhyDaDa
study

CPP高级操作___2023-09-29

目录

内置功能函数

迭代器的使用

迭代器（Iterator）是一种用于遍历容器（如数组、向量、链表等）中元素的对象。迭代器提供了一种通用的方式来访问容器中的元素，而不需要关心容器的具体实现方式。
迭代器的使用方式类似于指针，它可以指向容器中的某个元素，并支持指针运算（如 ++、–、* 等）。
迭代器一般遵循左闭右开的原则: [begin, end)

vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); it++) {
    cout << *it << " ";
}
cout << endl;

begin() 返回指向容器起始位置的迭代器，end() 返回指向容器末尾元素的下一个位置的迭代器。

由于所有函数都默认正向遍历容器, 为了实现反向遍历, 可以用reverse_iterator对象, 其用法和iterator类似, 只是方向相反:

vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.rbegin(); it != vec.rend(); it++) {
    cout << *it << " ";
}
cout << endl;

rbegin() 返回指向容器末尾元素的迭代器，rend() 返回指向容器起始位置前一个元素的迭代器。

Lambda表达式

为了避免显式声明函数的麻烦, Lambda表达式可以用来定义一个匿名函数, 从而简化代码。
其语法如下:

[ capture ] ( params ) -> ret { body }

参数说明:

  • capture: 捕获列表, 指定了Lambda表达式可以使用的外部变量或对象
  • [] 表示不捕获任何外部变量
  • [&] 表示按引用捕获所有外部变量
  • [=] 表示按值捕获所有外部变量
  • [&, x] 表示x按引用捕获, 其余按值捕获
  • [=, &x] 表示x按值捕获, 其余按引用捕获
  • [=, &x, &y] 表示x和y按引用捕获, 其余按值捕获
  • [&, x, &y] 表示x按值捕获, y按引用捕获, 其余按引用捕获
  • params: 形参列表, 指定了传递给Lambda表达式的参数
  • ret: 返回值类型, 指定了返回类型
  • body: 函数体, 指定了函数要执行的操作
int x = 10;
auto f = [x](int y) -> int { return x + y; };
cout << f(20) << endl;

上述函数声明亦可简写做:
auto f = [=](int y){ return x + y; };

sort

sort()函数可以用来对容器中的元素进行排序
对于对象数组, 要使用自定义的比较器
其参数如下:

  • first和last: 待排序区间(左闭右开)
  • comp: 比较器, 可以是函数对象或者Lambda表达式
struct Student {
    string name;
    int score;
};

vector<Student> vec = {{"Tom", 90}, {"Jerry", 80}, {"Jack", 70}};
sort(vec.begin(), vec.end(), [](const Student& a, const Student& b)
     { return a.score > b.score; });

这里必须要深刻理解比较器的含义:

  • 当返回值为true的时候, 说明第一个元素在前
  • 当返回值为false的时候, 说明第二个元素在前

而比较器在调用的时候, 都是后面的元素作为第一个参数, 前面的元素作为第二个参数.
由此, 对于分数相同的两人, 比较器返回false, 在原顺序中靠前的学生作为第二个参数, 就会排在前面, 即, 与原先顺序一致
这也就是为什么比较器中要写>而非>=的原因

greater<int>{}是C++内置的一个比较函数, 其效果等同于[](int a, int b){return a > b;}
相应的less<int>{}的效果等同于[](int a, int b){return a < b;}

reverse

reverse()函数可以把容器中的元素顺序进行反转

vector<int> vec = {1, 2, 3, 4, 5};
reverse(vec.begin(), vec.end());

accumulate

accumulate()函数可以将容器中元素的值进行累加, 并返回累加的结果
其第三个参数表示初始值

vector<int> vec = {1, 2, 3, 4, 5};
cout << accumulate(vec.begin(), vec.end(), 10) << endl;
// 25

count_if

count_if()函数可以用来统计容器中满足指定条件的元素个数

vector<int> vec = {1, 2, 3, 4, 5};
cout << count_if(vec.begin(), vec.end(), [](int i)
                 { return i % 2 == 0; }) << endl;
// 2

memset

memset()函数可以用来对一个数组进行初始化
其参数如下:

  • ptr: 待初始化的数组
  • value: 初始化的值
  • num: 初始化元素的个数
int arr[5];
memset(arr, 0, sizeof(arr));

之所以用sizeof()函数来指定初始化元素的个数, 是因为ta能够自动计算出数组的长度, 从而保证代码的可移植性

next_permutation

next_permutation(start, end)能将序列重新排列为下一个字典序更大的排列, 如果不存在下一个更大的排列, 则返回false, 否则返回true
一般可以用于输出全排列

vector<int> vec = {1, 2, 3};
do {
    cout << vec[0] << " " << vec[1] << " " << vec[2] << endl;
} while (next_permutation(vec.begin(), vec.end()));

单次的时间复杂度为$O(n)$, 全排列的时间复杂度为$O(n!)$

max_element & min_element

max_element()函数可以找出容器中的最大元素
min_element()函数可以找出容器中的最小元素
需要注意的是, 其返回值是迭代器, 指向最大/最小元素

vector<int> vec = {1, 2, 3, 4, 5};
cout << *max_element(vec.begin(), vec.end()) << endl;
cout << *min_element(vec.begin(), vec.end()) << endl;

upper_bound & lower_bound

upper_bound()函数可以找出容器中第一个大于某个值的元素
lower_bound()函数可以找出容器中第一个不小于某个值的元素
需要注意的是, 其返回值是迭代器, 指向该元素

vector<int> vec = {1, 2, 3, 3, 4, 5};
cout << upper_bound(vec.begin(), vec.end(), 3) - vec.begin() << endl;
cout << lower_bound(vec.begin(), vec.end(), 3) - vec.begin() << endl;

其结果是: 

4
2

其内部原理就是二分查找, 因此时间复杂度为$O(logn)$

find

find()函数可以在容器中找到第一个和指定值相等的元素, 并返回指向该元素的迭代器

vector<int> vec = {1, 2, 3, 4, 5};
cout << find(vec.begin(), vec.end(), 3) - vec.begin() << endl;

find_if()函数可以在容器中找到第一个满足指定条件的元素, 并返回指向该元素的迭代器

vector<int> vec = {1, 2, 3, 4, 5};
cout << find_if(vec.begin(), vec.end(), [](int i)
                { return i % 2 == 0; }) - vec.begin() << endl;

find()和find_if()函数的时间复杂度为$O(n)$

transform

transform()函数可以将一个序列中的每个元素都应用一个函数，并将结果存储到另一个序列中

可以和JavaScipt里面的map函数做类比

其参数如下:

  • first1和last1: 输入区间
  • first2: 输出区间的起始位置
  • op: 用于元素转换的函数
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> vec(n);
transform(arr, arr + n, vec.begin(), [](int i)
          { return i * i; });
for (auto i : vec)
    cout << i << " ";

partition

partition()函数用于把容器中的元素按照指定的条件分成两部分,满足条件的放在前面,不满足条件的放在后面,返回一个迭代器,指向第二部分的第一个元素

注意, 这里的区间都是左闭右开区间:

  • 输入区间是[first, last)
  • 返回值为true的区间是[first, mid)
  • 返回值为false的区间是[mid, last)
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    auto mid = partition(arr, arr + n, [&](int i)
                         { return i % 2 != 0; });
    cout << "Odd elements: ";
    transform(arr, mid, ostream_iterator<int>(cout, " "), [](int i)
              { return i; });
    cout << endl;
    cout << "Even elements: ";
    transform(mid, arr + n, ostream_iterator<int>(cout, " "), [](int i)
              { return i; });
    cout << endl;

运行结果:

Odd elements: 1 9 3 7 5 
Even elements: 6 4 8 2

注意到,partition()函数改变了元素原有的顺序
要保持原有顺序,可以用stable_partition()

partial_sum

partial_sum()函数可以将一个序列中的元素进行累加, 并将结果存储到另一个序列中
非常适合用于计算前缀和

vector<int> vec = {1, 2, 3, 4, 5};
vector<int> sum(vec.size());
partial_sum(vec.begin(), vec.end(), sum.begin());
// sum = {1, 3, 6, 10, 15}

iota

iota()函数可以用来给容器中的元素赋值, 其值为连续递增的序列, 其参数如下:

  • first: 起始位置
  • last: 结束位置
  • val: 赋值的起始值, 第一个元素为val, 第二个元素为val+1, 以此类推
vector<int> vec(5);
iota(vec.begin(), vec.end(), 3);
// vec = {3, 4, 5, 6, 7}

“iota” 这个名字是第九个希腊字母: $\iota$, 在数学中，”iota” 通常用来表示自然数序列的起始值

move

move()函数可以将一个对象的所有权转移给另一个对象
简单理解: =就是拷贝, move()就是剪切 

vector<int> vec1 = {1, 2, 3, 4, 5};
vector<int> vec2 = move(vec1);

move()函数将vec1的所有权转移到vec2之后, vec1就变成了空的, 内容转到了vec2里面

range::nth_element

nth_element()函数可以用来找出容器中的第k大/小的元素
其本质就是选择排序, 当第k个数左侧均小于ta, 右侧均大于ta时, 第k大/小的元素也就找到了 

vector<int> bbb  = {7, 1, 6, 3, 4, 5, 2};
nth_element(bbb.begin(), bbb.begin() + 3, bbb.end());

此时bbb[3]的值就被确定了, 此时的bbb序列就是: 

2 1 3 4 6 5 7

值得注意的是, 这个操作能确定前k-1个数都是小于bbb[k]的
换言之, 前k个数便是最小的k个数
从而可以用来实现 “数组前k小的数之和” 这种问题 

    ranges::nth_element(aaa, aaa.begin() + k);
    return accumulate(aaa.begin(), aaa.begin() + k, 0LL);

数据结构

用 using 在代码中声明结构的缩写

使用下面这种写法能省不少打字时间!

using pii = pair<int,int>;
Graph(int n, vector<vector<int>>& edges) {
    this->graph = vector<vector<pii>>(n);

数值常量

INT_MIN: int类型的最小值
INT_MAX: int类型的最大值
LLONG_MIN: long long类型的最小值
LLONG_MAX: long long类型的最大值

vector

一些实用的成员函数

  • vector.back(): 返回容器中的最后一个元素的引用
  • vector.front(): 返回容器中的第一个元素的引用
  • vector.begin(): 返回指向容器起始位置的迭代器
  • vector.end(): 返回指向容器尾元素的下一个位置的迭代器

合并

两个vector可以通过insert()函数合并

vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
a.insert(a.end(), b.begin(), b.end());
// a = {1, 2, 3, 4, 5, 6}
// b = {4, 5, 6}

去重

数组去重

链表

cpp库中提供了一些链表的操作函数, 例如list和forward_list

声明

list<int> l;

插入

push_back(x)和push_front(x)函数可以向容器中插入元素x

l.push_back(1);
l.push_front(2);

删除

pop_back()和pop_front()函数可以从容器中删除元素

l.pop_back();
l.pop_front();

访问

back()和front()函数可以访问容器中的最后一个元素和第一个元素

在任意位置插入

insert(it, x)函数可以在迭代器it指向的位置插入元素x

list<int> l = {1, 2, 3, 4, 5};
auto it = l.begin();
i
l.insert(it, 6);
// l = {1, 2, 6, 3, 4, 5}

删除任意位置的元素

erase(it)函数可以删除迭代器it指向的元素

list<int> l = {1, 2, 3, 4, 5};
auto it = l.begin();
it++;
l.erase(it);
// l = {1, 2, 4, 5}

删除区间内的元素

erase(it1, it2)函数可以删除区间[it1, it2)内的元素

list<int> l = {1, 2, 3, 4, 5};
auto it1 = l.begin();
auto it2 = l.begin();
it1+=1;
it2+=3;
l.erase(it1, it2);
// l = {1, 5}

multiset

multiset是一个可以维护有序元素集合的容器, 并且可以重复

声明

multiset<int> s;

如果有需要也可以设置比较器 

struct Student {
    string name;
    int score;
};

multiset<Student, function<bool(Student, Student)>>
    stu([](Student a, Student b) -> bool {
        return a.score < b.score;
    });

插入

insert(x)和emplace(x)函数可以向容器中插入元素x
其中insert(x)函数的时间复杂度为$O(logn)$, 而emplace(x)函数的时间复杂度为$O(1)$, 因此推荐使用emplace(x)函数

原因是insert(x)函数会先创建一个临时的对象, 然后再插入, 而emplace(x)函数直接在容器中构造对象

删除

erase(x)函数可以删除容器中值为x的元素
注意: 如果有多个一样的值, 只会删一个
erase(first, last)函数可以删除容器中从迭代器first到last之间的元素

multiset<int> s = {1, 2, 3, 4, 5, 5, 5, 6};
s.erase(5);
for (auto i : s)
    cout << i << " ";
cout << endl;

运行结果:

1 2 3 4 5 5 6

其他成员函数和set类似

pair

pair<type1, type2>可以用于存储两种不同类型的对象
其成员变量可以用first和second访问

pair<string, int> p = {"Tom", 20};
cout << p.first << " " << p.second << endl;

在lambda表达式中可以用auto来代替pair 

sort(vec.begin(), end, [](auto& a, auto& b) { return pair{ a[1], a[0] } > pair{ b[1], b[0] }; });

如果不给定比较方法, 默认按照first对应的数据作为排序依据

这也是重要技巧, 可以同时比较两个值
常见的应用场景: 分数一致的情况下, 按ID的字典序排序

解析赋值

从一个pair中解析出两个值, 并赋值给两个变量

pair<int, int> p = {1, 2};
auto [a, b] = p;
// a = 1, b = 2

线段树

用于快速处理前缀和的问题, 最大的优势是可以在$O(logn)$的时间内完成更新和查询, 其时间复杂度与数据量无关 

int c[1000006];

int lowbit(int x)
{
    return x & (-x);
}

void update(int x, int v, int n)
{
    for (; x <= n; x += lowbit(x))
        c[x] += v;
}

int sum(int x)
{
    int ans = 0;
    for (; x; x -= lowbit(x))
        ans += c[x];
    return ans;
}

树状数组

用于快速处理前缀和的问题, 最大的优势是可以在$O(logn)$的时间内完成更新和查询, 其时间复杂度与数据量无关
当需要”单点修改, 区间查询“的时候, 可以使用树状数组 

class bitree{
    vector<int> data;
    int n = 0;
public:
    bitree(int size): data(size+1), n(size) {
    }
    int size() {return n;}
    void add(int idx, int v){
        while(idx<=n){
            data[idx]+=v;
            idx += lowbit(idx);
        }
    }
    int query(int idx){
        int res = 0;
        while(idx>0){
            res+=data[idx];
            idx-=lowbit(idx);
        }
        return res;
    }
    int lowbit(int x){
        return x&-x;
    }

};

二进制运算

位图

在哈希这份笔记中摘录过来的

通常一个100位的int数组要占据400字节的内存
而我们现在只需要记录是或不是的信息, 那么完全不需要用int来记录, 为了将内存使用率提高到极致, 我们可以使用位图, 即只用1bit来记录是否存在

假定我们将信息记录在一个int arr[]中, 并且我们的信息对象是第i位bit

以下的好理解是为了方便理解的普通代码, 为了加速实际应当使用位运算的代码

首先我们要定位到这个对象的位置:

  • 该位置对应arr中的第i/32个int
  • 好理解: int numIndex = i / 32;
  • 位运算: int numIndex = i >> 5;
  • 该位置对应arr[numIndex]中的第i%32个bit
  • 好理解: int bitIndex = i % 32;
  • 位运算: int bitIndex = i & 0x1F;

然后我们的目标位就在第numIndex个int的第bitIndex位上

  • 该位置的状态就可以用位运算来提取了
  • int state = (arr[numIndex] >> bitIndex) & 1;

    前面的右移是把该位右侧的数全部挤出去, 保留该位, 然后和1做与运算, 就只保留个位, 也就是目标i位的状态

我们还能修改这个位置的状态:

  • 若要将该位置状态设置为1
  • arr[numIndex] = arr[numIndex] | (1 << bitIndex);

    (1 << bitIndex)就是第i为1, 其余位全为0, 再和arr[numIndex]做或运算, 就可以把i位的状态设置为1

  • 若要将该位置状态设置为0
  • arr[numIndex] = arr[numIndex] & ~(1 << bitIndex);

    这里~(1 << bitIndex)就是第i为0, 其余位全为1, 再和arr[numIndex]做与运算, 就相当于其他位不发生改变, 只把i位的状态设置为0

位运算

基本运算符

| 名称 | 运算符 | 描述 | 示例 |
| :—: | :—-: | :—————-: | :——————————————————————————: |
| & | 与 | 全真为真, 否则为假 | 1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0 |
| \| | 或 | 全假为假, 否则为真 | 1 \| 1 = 1
1 \| 0 = 1
0 \| 1 = 1
0 \| 0 = 0 |
| ^ | 异或 | 相同为假, 不同为真 | 1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0 |
| ~ | 取反 | 取负减一 | ~1 = -2
~0 = -1
~4 = -5
~-4 = 3 |
| << | 左移 | 左移相当于乘以2 | 1 << 1 = 2
1 << 2 = 4
1 << 3 = 8
1 << 4 = 16 |
| >> | 右移 | 右移相当于除以2 | 8 >> 2 = 2
1 >> 1 = 0
0 >> 1 = 0
-1 >> 1 = -1
-2 >> 3 = -1 |

这里右移需要留意, 对于一个正数, 右移会把最低位挤出去(因此自然就向下取整了), 且不会改变正负性
如果右移的位数大于该数的位数, 则结果为0
而对于一个负数, 如果右移的位数大于该数的位数, 则结果为-1
数位移动只针对整数int, 如果直接对浮点数float进行移位运算, 会出现编译错误

优先级规则

| 运算符 | 优先级 |
| :—————————————————————————-: | :—-: |
| () | 0 |
| ~ | 1 |
| 单目 + 和 - | 1 |
| 单目 ++ 和 -- | 1 |
| * 和 / 和 % | 2 |
| + 和 - | 3 |
| << 和 >> | 4 |
| & | 5 |
| ^ | 6 |
| \| | 7 |
| && | 8 |
| \|\| | 9 |
| ?: | 10 |
| = 和 += 和 -=
*= 和 /= 和 %=
<<= 和 >>=
&= | 11 |
| , | 12 |

技巧

取整数的某一二进制位

int getBit(int x, int i) {
    return (x >> i) & 1;
}

判断奇偶

bool isOdd(int x) {
    return x & 1;
}

交换两个整数

void swap(int& a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

判断两个整数是否异号

bool isOpposite(int x, int y) {
    return (x ^ y) < 0;
}

取最低位的1

int lowBit(int x) {
    return x & -x;
}

取最低位的0

int lowZeroBit(int x) {
    return ~x & (x + 1);
}

取最高位的1

int highBit(int x) {
    int res = 0;
    while (x) {
        x >>= 1;
        res++;
    }
    return res;
}

获取位数

int getBitNum(int x) {
    int res = 0;
    while (x) {
        x >>= 1;
        res++;
    }
    return res;
}

统一初始化

使用{}能为任何数据类型统一的初始化
好处是效率高, 且易懂

int a{}, b{};

效果上等同于int a=0, b=0;

数组去重

法一: 转到set中, 再转回来

vector<int> aaa={1,4,2,8,5,7,9,9,6,1,4};
set<int> s(aaa.begin(), aaa.end());
aaa.assign(s.begin(), s.end());

法二: 用unique()函数

vector<int> aaa={1,4,2,8,5,7,9,9,6,1,4};
sort(aaa.begin(), aaa.end());
aaa.erase(unique(aaa.begin(), aaa.end()), aaa.end());

50’000次测试做下来两者耗时分别为:

Test1 Runtime = 0.44900 s
Test2 Runtime = 0.13900 s

因此, 虽然法一很好想也很好写, 但请使用法二
不仅效率高, 而且内存占用少

自定义强力工具包

快速幂

ll inverse(ll a, ll mod) { 
    ll ans = 1;
    while (a != 1) {
        ans = ans * (mod - mod / a) % mod;
        a = mod % a;
    }
    return ans;
}
ll fast(ll a, ll b, ll mod) {
    a %= mod;
    if (b < 0)a = inverse(a, mod), b = -b;
    ll ans = 1;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans % mod;
}

fastIO

#include<bits/stdc++.h>
using namespace std; 

#define int long long
const int maxn=1e5+10;
int a[maxn];

namespace fastIO {
#define BUF_SIZE 100000
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if (p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if (pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
    inline void read(int &x) {
        char ch;
        while (blank(ch = nc()));
        if (IOerror) return;
        for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
    }

    inline void Out(int a) {
        if (a < 0) {
            putchar('-');
            a = -a;
        }
        if (a >= 10) {
            Out(a / 10);
        }
        putchar(a % 10 + '0');
    }
#undef BUF_SIZE
};
using namespace fastIO;


void solve(){
    int n;
    read(n);
    int m;
    int ans=0;
    while(n--)
    {
        read(m);
        ans^=m;
    }
    Out(ans);
}

signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0), cout.tie(0);

    int T = 1;
    while (T --){
        solve();
    }

    return 0;
}

// cout<<fixed<<setprecision(3)

快速乘法逆元

解方程: $ax \equiv 1(mod\ m)$

ll MOD(ll a, ll m)
{
    a %= m;
    if (a < 0)
        a += m;
    return a;
}

ll inverse(ll a, ll m)
{
    a = MOD(a, m);
    if (a <= 1)
        return a;
    return MOD((1 - inverse(m, a) * m) / a, m);
}

竞赛御用模板

#pragma clang diagnostic push
#pragma ide diagnostic ignored "cppcoreguidelines-narrowing-conversions"
#pragma ide diagnostic ignored "hicpp-signed-bitwise"
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
 if (a >= b) return false;
 a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
 if (a <= b) return false;
 a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t)) 
#define REP(i, e) for (int i = 0; i < (e); ++i) 
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
 if (withSize) cout << v.size() << endl;
 REP(i, v.size()) cout << v[i] << " "; 
 cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

int __FAST_IO__ = []() {
 std::ios::sync_with_stdio(0);
 std::cin.tie(0);
 std::cout.tie(0);
 return 0;
}();

// Mint & Combinatorics

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { Modular result(*this); *this += 1; return result; }
  Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
    uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
    asm(
      "divl %4; \n\t"
      : "=a" (d), "=d" (m)
      : "d" (xh), "a" (xl), "r" (mod())
    );
    value = m;
#else
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
    long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  friend const Type& abs(const Modular& x) { return x.value; }

  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}

// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

struct MOD {
    static int value;
};
int MOD::value = 998244353;
using Mint = Modular<MOD>;
typedef vector<Mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;

namespace fastIO {
#define BUF_SIZE 100000
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if (p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if (pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
    inline void read(int &x) {
        char ch;
        while (blank(ch = nc()));
        if (IOerror) return;
        for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
    }

    inline void Out(int a) {
        if (a < 0) {
            putchar('-');
            a = -a;
        }
        if (a >= 10) {
            Out(a / 10);
        }
        putchar(a % 10 + '0');
    }
#undef BUF_SIZE
};
using namespace fastIO;


void solve(){
}

signed main() {

    int T = 1;
    // read(T);
    while (T --){
        solve();
    }

    return 0;
}

暴力枚举所有01选择情况

让i从0到1<<n枚举所有情况, 然后用i的二进制表示来判断每一位是否被选中
对于j是否选中, 只需考察i >> j & 1是否为1

Avatar photo
我是 zhyDaDa

前端/UI/交互/独立游戏/JPOP/电吉他/游戏配乐/网球/纸牌魔术

Related Posts

发表回复