CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:namespace:牛客多校第六场 [2020/07/29 20:36]
great_designer [I]
+++ 2020-2021:teams:namespace:牛客多校第六场 [2020/08/01 10:22] (当前版本)
great_designer [I]
@@ 行 165: / 行 165: @@
 以下是补题。
+本题用到了斐波那契数和卢卡斯数的结论。[[斐波那契和卢卡斯]]
 <hidden>
-<code C>
+<code C++>
+#include<stdio.h>
+#include<algorithm>
+#include<set>
+using namespace std;
+set<pair<int,int> > s;
+long long L[44],ans;
+void Sub(set<pair<int,int> >::iterator p)
+{
+    set<pair<int,int> >::iterator pl=p,pr=p;
+    int l=(*p).second,r=(*p).first,last,plast;
+    if(p==s.begin())
+	{
+        ans-=l>>1;
+        if(l<=3)
+		{
+			ans-=r-l>>1;
+			plast=r;
+		}
+        else
+		{
+			ans-=r-l;
+			plast=r-1;
+		}
+        last=1;
+    }
+    else
+	{
+        --pl;
+        last;
+        if((*pl).second<=3)
+		{
+			last=(*pl).first;
+		}
+        else
+		{
+			last=(*pl).first-1;
+		}
+        ans-=(l-last+1)/2;
+        ans-=r-l;
+        plast=r-1;
+    }
+    ++pr;
+    if(pr==s.end())
+	{
+        return;
+    }
+    ans+=((*pr).second-last+1)>>1;
+    ans-=((*pr).second-plast+1)>>1;
+    return;
+}
+void Add(set<pair<int,int> >::iterator p)
+{
+    set<pair<int,int> >::iterator pl=p,pr=p;
+    int l=(*p).second,r=(*p).first,last,plast;
+    if(p==s.begin())
+	{
+        ans+=l>>1;
+        if(l<=3)
+		{
+			ans+=r-l>>1;
+			plast=r;
+		}
+        else
+		{
+			ans+=r-l;
+			plast=r-1;
+		}
+        last=1;
+    }
+    else
+	{
+        --pl;
+        last;
+        if((*pl).second<=3)
+		{
+			last=(*pl).first;
+		}
+        else
+		{
+			last=(*pl).first-1;
+		}
+        ans+=(l-last+1)/2;
+        ans+=r-l;
+        plast=r-1;
+    }
+    ++pr;
+    if(pr==s.end())
+	{
+        return;
+    }
+    ans-=((*pr).second-last+1)>>1;
+    ans+=((*pr).second-plast+1)>>1;
+    return;
+}
+void add(int x)
+{
+    if(!x)
+	{
+		return;
+	}
+    if(x==1)
+	{
+		x=2;
+	}
+    set<pair<int,int> >::iterator p=s.lower_bound(make_pair(x-1,-1));
+    if(p==s.end()||(*p).second>x+1)
+	{
+        int l=(1ll<<31)-1,r;
+        if(p!=s.end())
+		{
+			l=(*p).second;
+			r=(*p).first;
+		}
+        if(l==x+2)
+		{
+            Sub(p);
+            s.erase(p);
+        }
+        else
+		{
+			r=x;
+		}
+        p=s.lower_bound(make_pair(x-2,-1));
+        if(p!=s.end()&&(*p).first==x-2)
+		{
+            l=(*p).second;
+            Sub(p);
+            s.erase(p);
+        }
+        else
+		{
+			l=x;
+		}
+        s.insert(make_pair(r,l));
+		Add(s.lower_bound(make_pair(r,l)));
+        return;
+    }
+    if((*p).first==x-1)
+	{
+        int l=(*p).second;
+        Sub(p);
+        s.erase(p);
+        if(l<x-1)
+		{
+            s.insert(make_pair(x-3,l));
+			Add(s.lower_bound(make_pair(x-3,l)));
+        }
+        add(x+1);
+        return;
+    }
+    if(((*p).first-x)&1)
+	{
+        int l=(*p).second,r=(*p).first;
+        Sub(p);
+        s.erase(p);
+        if(l<x)
+		{
+            s.insert(make_pair(x-1,l));
+			Add(s.lower_bound(make_pair(x-1,l)));
+        }
+        l=r+1,r=r+1;
+        p=s.lower_bound(make_pair(r+2,-1));
+        if(p!=s.end()&&(*p).second==r+2)
+		{
+            r=(*p).first;
+            Sub(p);
+            s.erase(p);
+        }
+        s.insert(make_pair(r,l));
+		Add(s.lower_bound(make_pair(r,l)));
+        return;
+    }
+    else
+	{
+        int l=(*p).second,r=(*p).first;
+        Sub(p);
+        s.erase(p);
+        if(l<x)
+		{
+            s.insert(make_pair(x-1,l+1));
+			Add(s.lower_bound(make_pair(x-1,l+1)));
+        }
+        int nl=r+1;
+        r=r+1;
+        p=s.lower_bound(make_pair(r+2,-1));
+        if(p!=s.end()&&(*p).second==r+2)
+		{
+            r=(*p).first;
+            Sub(p);
+            s.erase(p);
+        }
+        p=s.lower_bound(make_pair(nl-2,-1));
+        if(p!=s.end()&&(*p).first==nl-2)
+		{
+            nl=(*p).second;
+            Sub(p);
+            s.erase(p);
+        }
+        s.insert(make_pair(r,nl));
+		Add(s.lower_bound(make_pair(r,nl)));
+        add(l-2);
+        return;
+    }
+}
+void del(int x)
+{
+    if(!x)
+	{
+		return;
+	}
+    if(x==1)
+	{
+		x=2;
+	}
+    set<pair<int,int> >::iterator p=s.lower_bound(make_pair(x,-1));
+    if((*p).second>x)
+	{
+        int r=(*p).first,l=(*p).second;
+        Sub(p);
+        s.erase(p);
+        if(l<r)
+		{
+			s.insert(make_pair(r,l+2));
+			Add(s.lower_bound(make_pair(r,l+2)));
+		}
+        if((x-l)&1)
+		{
+            if(l-2>=x+1)
+			{
+                p=s.lower_bound(make_pair(x-1,-1));
+                if(p==s.end()||(*p).first!=x-1)
+				{
+					s.insert(make_pair(l-2,x+1));
+					Add(s.lower_bound(make_pair(l-2,x+1)));
+				}
+                else
+				{
+                    int nl=(*p).second;
+                    Sub(p);
+                    s.erase(p);
+                    s.insert(make_pair(l-2,nl));
+					Add(s.lower_bound(make_pair(l-2,nl)));
+                }
+            }
+            add(l-2);
+        }
+        else
+		{
+            p=s.lower_bound(make_pair(x-1,-1));
+            if(p==s.end()||(*p).first!=x-1)
+			{
+				s.insert(make_pair(l-1,x+1));
+				Add(s.lower_bound(make_pair(l-1,x+1)));
+			}
+            else
+			{
+                int nl=(*p).second;
+                Sub(p);
+                s.erase(p);
+                s.insert(make_pair(l-1,nl));
+				Add(s.lower_bound(make_pair(l-1,nl)));
+            }
+        }
+        return;
+    }
+    if(((*p).second-x)&1)
+	{
+        int r=(*p).first,l=(*p).second;
+        Sub(p);
+        s.erase(p);
+        s.insert(make_pair(x-1,l));
+		Add(s.lower_bound(make_pair(x-1,l)));
+        if(x+3<=r)
+		{
+			s.insert(make_pair(r,x+3));
+			Add(s.lower_bound(make_pair(r,x+3)));
+		}
+        add(x-1);
+        return;
+    }
+    else
+	{
+        int r=(*p).first,l=(*p).second;
+        Sub(p);
+        s.erase(p);
+        if(r>x)
+		{
+			s.insert(make_pair(r,x+2));
+			Add(s.lower_bound(make_pair(r,x+2)));
+		}
+        if(l<x)
+		{
+			s.insert(make_pair(x-2,l));
+			Add(s.lower_bound(make_pair(x-2,l)));
+		}
+        return;
+    }
+}
+int X[1000],Y[1000];
+void solve()
+{
+    int a,b;
+    scanf("%d%d",&a,&b);
+    ++b;
+    int op=0,OP=0;
+    if(a<0)
+	{
+		OP=1;
+		a=-a;
+	}
+    int cnt=0,cnt2=0;
+    while(a)
+	{
+        int k=upper_bound(L+1,L+44,a)-L-1;
+        a-=L[k];
+        op=OP;
+        if(op&1)
+		{
+			Y[cnt2++]=b+k;
+		}
+        else
+		{
+			X[cnt++]=b+k;
+		}
+        if(b-k>=0)
+		{
+            op^=k&1;
+            if(op&1)
+			{
+				Y[cnt2++]=b-k;
+			}
+            else
+			{
+				X[cnt++]=b-k;
+			}
+        }
+        else
+		{
+            op^=k&1;
+            if((b-k+1)&1)
+			{
+				op^=1;
+			}
+            if(op&1)
+			{
+				Y[cnt2++]=k-b;
+			}
+            else
+			{
+				X[cnt++]=k-b;
+			}
+        }
+    }
+    int i;
+    for(i=0;i<cnt;++i)
+	{
+		add(X[i]);
+	}
+    for(i=0;i<cnt2;++i)
+	{
+		del(Y[i]);
+	}
+    printf("%lld\n",ans);
+}
+int main()
+{
+    L[0]=2;
+    L[1]=1;
+    int i;
+    for(i=2;i<44;++i)
+	{
+		L[i]=L[i-1]+L[i-2];
+	}
+    int T;
+    scanf("%d",&T);
+    while(T--)
+	{
+        ans=0;
+        s.clear();
+        int n;
+        scanf("%d",&n);
+        while(n--)
+		{
+			solve();
+		}
+    }
+}
 </code>
@@ 行 333: / 行 734: @@
 =====I=====
-[[Stling数]]
+题目、解答与代码见[[Stirling数]]。
-<hidden>
-<code C>
-#include<stdio.h>
-int MOD;
-long long powmod(long long x,int k)
-{
-	long long ans=1;
-	while(k)
-	{
-		if(k&1)
-		{
-			ans=ans*x%MOD;
-		}
-		x=x*x%MOD;
-		k>>=1;
-	}
-	return ans;
-}
-int getfact(int x,int *p)
-{
-	int t=x,sz=0;
-	int i;
-	for(i=2;i*i<=t;i++)
-	{
-		if(x%i==0)
-		{
-			p[++sz]=i;
-			while(x%i==0)
-			{
-				x/=i;
-			}
-		}
-	}
-	if(x>1)
-	{
-		p[++sz]=x;
-	}
-	return sz;
-}
-long long facd[1000005],facv[1000005];
-long long G,mi[1000005],inv[1000005];
-void pre()
-{
-	facd[0]=1;
-	int i;
-	for(i=1;i<MOD;i++)
-	{
-		facd[i]=facd[i-1]*i%MOD;
-	}
-	facv[MOD-1]=facd[MOD-1];
-	for(i=MOD-2;i>=0;i--)
-	{
-		facv[i]=facv[i+1]*(i+1)%MOD;
-	}
-	int prime[10];
-	int sz=getfact(MOD-1,prime);
-	for(G=1;;G++)
-	{
-		bool ok=1;
-		for(i=1;i<=sz;i++)
-		{
-			if(powmod(G,(MOD-1)/prime[i])==1)
-			{
-				ok=0;
-				break;
-			}
-		}
-		if(ok)
-		{
-			break;
-		}
-	}
-	mi[0]=1;
-	for(i=1;i<MOD-1;i++)
-	{
-		mi[i]=mi[i-1]*G%MOD;
-	}
-	inv[1]=1;
-	for(i=2;i<MOD;i++)
-	{
-		inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
-	}
-}
-long long C(long long n,long long m)
-{
-	return (n<m)?0:facd[n]*facv[m]%MOD*facv[n-m]%MOD;
-}
-long long calc(long long n,long long m)
-{
-	if(!m)
-	{
-		return 1;
-	}
-	if(n<m)
-	{
-		return 0;
-	}
-	return C(n%MOD,m%MOD)*calc(n/MOD,m/MOD)%MOD;
-}
-long long query(long long n,long long m)
-{
-	m=(n<m)?n:m;
-	long long s=0;
-	int i;
-	for(i=0;i<MOD-1;i++)
-	{
-		int x=mi[i];
-		if(x+n>MOD)
-		{
-			continue;
-		}
-		if(!i)
-		{
-			s=(s+(m+1)*facd[x+n-1]%MOD*facv[x-1])%MOD;
-		}
-		else
-		{
-			s=(s+(mi[(MOD-1-i*(m+1)%(MOD-1))%(MOD-1)]-1LL)*inv[mi[MOD-1-i]-1LL]%MOD*facd[x+n-1]%MOD*facv[x-1])%MOD;
-		}
-	}
-	s=(MOD-s)%MOD;
-	if(n==MOD-1)
-	{
-		s=(s-1LL+MOD)%MOD;
-	}
-	return s;
-}
-long long solve(long long n,long long m)
-{
-	long long u1=n/MOD,v1=n%MOD;
-	if(m<u1)
-	{
-		return 0;
-	}
-	m-=u1;
-	long long u2=m/(MOD-1),v2=m%(MOD-1);
-	long long s=0;
-	if(u2)
-	{
-		s=(s+(((u2-1)&1)?MOD-1:1)*calc(u1-1,u2-1)%MOD*query(v1,MOD-2))%MOD;
-	}
-	s=(s+((u2&1)?MOD-1:1)*calc(u1,u2)%MOD*query(v1,v2))%MOD;
-	if(v1==MOD-1&&u2)
-	{
-		s=(s+(((u2-1)&1)?MOD-1:1)*calc(u1-1,u2-1))%MOD;
-	}
-	return s*((u1&1)?MOD-1:1)%MOD;
-}
-int main()
-{
-	long long n,l,r;
-	scanf("%lld%lld%lld%d",&n,&l,&r,&MOD);
-	pre();
-	long long s1=solve(n,r);
-	long long s2=solve(n,l-1);
-	printf("%lld\n",(s1-s2+MOD)%MOD);
-	return 0;
-}
-</code>
-</hidden>
 =====K=====

CVBB ACM Team

用户工具

站点工具

页面工具