多校省选模拟2
T1 守序划分问题
记划分后的集合为\(A_i\)，全集\(U=\{i|1<=i<=m\}\)
题目限制等价于，一种集合划分合法，当且仅当\(\forall S\subset U且S!=\varnothing,\min A_{i\in S}<\max A_{j \not\in S}\)
证明充分性就构造然后归纳一下
将所有集合按min升序，设已经处理完 \(A_{p_{i-1}}\)且合法
由于\(\min A_{j\in[i,m]}=\min A_i\)，根据条件可知，存在\(j\in[1,i-1]\)满足\(\max A_j>\min A_i\)
必要性是显然的
然后可以dp了，f[i][j][k]设前 i 个数划分到 j 个集合，有 k 个集合还未闭合
转移就分四种情况，是否闭合集合和是否新开集合
\[f[i][j][k]=f[i-1][j-1][k]+f[i-1][j-1][k-1]+(k+1)*f[i-1][j][k+1]+k*f[i-1][j][k] \]还要注意边界
T2 欧拉函数
然而并没有写正解
加法还是比较好写的，就扫一遍\(p_i<=\sqrt {\sum a_j}\)，复杂度是\(O(q\frac{\sqrt {nw}}{\log \sqrt {nw}})\)
对于乘法，每个数把质因数存进bitset里，每个线段树节点存一个bitset，然后就单点修改区间查询
bitset还有俩nb的函数，叫\(\_Find\_first，\_Find\_next\)，找第一个1和下一个1
T3 点整的上圆
Min_25筛还没学，，，
代码
T1
#include
using namespace std;
#define il inline
#define int long long
const int N=5e2+11;
const int mod=998244353;
int n,m;
int f[2][N][N];
il void md(int &x){if(x>=mod)x-=mod;return;}
il int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
signed main()
{
freopen("partition.in","r",stdin);
freopen("partition.out","w",stdout);
n=read(),m=read();
f[0][0][0]=1;
bool now,last;
for(int i=1;i<=n;++i)
{
now=i&1,last=now^1;
for(int j=1;j<=m;++j)
{
for(int k=0;k<=j;++k)
{
md(f[now][j][k]+=f[last][j-1][k]);
if(k) md(f[now][j][k]+=f[last][j-1][k-1]);
md(f[now][j][k]+=(k+1)*f[last][j][k+1]%mod);
md(f[now][j][k]+=k*f[last][j][k]%mod);
}
if(i!=n) f[now][j][0]=0;
}
memset(f[last],0,sizeof(f[last]));
}
cout< T2
#include
using namespace std;
#define il inline
#define int long long
const int B=4205;
const int N=4e4+11;
const int M=5e4+11;
const int mod=1e9+7;
struct tree{int l,r;bitset bit;}tre[4*M];
int n,q;
bool fp[N];
int p[N],num,inv[N];
int a[M],tre1[M],tre2[M];
vector vct[N];
bitset bit;
int fm(int x,int y){int ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
void insert1(int x,int val){for(;x<=n;x+=(x&-x))tre1[x]+=val;return;}
int query1(int x){int sum=0;for(;x;x-=(x&-x))sum+=tre1[x];return sum;}
void insert2(int x,int val){for(;x<=n;x+=(x&-x))tre2[x]=tre2[x]*val%mod;return;}
int query2(int x){int sum=1;for(;x;x-=(x&-x))sum=sum*tre2[x]%mod;return sum;}
il int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
void pre()
{
fp[0]=fp[1]=1;
inv[0]=inv[1]=1;
for(int i=0;i>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
tre[i].bit=tre[i<<1].bit|tre[i<<1|1].bit;
return;
}
void insert(int i,int x,int val)
{
if(tre[i].l==tre[i].r){tre[i].bit.reset();for(int x : vct[val]) tre[i].bit[x]=1;return;}
int mid=(tre[i].l+tre[i].r)>>1;
if(x<=mid) insert(i<<1,x,val);
else insert(i<<1|1,x,val);
tre[i].bit=tre[i<<1].bit|tre[i<<1|1].bit;
return;
}
bitset query(int i,int l,int r)
{
if(tre[i].l>=l&&tre[i].r<=r) return tre[i].bit;
bitset ans;ans.reset();
int mid=(tre[i].l+tre[i].r)>>1;
if(l<=mid) ans=query(i<<1,l,r);
if(r>mid) ans|=query(i<<1|1,l,r);
return ans;
}
int get_ans1(int l,int r)
{
int sum=query1(r)-query1(l-1);
int ans=sum%mod;
int sq=sqrt(sum);
for(int i=1;i<=num;++i)
{
if(p[i]>sq) break;
if(sum%p[i]==0)
{
ans=ans*inv[p[i]]%mod*(p[i]-1)%mod;
while(sum%p[i]==0)sum/=p[i];
}
}
if(sum>1) ans=ans*fm(sum,mod-2)%mod*(sum-1)%mod;
return ans;
}
int get_ans2(int l,int r)
{
int ans=query2(r)*fm(query2(l-1),mod-2)%mod;
bit.reset(),bit=query(1,l,r);
for(int i=bit._Find_first();i