test20190903

发表于

闲扯

今天打了 $3$ 道题的暴力，结果全部打挂了。。。

$T1$ 的想法和正解一毛一样，就是没打出来，而且还把题中的按位或看成按位异或了。。。

题面

题面

$T1$

Solution

对于这种关于位运算的题目，我们可以考虑将原数拆开，对每一位分别进行计算。

我们考虑一个子矩阵，如果在这个矩阵中该位有贡献，那么对于按位于就等价与该子矩阵中的数都为 $1$ ，对于按位与就等价于该子矩阵中至少有一个 $1$ 。

对于按位与，我们可看做所有的矩形减去全为 $0$ 的矩阵的贡献。

这样我们就将问题统一成了求全 $1$ 子矩阵和全 $0$ 子矩阵的个数。

我们可以用单调栈来求，做法和求最大子矩阵类似，就不写了才不会告诉你们是我懒得写呢

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il print(T x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
it mul(int a,int b,int mod){return 1ll*a*b%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 1e3+5,mod = 998244353;
int n,val[MAXN][MAXN],sum[MAXN][MAXN],ans_or,ans_ad,top,h[MAXN][MAXN],tot,mx;
pair<int,int> stk[MAXN];
it add(int a,int b){return ((a+b)%mod+mod)%mod;}
il solve(int k){
	ri bas=1<<k,ans=0;
	for(ri i=1;i<=n;++i)
		for(ri j=1;j<=n;++j)
			if(val[i][j]&bas) h[i][j]=h[i-1][j]+1;
			else h[i][j]=0;
	for(ri i=1;i<=n;++i){
		top=0;ri sum=0;
		for(ri j=1;j<=n;++j){
			ri w=0;
			while(top&&stk[top].first>=h[i][j]) w+=stk[top].second,ans=add(ans,mul(h[i][j],stk[top].second,mod)),sum=add(sum,-mul(stk[top].first,stk[top].second,mod)),--top;
			if(h[i][j]) stk[++top]=make_pair(h[i][j],w+1),ans=add(ans,sum+h[i][j]),sum=add(sum,mul(w+1,h[i][j],mod));
		}
	}
	ans_ad=add(ans_ad,mul(ans,bas,mod));
	ans=0;
	for(ri i=1;i<=n;++i)
		for(ri j=1;j<=n;++j)
			if(val[i][j]&bas) h[i][j]=0;
			else h[i][j]=h[i-1][j]+1;
	for(ri i=1;i<=n;++i){
		top=0;ri sum=0;
		for(ri j=1;j<=n;++j){
			ri w=0;
			while(top&&stk[top].first>=h[i][j]) w+=stk[top].second,ans=add(ans,mul(h[i][j],stk[top].second,mod)),sum=add(sum,-mul(stk[top].first,stk[top].second,mod)),--top;
			if(h[i][j]) stk[++top]=make_pair(h[i][j],w+1),ans=add(ans,sum+h[i][j]),sum=add(sum,mul(w+1,h[i][j],mod));
		}
	}
	ans_or=add(ans_or,mul(add(tot,-ans),bas,mod));
}
int main()
{
	freopen("mob.in","r",stdin);
	freopen("mob.out","w",stdout);
	read(n),tot=mul(1ll*n*(n+1)/2,1ll*n*(n+1)/2,mod);
	for(ri i=1;i<=n;++i)
		for(ri j=1;j<=n;++j)
			read(val[i][j]),mx=max(mx,val[i][j]);
	for(ri i=0;i<31;++i)
		if(mx>=(1<<i)) solve(i);
		else break;
	print(ans_ad),puts(""),print(ans_or);
	return 0;
}

$T2$

Solution

问题等价于求有多少种方案，使得删去一条边后，该图是一个二分图。

对于二分图，我们有一个定义是：没有奇环的图。

对于一个连通块，我们可以考虑先求出一颗原图的生成树。

对于每一条非树边，我们连接之后，一定会形成环。

如果是奇环，那么我们就将计数器加一。

对结果进行分类讨论。

  1. 如果 $cnt=0$ ，说明没有奇环，每一条边都可以。
  2. 如果 $cnt=1$ ，那么我们一定要删去该奇环上的边。但要保证它没有位于偶环上。
  3. 如果 $cnt>1$ ，那么我们一定要删去所有奇环的交集内的边，同样不能在偶环上。

为了问题便于解决，我们可以用树上差分。

所有位于奇环上的边，我们将其全部加 $1$ ；如果位于偶环上，那么我们将其全部减 $1$ 。

这样做最后的答案就是权值等于 $cnt$ 的边。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e5+10;
int head[MAXN],edges[MAXN<<1],nx[MAXN<<1],to[MAXN<<1];
int n,m,ecnt=-1;
int vis[MAXN],dfn[MAXN],tag[MAXN];
int tmp,cnt,s=0;
void addedge(int u,int v,int id)
{
	++ecnt;
	nx[ecnt]=head[u];
	to[ecnt]=v;
	edges[ecnt]=id;
	head[u]=ecnt;
}
void dfs(int u,int PreEdge)
{
	for(int i=head[u]; i!=-1; i=nx[i])
	{
		if(i==(PreEdge^1))
			continue;
		int v=to[i];
		if(dfn[v])
		{
			if(dfn[u]<dfn[v])
				continue;
			if((dfn[u]-dfn[v]+1)&1) // ²»ºÏ·¨±ß 
			{
				tag[u]++;
				tag[v]--;
				cnt++;
				tmp=edges[i];
			}
			else //ºÏ·¨±ß 
			{
				tag[u]--;
				tag[v]++;
			}
		}
		else
		{
			dfn[v]=dfn[u]+1;
			dfs(v,i);
			tag[u]+=tag[v];
		}
	}
}
int ans[MAXN],tot=0;
void calc(int u)
{
	vis[u]=1;
	for(int i=head[u]; i!=-1; i=nx[i])
	{
		int &v=to[i];
		if(vis[v])
			continue;
		if(tag[v]==cnt)
			ans[++tot]=edges[i];
		calc(v);
	}
}
int main()
{
	freopen("crusade.in","r",stdin);
	freopen("crusade.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		head[i]=-1;
	for(int i=1; i<=m; i++)
	{
		int u=read(),v=read();
		addedge(u,v,i);
		addedge(v,u,i);
	}
	for(int i=1; i<=n; i++)
		if(!dfn[i])
		{
			dfn[i]=1;
			dfs(i,-1);
		}	
	if(!cnt)
	{
		printf("%d\n",m);
		for(int i=1;i<=m;++i)
			s^=i;
		printf("%d\n",s);
		return 0;
	}
	for(int i=1; i<=n; i++)
		if(!vis[i])
			calc(i);
	if(cnt==1)
		ans[++tot]=tmp;
	printf("%d\n",tot);
	for(int i=1; i<=tot; i++)
		s^=ans[i];
	printf("%d\n",s);
	return 0;
}

$T3$

Solution

我们可以知道，欧拉函数值 $\varphi(x)$ 只和 $x$ 与 $x$ 包含的质因子有关。

通过打表可以发现，在 $300$ 以内的质数只有 $62$ 个，刚好可以用一个 $long\ long$ 的数来表示。

我们可以用线段树维护区间的乘积和区间含有的质数。

这样每次查询、修改就很简单了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il print(T x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	ri res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 4e5+5,mod = 998244353;
int n,m,opt,x,y,k,val[MAXN],inv[65],pri[65]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293};
ll sta[305]={0,0,1,2,1,4,3,8,1,2,5,16,3,32,9,6,1,64,3,128,5,10,17,256,3,4,33,2,9,512,7,1024,1,18,65,12,3,2048,129,34,5,4096,11,8192,17,6,257,16384,3,8,5,66,33,32768,3,20,9,130,513,65536,7,131072,1025,10,1,36,19,262144,65,258,13,524288,3,1048576,2049,6,129,24,35,2097152,5,2,4097,4194304,11,68,8193,514,17,8388608,7,40,257,1026,16385,132,3,16777216,9,18,5,33554432,67,67108864,33,14,32769,134217728,3,268435456,21,2050,9,536870912,131,260,513,34,65537,72,7,16,131073,4098,1025,4,11,1073741824,1,8194,37,2147483648,19,136,262145,6,65,4294967296,259,8589934592,13,16386,524289,48,3,516,1048577,10,2049,17179869184,7,34359738368,129,66,25,1028,35,68719476736,2097153,32770,5,264,3,137438953472,4097,22,4194305,274877906944,11,32,69,130,8193,549755813888,515,12,17,65538,8388609,1099511627776,7,2199023255552,41,131074,257,2052,1027,80,16385,10,133,4398046511104,3,8796093022208,16777217,38,9,17592186044416,19,35184372088832,5,262146,33554433,520,67,4100,67108865,258,33,144,15,70368744177664,32769,524290,134217729,8196,3,1032,268435457,1048578,21,96,2051,140737488355328,9,6,536870913,281474976710656,131,562949953421312,261,26,513,1125899906842624,35,16388,65537,2097154,73,2251799813685248,7,4503599627370496,17,2,131073,12,4099,160,1025,4194306,5,9007199254740992,11,272,1073741825,70,1,18014398509481984,8195,2056,37,514,2147483649,36028797018963968,19,32772,137,8388610,262145,72057594037927936,7,144115188075855872,65,42,4294967297,20,259,288230376151711744,8589934593,1026,13,576460752303423488,16387,1152921504606846976,524289,134,49,4104,3,64,517,16777218,1048577,2305843009213693952,11,65540,2049,18,17179869185,288,7};
struct Seg_Tree{
	int sum,tag;
	ll sta,_tag;
}T[MAXN<<2];
#define lc (cur<<1)
#define rc (cur<<1|1)
il pushup(int cur){T[cur].sum=(1ll*T[lc].sum*T[rc].sum)%mod,T[cur].sta=T[lc].sta|T[rc].sta;}
il pushdown(int cur,int l,int r){
	if(T[cur].tag==1) return ;
	T[lc].sta|=T[cur]._tag;
	T[rc].sta|=T[cur]._tag;
	T[lc]._tag|=T[cur]._tag;
	T[rc]._tag|=T[cur]._tag;
	T[lc].tag=(1ll*T[lc].tag*T[cur].tag)%mod;
	T[rc].tag=(1ll*T[rc].tag*T[cur].tag)%mod;
	T[lc].sum=(1ll*T[lc].sum*qpow(T[cur].tag,mid-l+1,mod))%mod;
	T[rc].sum=(1ll*T[rc].sum*qpow(T[cur].tag,r-mid,mod))%mod;
	T[cur].tag=1;
}
il build_tree(int cur,int l,int r){
	T[cur].tag=1;
	if(l==r){
		T[cur].sum=val[l],T[cur].sta=sta[val[l]];
		return ;
	}
	build_tree(lc,l,mid),build_tree(rc,mid+1,r);
	pushup(cur);
}
il updata(int cur,int l,int r,int L,int R,int k,ll sta){
	if(l>=L&&r<=R) T[cur].sta|=sta,T[cur].sum=(1ll*T[cur].sum*qpow(k,(r-l+1),mod))%mod,T[cur].tag=(1ll*T[cur].tag*k)%mod,T[cur]._tag|=sta;
	else{
		pushdown(cur,l,r);
		if(mid>=L) updata(lc,l,mid,L,R,k,sta);
		if(R>mid) updata(rc,mid+1,r,L,R,k,sta);
		pushup(cur);
	}
}
inl Seg_Tree query(int cur,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T[cur];
	pushdown(cur,l,r);Seg_Tree res,tmp;
	res.sum=1,res.sta=0;
	if(mid>=L) tmp=query(lc,l,mid,L,R),res.sta|=tmp.sta,res.sum=(1ll*res.sum*tmp.sum)%mod;
	if(R>mid) tmp=query(rc,mid+1,r,L,R),res.sta|=tmp.sta,res.sum=(1ll*res.sum*tmp.sum)%mod;
	return res;
}
int main()
{
	freopen("hanabi.in","r",stdin);
	freopen("hanabi.out","w",stdout);
	read(n),read(m);
	for(ri i=0;i<62;++i) inv[i]=qpow(pri[i],mod-2,mod),inv[i]=(1ll*inv[i]*(pri[i]-1))%mod;
	for(ri i=1;i<=n;++i) read(val[i]);
	build_tree(1,1,n);
	for(ri i=1;i<=m;++i){
		read(opt),read(x),read(y);
		if(opt==1){
			read(k);
			updata(1,1,n,x,y,k,sta[k]);
		}
		else{
			Seg_Tree tmp=query(1,1,n,x,y);
			tmp=query(1,1,n,x,y);
			ri res=tmp.sum;rl sta=tmp.sta;
			for(ri j=0;j<62;++j) if(sta&(1ll<<j)) res=(1ll*res*inv[j])%mod;
			print(res),puts("");
		}
	}
	return 0;
}

为了卡常改的面目全非了。。。

$ps:$ 有一种优化方式是，将这 $62$ 个数分为 $4$ 段，维护出每一段中的每种质数集合的贡献，查询时直接合并就行。

总结

做题要细心。题要看对，暴力一定不要打错，想到方法要大胆尝试，不要不敢打。。。