锐客网

  1. 首页 > it技术 > >

杜教筛|191106CSP（NOI（）模拟及NOI（CSP？）模拟题解）

莫比乌斯反演杜教筛bm

【杜教筛|191106CSP（NOI（）模拟及NOI（CSP？）模拟题解）】CSP模拟：
T1：求 ∑ i = 1 n ∑ j = 1 m C g c d ( i , j ) B % m o d \sum_{i=1}^n\sum_{j=1}^mC_{gcd(i,j)}^B \%mod ∑i=1n?∑j=1m?Cgcd(i,j)B?%mod
n , m ≤ 1 e 10 , B ≤ m o d = 9990017 n,m\le1e10,B\le mod=9990017 n,m≤1e10,B≤mod=9990017
莫比乌斯反演，设 f ( i ) f(i) f(i)表示 C i B C_i^B CiB?
∑ i = 1 n ∑ j = 1 m f ( g c d ( i , j ) ) \sum_{i=1}^n\sum_{j=1}^mf(gcd(i,j)) i=1∑n?j=1∑m?f(gcd(i,j))
∑ d = 1 m i n ( n , m ) d ∑ i = 1 ? n d ? ∑ j = 1 ? m d ? f ( d ) [ g c d ( i , j ) = = 1 ] \sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \lfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \lfloor}f(d)[gcd(i,j)==1] d=1∑min(n,m)?di=1∑?dn???j=1∑?dm???f(d)[gcd(i,j)==1]
∑ d = 1 m i n ( n , m ) d ∑ x = 1 f ( d ) μ ( x ) ? n x d ? ? m x d ? \sum_{d=1}^{min(n,m)}d\sum_{x=1}f(d)\mu(x)\lfloor \frac{n}{xd} \rfloor \lfloor \frac{m}{xd} \rfloor d=1∑min(n,m)?dx=1∑?f(d)μ(x)?xdn???xdm??
∑ T = 1 m i n ( n , m ) ( ∑ d ∣ T f ( T d ) μ ( d ) ) ? n T ? ? m T ? \sum_{T=1}^{min(n,m)}(\sum_{d|T}f(\frac{T}{d})\mu(d))\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor T=1∑min(n,m)?(d∣T∑?f(dT?)μ(d))?Tn???Tm??
杜教筛中间的，然后整除分块
中间的卷上一个 I I I就完事，还要用到一个定理： ∑ i = 1 n ( B i ) \sum_{i=1}^n(_B^i) ∑i=1n?(Bi?)= ( B + 1 i + 1 ) (_{B+1}^{i+1}) (B+1i+1?)
Code：

#include #define ll long long #define mod 9990017 using namespace std; inline ll read(){ ll res=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48); ch=getchar(); } return res*f; } inline int add(int x,int y){x+=y; if(x>=mod) x-=mod; return x; } inline int dec(int x,int y){x-=y; if(x<0) x+=mod; return x; } inline int mul(int x,int y){return 1ll*x*y%mod; } inline void inc(int &x,int y){x+=y; if(x>=mod) x-=mod; } inline void Dec(int &x,int y){x-=y; if(x<0) x+=mod; } inline void Mul(int &x,int y){x=1ll*x*y%mod; } inline int ksm(int a,int b){int res=1; for(; b; b>>=1,a=mul(a,a)) if(b&1) res=mul(res,a); return res; } const int N=3e6+5; int pri[N],pt[N],tot=0,mu[N],f[N]; int fac[mod],ifac[mod]; int B; inline int C(int n,int m){if(n<0 || m<0 || nmp; int S(ll x){ if(x<=3000000) return f[x]; if(mp.count(x)) return mp[x]; int res=lucas(x+1,B+1); for(ll i=2,j; i<=x; i=j+1){ j=x/(x/i); Dec(res,mul(dec(add(j,1),i),S(x/i))); } return mp[x]=res; } int main(){ ll n=read(),m=read(); B=read(); init(3000000); int ans=0,now=0,last=0; for(ll i=1,j; i<=min(n,m); i=j+1){ j=min(n/(n/i),m/(m/i)); now=S(j); inc(ans,mul(n/i%mod,mul(m/i%mod,dec(now,last)))); last=now; } cout<

T2：一个 2 ? n 2*n 2?n的点集，一共有 n n n条弦，每条弦由两个点组成，每个点仅属于一条弦，每次询问给出两个点 r 1 , r 2 r1,r2 r1,r2，询问有多少个 l l l满足区间 [ l , r 1 ] [l,r1] [l,r1]和 [ l , r 2 ] [l,r2] [l,r2]都不会跨过任意一条弦的恰好一个点， n ≤ 2 e 6 n\le2e6 n≤2e6
单调栈预处理每个点往左的极小合法区间左端点，然后每个点向其极小合法区间左端点连边，形成一棵树，则不难发现答案就是两点间 l c a lca lca的深度
Code：
#include using namespace std; inline int read(){ int res=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48); ch=getchar(); } return res*f; } const int N=2e6+5; int vis[N],head[N],nxt[N],tot=0; inline void add(int x,int y){vis[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } int siz[N],hson[N],fa[N],dep[N],rt[N]; int R; void dfs1(int v){ siz[v]=1; rt[v]=R; for(int i=head[v]; i; i=nxt[i]){ int y=vis[i]; if(y==fa[v]) continue; fa[y]=v; dep[y]=dep[v]+1; dfs1(y); siz[v]+=siz[y]; if(siz[y]>siz[hson[v]]) hson[v]=y; } } int top[N]; void dfs2(int v,int T){ top[v]=T; for(int i=head[v]; i; i=nxt[i]) if(top[vis[i]]==-1) dfs2(vis[i],vis[i]==hson[v]?T:vis[i]); } inline int lca(int x,int y){ while(top[x]!=top[y]) dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]]; int lc=dep[x]=l[i]){ l[i]=min(l[i],l[sta[tp]]); r[i]=max(r[i],r[sta[tp]]); --tp; } sta[++tp]=i; } memset(rt,-1,sizeof(rt)); memset(top,-1,sizeof(top)); for(int i=1; i<=n; i++) if(i==r[i]) add(l[i]-1,i); for(int i=0; i<=n; i++) if(rt[i]==-1){R=i; dfs1(i); dfs2(i,i); } while(q--){ int x=read(),y=read(); if(x<1 || y<1 || x>n || y>n || rt[x]!=rt[y]) puts("0"); else cout<

T3：多次给出一个 4 ? n 4*n 4?n的矩阵，求用俄罗斯方块将其恰好填满的方案数 n ≤ 1 e 9 , T ≤ 1000 n\le1e9,T\le1000 n≤1e9,T≤1000
显然是状态压缩后用矩阵快速幂优化，然而其有常系数线性递推式，所以可以BM打表+多项式取模
Code：咕咕咕
NOI模拟：
T1：CSPT3
T2：一个sb计数，懒得写了
T3：一个sb推式子，懒得写了

    推荐阅读


    上一篇：线段树|191024省选测试题解

    下一篇：线段树|[线段树]区间and or xor