|
Daimayuan Online Judge
思路：思维
我们从问题的反面考虑，就是要求所有的子串减去只含
0
0
0的子串，那问题转化成如何让只含
0
0
0的子串尽可能的少，结论是将
1
1
1尽可能的均匀的分布在这个字符串中
显然我们有
m
m
m个
1
1
1就会分割出
m
+
1
m+1
m+1个只含
0
0
0的区间，那我们只要用总的子串个数减去这些只含
0
0
0的区间的子串即可
一个长度为
l
l
l的字符串的子串个数为：
l
?
(
l
+
1
)
/
2
l*(l+1)/2
l?(l+1)/2
现在我们来证明一下这个结论，为了方便我们只考虑整除的情况，即这些
1
1
1划分的
0
0
0区间长度相同
我们定义字符串长度
n
n
n，
1
1
1的个数
m
m
m，那么只含
0
0
0的区间个数为
m
+
1
m+1
m+1，这些区间的长度为
k
=
n
?
m
m
+
1
k=\frac{n-m}{m+1}
k=m+1n?m?，那么只含
0
0
0的子串个数
c
n
t
=
(
m
+
1
)
?
1
2
?
k
?
(
k
+
1
)
cnt=(m+1)*\frac{1}{2}*k*(k+1)
cnt=(m+1)?21??k?(k+1)，现在我们将其中一个
1
1
1向一侧移动一个位置，那么会导致两侧的两个
0
0
0长度分别
?
1
-1
?1，
+
1
+1
+1，那么子串个数变为
c
n
t
’
=
(
m
?
1
)
?
1
2
?
k
?
(
k
+
1
)
+
1
2
?
(
k
+
1
)
?
(
k
+
2
)
+
1
2
?
(
k
?
1
)
?
k
cnt’=(m-1)*\frac{1}{2}*k*(k+1)+\frac{1}{2}*(k+1)*(k+2)+\frac{1}{2}*(k-1)*k
cnt’=(m?1)?21??k?(k+1)+21??(k+1)?(k+2)+21??(k?1)?k，做差比较：
c
n
t
?
c
n
t
′
=
1
2
(
2
?
k
?
(
k
+
1
)
?
(
k
+
1
)
?
(
k
+
2
)
?
k
?
(
k
?
1
)
)
=
?
1
<
0
cnt-cnt'=\frac{1}{2}\Big(2*k*(k+1)-(k+1)*(k+2)-k*(k-1)\Big)=-1<0
cnt?cnt′=21?(2?k?(k+1)?(k+1)?(k+2)?k?(k?1))=?1<0，因此
c
n
t
<
c
n
t
′
cnt<cnt'
cnt<cnt′得证
Code：
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n';
typedef long long ll;
typedef pair<ll,ll> PII;
const int N=1e6+10;
ll n,m,t;
int main(){
IOS;
cin>>t;
while(t--){
cin>>n>>m;
ll ans=n*(n+1)/2,x=(n-m)/(m+1),y=(n-m)%(m+1);
if((n-m)%(m+1)==0) ans-=(m+1)*x*(x+1)/2;
else ans-=((m+1-y)*x*(x+1)/2+y*(x+1)*(x+2)/2);
cout<<ans<<endl;
}
return 0;
}
|