2018.10.14 牛客提高集训营5

A 同余方程(思路位运算)

　　首先容斥一下，(Ans=(r_1,r_2)-(r_1,l_2-1)-(l_1-1,r_2)+(l_1-1,l_2-1))。((x,y))表示(l_1=l_2=0, r_1=x, r_2=y)时的答案。
　　因为是异或，我们按位考虑。
　　对于((r_1,r_2))，考虑这种特殊情况：(r_1=2^n-1, r_2=2^m-1)（假设(nleq m)）。
　　从([0,2^n))中任取一个(x)，([0,2^m))中任取一个(y)，那么(x^{wedge}y)还在([0,2^n))内。
　　对于任意一个(zin[0,2^n))，它的前(n-m)位是由(x)确定的，后(m)位由(x,y)共同确定。那么对于(x)的后(m)位的(2^m)种取值，(y)都有唯一的值使得(x^{wedge}y=z)。所以我们算一下([0,2^n))中有多少个(P)的倍数，再乘上(2^m)就行了。
　　考虑更一般的情况。如果枚举(r)的某一位(1)选(0)，那么后面所有位可以随意确定。比如(r=(1011)_2)，可以将它拆成(0???,100?,1010)三个区间（区间左端点为(0)），这样就对应三个形如(a imes2^n+[0,2^n))的区间（(a)就是枚举的(1)之前的前缀）。当然(1011)本身不会计算到，让(r+1)就行了。
　　这样我们就把任意区间拆成了(O(log n))个前缀固定，后面随便放的区间。
　　考虑对于(r_1,r_2)，设拆出的区间分别是(a_1 imes2^n+[0,2^n))和(a_2 imes2^m+[0,2^m))，且(ngeq m)。那么从这两个区间中任取两个数异或，结果的后(n)位可以任意定，剩余高位由(a_1 imes2^n ^{wedge} a_2 imes2^m)确定。异或的结果是一个区间，区间中任意数同样有(2^m)种选择得到。算一下区间中有多少个数整除(P)就行了。（因为有个([0,2^n))的数，所以区间下界的后(n)位为全(0)，上界就全(1)，其余高位由(a_1 imes2^n ^{wedge} a_2 imes2^m)决定）。

#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define BIT 59
#define mod 998244353
typedef long long LL;

inline LL read()
{
	LL now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
//LL Calc(LL a,LL b,LL m)//两种写法 
//{
//	LL ans=0;
//	for(int i=0; i<=BIT; ++i)
//		if(a>>i&1)
//			for(int j=0; j<=BIT; ++j)
//				if(b>>j&1)
//				{
//					int mx=std::max(i,j),mn=std::min(i,j);
//					LL L=((a^1ll<<i)^(b^1ll<<j))&~((1ll<<mx)-1),R=L+(1ll<<mx)-1,tot=(R/m-L/m+(L%m==0))%mod;//0
//					(ans+=(1ll<<mn)%mod*tot)%=mod;
//				}
//	return ans;
//}
LL Calc(LL a,LL b,LL m)
{
	LL ans=0;
	for(LL i=a; i; i&=i-1)
		for(LL j=b; j; j&=j-1)
		{
			LL mx=std::max(i&-i,j&-j),mn=std::min(i&-i,j&-j);
			LL L=((i&i-1)^(j&j-1))&~(mx-1),R=L+mx-1,tot=(R/m-L/m+(L%m==0))%mod;
			(ans+=mn%mod*tot)%=mod;
		}
	return ans;
}

int main()
{
	LL l1=read(),r1=read(),l2=read(),r2=read(),m=read();
	printf("%lld
",(Calc(r1+1,r2+1,m)+mod-Calc(r1+1,l2,m)+mod-Calc(l1,r2+1,m)+Calc(l1,l2,m))%mod);
	return 0;
}

B 旅游(Kruskal 贪心)

题目链接

假设让每条边经过(a_i)次，那么我们要最小化(sum_{i=1}^m 2^i*a_i)。
怎么判断当前(a_i)的选择方案是否合法呢？也就是判是否存在欧拉回路。那么令(dgr_i)为(i)点度数，那么若满足(forall i,dgr_i\%2=0)，方案合法。
好了以上是废话。我们先求最小生成树。
因为树边权值都小于非树边，且(2^k>sum_{i=0}^{k-1}2^i)，所以如果要走一条权值大的非树边两次，完全可以多绕一圈树边代替，且同样只影响路径端点的两个点的度数奇偶性。
我们还可以发现，(1leq a_ileq2)。对生成树DFS一遍，根据点的度数确定一下(x)需要走到(fa[x])的边多少次就行了。
(1)节点没有到父节点的边，但因为所有点度数和为偶数，所有它的度数也一定是偶数。

//107ms	16476KB
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mod 998244353
typedef long long LL;
const int N=5e5+5;

int pw[N],Enum,H[N],to[N<<1],nxt[N<<1],len[N<<1],fa[N],dgr[N];
LL Ans;
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline void AE(int u,int v,int w)
{
	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
int Find(int x)
{
	return x==fa[x]?x:fa[x]=Find(fa[x]);
}
void DFS(int x,int fa)
{
	for(int i=H[x],v; i; i=nxt[i])
		if((v=to[i])!=fa)
		{
			DFS(v,x);
			if(dgr[v]) dgr[x]^=1,Ans+=pw[len[i]];//异或比++快好多啊（比较n大）
		}
}

int main()
{
	int n=read(),m=read();
	for(int i=1; i<=n; ++i) fa[i]=i;
	pw[0]=1;
	for(int i=1; i<=m; ++i) pw[i]=pw[i-1]<<1,pw[i]>=mod&&(pw[i]-=mod);
	Ans=0;
	for(int i=1,u,v,r1,r2; i<=m; ++i)
	{
		dgr[u=read()]^=1, dgr[v=read()]^=1, Ans+=pw[i];
		if((r1=Find(u))==(r2=Find(v))) continue;
		fa[r1]=r2, AE(u,v,i);
	}
	DFS(1,1);
	printf("%lld
",Ans%mod);

	return 0;
}

C 串串(思路组合)

题目链接

　　首先串(T)有(inom{c+d}{c})种可能。
　　先生成串(S)再判断(T)是(S)的子序列很麻烦。我们可以往(T)中加入(a-c)个(0)和(b-d)个(1)来得到(S)。那么所求即为有多少种加入(0/1)的方案由(T)得到(S)。
　　显然多余的(0/1)是哪都可以加的。但是直接这么算会算重。比如000加一个0，有(4)个位置可选，但实际方案数只有1种。
考虑比如0001要加入一个0，只要钦定0只能放在那个1前面，就不会算重了。再比如00011001，每个1前（且只在(1)前）可以放若干个0，方案都是不同的。
　　所以实际上(0)可以放的位置只有(d)个（即(1)的个数）（当然一个位置可以放多个(0)）。
　　另外(T)的末尾是可以任意放(0/1)的。那我们枚举(T)的末尾放多少个(0/1)，方案数可以用组合数算。同样其余的(0/1)只能放在前面确定的一些位置，方案数同样可以用组合数(O(1))计算（就是(n)个球放入(m)个盒子，允许盒子为空，即将(n)个球分成(m)组）。
　　设在前面放(x)个(0)，(y)个(1)，则方案数为：$$inom{x+d-1}{d-1} imesinom{y+c-1}{c-1} imesinom{a-c-x+b-d-y}{a-c-x}$$

　　因为有(c-1,d-1)，所以要特判(c,d)为(0)的情况。而且这样算只与(0/1)数量有关，最后可以直接乘(inom{c+d}{c})。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define mod 1000000007
typedef long long LL;
const int N=4005;

int fac[N],ifac[N];

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline int FP(int x,int k)
{
	int t=1;
	for(; k; k>>=1,x=1ll*x*x%mod)
		if(k&1) t=1ll*t*x%mod;
	return t;
}
#define C(n,m) (1ll*fac[n]*ifac[m]%mod*ifac[(n)-(m)]%mod)

int main()
{
	const int lim=4000;
	fac[0]=fac[1]=1;
	for(int i=2; i<=lim; ++i) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[lim]=FP(fac[lim],mod-2);
	for(int i=lim; i; --i) ifac[i-1]=1ll*ifac[i]*i%mod;

	int a=read(),b=read(),c=read(),d=read(); a-=c,b-=d;
	LL ans=0;
	if(!c)
		for(int x=0; x<=a; ++x)
			ans+=1ll*C(x+d-1,d-1)%mod*C(a-x+b,a-x)%mod;
	else if(!d)
		for(int y=0; y<=b; ++y)
			ans+=1ll*C(y+c-1,c-1)%mod*C(a+b-y,a)%mod;
	else
		for(int x=0; x<=a; ++x)
			for(int y=0; y<=b; ++y)
				ans+=1ll*C(x+d-1,d-1)*C(y+c-1,c-1)%mod*C(a-x+b-y,a-x)%mod;
	printf("%lld
",ans%mod*C(c+d,c)%mod);

	return 0;
}

10.14 牛客提高集训营5

2018.10.14 牛客提高集训营5

A 同余方程(思路 位运算)

B 旅游(Kruskal 贪心)

C 串串(思路 组合)

A 同余方程(思路位运算)

C 串串(思路组合)