//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
活动打卡代码
AcWing 2437. Splay
#include<bits/stdc++.h>
using namespace std;
struct node;
node*root;
struct node{
node*son[2];
node*fa;
int data;
int cnt;
bool flex;
node(node*f,int x):fa(f),data(x){son[0]=son[1]=nullptr;cnt=1;flex=false;}
int get(void){return fa->son[1]==this;}
void pushup(void){
cnt=1;
if(son[0])cnt+=son[0]->cnt;
if(son[1])cnt+=son[1]->cnt;
}
void pushdown(void){
if(flex){
swap(son[0],son[1]);
if(son[0]){son[0]->flex^=1;}
if(son[1]){son[1]->flex^=1;}
flex=0;
}
}
void rotate(int x){
son[x]->fa=fa;
if(son[x]->son[x^1])son[x]->son[x^1]->fa=this;
if(fa)fa->son[get()]=son[x];
fa=son[x];
son[x]=fa->son[x^1];
fa->son[x^1]=this;
pushup();
fa->pushup();
}
void splay(node*ed){
while(fa!=ed){
if(fa->fa==ed)fa->rotate(get());
else if(fa->get()==get()){
fa->fa->rotate(fa->get());
fa->rotate(get());
}
else{
fa->rotate(get());
fa->rotate(get());
}
}
if(!ed)root=this;
}
void find(int rnk,node*ed=nullptr){
pushdown();
if(son[0]&&rnk<=son[0]->cnt)son[0]->find(rnk,ed);
else {
if(son[0])rnk-=son[0]->cnt;
if(rnk==1){
splay(ed);
return;
}
son[1]->find(rnk-1,ed);
}
}
void print(void){
pushdown();
if(son[0]){
son[0]->print();
putchar('\40');
}
cout<<data;
if(son[1]){
putchar('\40');
son[1]->print();
}
}
};
void insert(int x,int*dat,int num){
node*u;
u=new node(nullptr,dat[0]);
for(int i=1;i<num;++i){
u->fa=new node(nullptr,dat[i]);
u->fa->son[0]=u;
u=u->fa;
u->pushup();
}
root->find(x+1);
root->find(x+2,root);
root->son[1]->son[0]=u;
u->fa=root->son[1];
root->son[1]->pushup();
root->pushup();
}
void reserve(int l,int r){
root->find(l);
root->find(r+2,root);
root->son[1]->son[0]->flex^=1;
}
int n,m;
void print(void){
root->find(1);
root->find(n+2,root);
root->son[1]->son[0]->print();
}
template<typename T>void read(T&ans){
ans=0;char us=getchar();bool f=false;
while(us!=EOF&&(us<48||us>57)){f|=(us==45);us=getchar();}
while(us>47&&us<58){ans=(ans<<1)+(ans<<3)+(us^48);us=getchar();}
ans=f?-ans:ans;
}
template<typename T,typename ...O>void read(T&x,O&...oth){read(x);read(oth...);}
template<typename T=signed int>T read(void){T x;read(x);return x;}
int inp[100005];
int main(){
root=new node(nullptr,0x7fffffff);
root->son[1]=new node(root,0x7fffffff);
read(n,m);
for(int i=1;i<=n;++i){
inp[i]=i;
}
insert(0,inp+1,n);
int l,r;
while(m--){
read(l,r);
reserve(l,r);
}
print();
}
活动打卡代码
AcWing 3020. 建筑师
#include<bits/stdc++.h>
using namespace std;
long long C[205][105],stirling1[205][50004];
constexpr int MOD = 1000000007;
int main(){
int t,n,a,b;
scanf("%d",&t);
C[0][0]=1;
for(int i=1;i<=200;++i){
C[i][0]=1;
for(int j=1;j<=100;++j){
C[i][j]=C[i-1][j-1]+C[i-1][j];
C[i][j]%=MOD;
}
}
stirling1[0][0]=1;
for(int i=1;i<=200;++i){
for(int j=1;j<=50000;++j){
stirling1[i][j]=stirling1[i-1][j-1]+(j-1)*stirling1[i][j-1];
stirling1[i][j]%=MOD;
}
}
while(t--){
scanf("%d%d%d",&n,&a,&b);
cout<<C[a+b-2][a-1]*stirling1[a+b-2][n-1]%MOD<<'\12';
}
return 0;
}
活动打卡代码
AcWing 3165. 第一类斯特林数
#include<bits/stdc++.h>
using namespace std;
constexpr int MOD = 1000000007;
long long stirling1[1005][1005];
int main(){
int n,k;
scanf("%d%d",&n,&k);
stirling1[0][0]=1;
for(int i=1;i<=k;++i){
for(int j=1;j<=n;++j){
stirling1[i][j]=stirling1[i-1][j-1]+(j-1)*stirling1[i][j-1];
stirling1[i][j]%=MOD;
}
}
cout<<stirling1[k][n];
return 0;
}
活动打卡代码
AcWing 3122. 多项式乘法
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 300005;
constexpr double PI = acos(-1);
int n, m;
struct Complex
{
double x, y;
friend Complex operator+(const Complex &a, const Complex &b) { return {a.x + b.x, a.y + b.y}; }
friend Complex operator-(const Complex &a, const Complex &b) { return {a.x - b.x, a.y - b.y}; }
friend Complex operator*(const Complex &a, const Complex &b) { return {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; }
} a[MAXN], b[MAXN]; //复数类
int rev[MAXN], bit, tot; //迭代翻转及长度
void fft(Complex *a, int inv)
{
for (int i = 0; i < tot; ++i)
if (i < rev[i])
swap(a[i], a[rev[i]]); //迭代翻转
for (int mid = 1; mid < tot; mid <<= 1) //
{ //倍增？反正是从下往上处理
auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)}); // n次单位根
for (int i = 0; i < tot; i += mid * 2) //
{ //遍历每个小段
auto wk = Complex({1, 0}); //需要的单位根的幂值
for (int j = 0; j < mid; ++j, wk = wk * w1) //
{ //处理在所有位置的横坐标（单位根）
auto x = a[i + j], y = wk * a[i + j + mid]; // f(x)=A(x^2)-xB(x^2)
a[i + j] = x + y; //前面一项
a[i + j + mid] = x - y; //后面一项
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; ++i)
scanf("%lf", &a[i].x);
for (int i = 0; i <= m; ++i)
scanf("%lf", &b[i].x); //输入
while ((1 << bit) < n + m + 1) //
++bit; //确定二进制位数
tot = 1 << bit; //长度
for (int i = 0; i < tot; ++i) //
{ //处理迭代翻转的目标位置
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1)); //
} //
fft(a, 1); //系数转点值
fft(b, 1); //同上
for (int i = 0; i < tot; ++i) //
a[i] = a[i] * b[i]; //确定答案的点值
fft(a, -1); //点值转系数
for (int i = 0; i <= n + m; ++i)
cout << (int)(a[i].x / tot + 0.5) << ' ';
return 0;
}
