51nod pit filling record (1) (1742,1810,1753,1291,1296)

Chong Wang Lv6
  2017-10-02 21:28:32 2017-10-02 21:28:32 Created   2026-10-09 08:56:49 2026-10-09 08:56:49 Updated  

I have been doing 51nod for a long time, because in the early days I always liked to read the solutions and missed a lot of good questions. Now that I think about it, I want to give myself a few slaps. The important thing is never whether you can solve the problem, but how to think about it. Many of the questions here are good, and I want to record them here.

51nod 1742 Happy Little Q

This is a great topic. . . No way. . . Maybe it’s because there are too few questions like this. I can’t do the derivation of expressions + inclusion and rejection. . .

Before I lose my memory. . To summarize.

The question requires the total number of interesting divisors. The definition of an interesting number is a perfect square number greater than 1.

At this time, consider the Möbius function, so the question requires:
$$
S(n) = \sum_{i=1}^{n}\sum_{d|i}(1-|u(d)|)
$$
What I want is
$$
S(b)-S(a-1)
$$
then there are
$$
S(n) = \sum_{i=1}^{n}\sum_{d|i}(1-|u(d)|) = \sum_{x=1}^{n}\sum_{d=1}^{\frac{x}{d}}(1-|u(d)|) = \sum_{x=1}^{n}F(\frac{n}{x})
$$

$$
F(n)=\sum_{i=1}^{n}(1-|u(i)|)
$$

At this time, you can find that $F(x)$ represents the number of square factors that do not exceed $n$. At this time, I found that it can be solved by tolerance and rejection. . .
$$
F(n)=n-\sum_{i=1}^{\sqrt{n}}u(i)*(\frac{n}{i^2})
$$
The meaning of this formula is that there are n in total, minus all the numbers without square factors. Why can’t Rong Shui think of it later? He’s so stupid. . .

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
int vis[maxn];
int pri[maxn];
int u[maxn];
void init()
{
	int i, j, k;
	u[1] = 1;
	int cnt = 0;
	for (i = 2; i <= 1e5; i++)
	{
		if (!vis[i])
		{
			cnt++;
			pri[cnt] = i;
			u[i] = -1;
		}
		for (j = 1; j <= cnt && 1LL*pri[j] * i <= 1e5; j++)
		{
			vis[i*pri[j]] = 1;
			if (i%pri[j] == 0)
			{
				u[i*pri[j]] = 0;
				break;
			}
			else
			{
				u[i*pri[j]] = -u[i];
			}
		}
	}
}

ll F(ll n)
{
	if(n==0)return 0;
	ll ans = n;
	for(int i=1;i*i<=n;i++)
	{
		ans-=u[i]*(n/(i*i));
	}
	return ans;
}

ll S(ll n)
{
	ll ans=0;
	ll cnt=1;
	for(int i=1;i<=n&&cnt;i+=cnt)
	{
		int ri = n/i;
		cnt = n/ri - n/(ri+1);
		ans += cnt*F(ri);
	}
	return ans;
}

void solve()
{
	ll a,b;
	cin>>a>>b;
	cout<<S(b)-S(a-1)<<endl;
}

51nod 1810 continuous interval

According to the meaning of the question, “continuous interval” means that the difference between the maximum value and the minimum value of this interval is equal to the number.

Consider partition. . . . . . . . . .

Just consider one endpoint to the left of the center and one endpoint to the right of the center. If it can be done in O(n), you can consider divide and conquer. . . .

Specifically, the left endpoint is i and the right endpoint is j, and then the sources of Max and Min are discussed.

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
ll ans;
int n;
int val[maxn];
int cnt[maxn * 3];
int maxx[maxn], minn[maxn];

int read() {
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    int x=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

void cal(int le, int ri)
{
	int mid = (le + ri) / 2;
	//le,mid
	maxx[mid] = minn[mid] = val[mid];
	for (int i = mid - 1; i >= le; i--)
	{
		maxx[i] = max(maxx[i + 1], val[i]);
		minn[i] = min(minn[i + 1], val[i]);
	}

	maxx[mid + 1] = minn[mid + 1] = val[mid + 1];
	for (int i = mid + 2; i <= ri; i++)
	{
		maxx[i] = max(maxx[i - 1], val[i]);
		minn[i] = min(minn[i - 1], val[i]);
	}

	//for (int i = le; i <= mid; i++)
	for (int i = mid; i >= le; i--)
	{
		int j = maxx[i] - minn[i] + i;
		if (j > mid&&j <= ri&&maxx[i] > maxx[j] && minn[i] < minn[j])
		{
			ans++;
		}
	}
	for (int j = mid + 1; j <= ri; j++)
	{
		int i = -(maxx[j] - minn[j] - j);
		if (i >= le&&i <= mid&&maxx[j]>maxx[i] && minn[j]<minn[i])ans++;
	}

	int t_le = mid + 1, t_ri = mid;
	for (int i = mid; i >= le; i--)
	{
		while (t_ri<ri&&maxx[t_ri + 1]<maxx[i])
		{
			t_ri++;
			cnt[minn[t_ri] + t_ri + maxn]++;
		}
		while (t_le <= t_ri&&minn[t_le]>minn[i])
		{
			cnt[minn[t_le] + t_le + maxn]--;
			t_le++;
		}
		ans += cnt[maxx[i] + i + maxn];
	}
	while (t_le <= t_ri)
	{
		cnt[minn[t_le] + t_le + maxn]--;
		t_le++;
	}


	t_le = mid + 1, t_ri = mid;

	for (int j = mid + 1; j <= ri; j++)
	{
		while (t_le>le&&maxx[t_le - 1]<maxx[j])
		{
			t_le--;
			cnt[minn[t_le] - t_le + maxn]++;
		}
		while (t_le <= t_ri&&minn[t_ri]>minn[j])
		{
			cnt[minn[t_ri] - t_ri + maxn]--;
			t_ri--;
		}
		ans += cnt[maxx[j] - j + maxn];
	}
	while (t_le <= t_ri)
	{
		cnt[minn[t_ri] - t_ri + maxn]--;
		t_ri--;
	}

	if (le == ri)
	{
		return;
	}
	cal(le, mid);
	cal(mid + 1, ri);
}

void solve()
{
	sa(n);
	repp(i, 1, n)val[i]=read();

	ans = 0;
	cal(1, n);
	printf("%lld\n", ans + n);
}

51nod 1753 similar substring

Construct 26 01 strings, and then merge and merge each time, string hash, if there is a difference, the difference must be $p_i^k$, record it.

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
ll n;
char val[maxn];
ll fac[maxn][2];
bool Hash1[mod+2];
bool Hash2[mod+2];
int sum[maxn][27][2];
int fa[30];
ll v[27][3][2];

int getfa(int x)
{
	if(x==fa[x])return x;
	else 
	{
		return fa[x]=getfa(fa[x]);
	}
}

void uni(int x,int y)
{
	x=getfa(x);
	y=getfa(y);
	if(x==y)return;
	fa[x]=y;
	v[y][1][0]+=v[x][1][0];
	v[y][1][1]+=v[x][1][1];

	v[y][1][0]=(v[y][1][0]%mod+mod)%mod;
	v[y][1][1]=(v[y][1][1]%mod+mod)%mod;

	v[y][2][0]+=v[x][2][0];
	v[y][2][1]+=v[x][2][1];

	v[y][2][0]=(v[y][2][0]%mod+mod)%mod;
	v[y][2][1]=(v[y][2][1]%mod+mod)%mod;
}

void cal()
{
	int t,le1,le2,ri1,ri2;
	sa(t),sa(le1),sa(ri1),sa(le2),sa(ri2);
	if(ri1-le1!=ri2-le2)
	{
		puts("NO");
		return;
	}
	repp(k,'a'-'a','z'-'a')
	{
		fa[k]=k;
		v[k][1][0] = sum[ri1][k][0]-sum[le1-1][k][0];
		v[k][1][0] = (v[k][1][0]%mod+mod)%mod;

		v[k][1][1] = sum[ri2][k][0]-sum[le2-1][k][0];
		v[k][1][1] = (v[k][1][1]%mod+mod)%mod;

		if(le1<le2)
		{
			v[k][1][0] *= fac[le2-le1][0];
			v[k][1][0] = (v[k][1][0]%mod+mod)%mod;
		}
		else
		{
			v[k][1][1] *= fac[le1-le2][0];
			v[k][1][1] = (v[k][1][1]%mod+mod)%mod;
		}

		v[k][2][0] = sum[ri1][k][1]-sum[le1-1][k][1];
		v[k][2][0] = (v[k][2][0]%mod+mod)%mod;

		v[k][2][1] = sum[ri2][k][1]-sum[le2-1][k][1];
		v[k][2][1] = (v[k][2][1]%mod+mod)%mod;

		if(le1<le2)
		{
			v[k][2][0]*=fac[le2-le1][1];
			v[k][2][0] = (v[k][2][0]%mod+mod)%mod;
		}
		else
		{
			v[k][2][1]*=fac[le1-le2][1];
			v[k][2][1] = (v[k][2][1]%mod+mod)%mod;
		}
	}
	char h[5];
	repp(i,1,t)
	{
		scanf("%s",h+1);
		int k1 = h[1]-'a';
		int k2 = h[2]-'a';
		uni(k1,k2);
	}
	int cnt=0;
	repp(k,'a'-'a','z'-'a')
	{
		if(k!=fa[k])continue;
		if(v[k][1][0]!=v[k][1][1])
		{
			cnt++;
			if(cnt>2)
			{
				puts("NO");
				return;
			}
			ll h1 = v[k][1][0]-v[k][1][1];
			h1=(h1%mod+mod)%mod;
			ll h2 = v[k][2][0]-v[k][2][1];
			h2=(h2%mod+mod)%mod;
			if(!((Hash1[h1]&&Hash2[h2])||(Hash1[mod-h1]&&Hash2[mod-h2])))
			{
				puts("NO");
				return;
			}
		}
	}
	puts("YES");
}

void solve()
{
	scanf("%s",val+1);
	n = strlen(val+1);
	fac[0][0]=fac[0][1]=1;
	repp(i,1,n)
	{
		fac[i][0]=fac[i-1][0]*29%mod;Hash1[fac[i][0]]=1;
		fac[i][1]=fac[i-1][1]*13%mod;Hash2[fac[i][1]]=1;
	}
	repp(k,'a','z')
	{
		repp(i,1,n)
		{
			sum[i][k-'a'][0]=sum[i-1][k-'a'][0]+ (val[i]==k)*fac[i][0]%mod;
			sum[i][k-'a'][0]=(sum[i][k-'a'][0]%mod+mod)%mod;

			sum[i][k-'a'][1]=sum[i-1][k-'a'][1]+ (val[i]==k)*fac[i][1]%mod;
			sum[i][k-'a'][1]=(sum[i][k-'a'][1]%mod+mod)%mod;
		}
	}
	int t;
	sa(t);
	while(t--)
	{
		cal();
	}
}

51nod 1291 Farmer

Monotone stack, add layer by layer, then +1, -1. . .

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
int m,n;
int val[maxn][maxn];
char v[maxn];
int top,sta[maxn],hei[maxn];
int ans[maxn][maxn];

void solve()
{
	sa(m),sa(n);
	repp(i,1,n)
	{
		scanf("%s",v+1);
		repp(j,1,m)
		{
			hei[j] = (v[j]=='1'?hei[j]+1:0);
		}
		top=0;
		sta[++top] = 0;
		repp(k,1,m+1)
		{
			while(hei[k]<hei[sta[top]])
			{
				ans[max(hei[k],hei[sta[top-1]])+1][k-sta[top-1]-1]++;
				ans[hei[sta[top]]+1][k-sta[top-1]-1]--;
				top--;
			}
			while(top&&hei[sta[top]]==hei[k])top--;
			sta[++top]=k;
		}
	}
	repp(i,1,n)
	{
		repp(j,1,m)
		{
			ans[i][j]+=ans[i-1][j];
		}
	}
	repp(i,1,n)
	{
		for(int k=m-1;k>=1;k--)
		{
			ans[i][k]+=ans[i][k+1];
		}
		for(int k=m-1;k>=1;k--)
		{
			ans[i][k]+=ans[i][k+1];
		}
	}
	repp(i,1,n)
	{
		repp(k,1,m)
		{
			if(k>1)printf(" ");
			printf("%d", ans[i][k]);
		}
		printf("\n");
	}
}

51nod1296 Restricted permutation

Consider how a permutation is generated. When i is added at the last position, the previous number greater than i is automatically +1.

dp[i][j] represents i numbers, and j is the legal number of permutations of the last number. The transfer is obviously a prefix sum transfer.

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
int n,k1,k2;
int vis[5005];
int dp[5005][5005];
// 1 xiaoyu
int sum[5005];

void solve()
{
	sa(n),sa(k1),sa(k2);
	repp(i,1,k1)
	{
		int x;
		sa(x);
		vis[x+1]=1;
		vis[x+2]=2;
	}
	repp(i,1,k2)
	{
		int x;
		sa(x);
		if(vis[x+1]==1)
		{
		    puts("0");
		    return;
		}
		vis[x+1]=2;
		vis[x+2]=1;
	}
	dp[1][1] = sum[1] = 1;
	repp(i,2,n)
	{
		repp(j,1,i)
		{
			if(vis[i]==1)
			{
				dp[i][j] = sum[i-1]-sum[j-1];
				dp[i][j] = (dp[i][j]%mod+mod)%mod;
			}
			else if(vis[i]==2)
			{
				dp[i][j] = sum[j-1];
			}
			else
			{
				dp[i][j] = sum[i-1];
			}
		}
		memset(sum,0,sizeof(sum));
		repp(j,1,i)
		{
			sum[j]=sum[j-1]+dp[i][j];
			sum[j]=(sum[j]%mod+mod)%mod;
		}
	}
	int ans=0;
	repp(i,1,n)
	{
		ans = ans + dp[n][i];
		while(ans>=mod)ans-=mod;
	}
	printf("%d\n", ans);
}
On this page
51nod pit filling record (1) (1742,1810,1753,1291,1296)
  1. 51nod 1742 Happy Little Q
  2. 51nod 1810 continuous interval
  3. 51nod 1753 similar substring
  4. 51nod 1291 Farmer
  5. 51nod1296 Restricted permutation