Codeforces Round #619 (Div. 2)：C. Ayoub's function

╰半橙微兮° 2023-07-05 11:42 9阅读 0赞

**Discription**  
Ayoub thinks that he is a very smart person, so he created a function f(s), where s is a binary string (a string which contains only symbols “0” and “1”). The function f(s) is equal to the number of substrings in the string s that contains at least one symbol, that is equal to “1”.

More formally, f(s) is equal to the number of pairs of integers (l,r), such that 1≤l≤r≤|s| (where |s| is equal to the length of string s), such that at least one of the symbols sl,sl+1,…,sr is equal to “1”.

For example, if s=“01010” then f(s)=12, because there are 12 such pairs (l,r): (1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,4),(3,5),(4,4),(4,5).

Ayoub also thinks that he is smarter than Mahmoud so he gave him two integers n and m and asked him this problem. For all binary strings s of length n which contains exactly m symbols equal to “1”, find the maximum value of f(s).

Mahmoud couldn’t solve the problem so he asked you for help. Can you help him?

**Input**  
The input consists of multiple test cases. The first line contains a single integer t (1≤t≤105) — the number of test cases. The description of the test cases follows.

The only line for each test case contains two integers n, m (1≤n≤109, 0≤m≤n) — the length of the string and the number of symbols equal to “1” in it.

**Output**  
For every test case print one integer number — the maximum value of f(s) over all strings s of length n, which has exactly m symbols, equal to “1”.

**Example**  
**input**

5
    3 1
    3 2
    3 3
    4 0
    5 2

**output**

4
    5
    6
    0
    12

**Note**  
In the first test case, there exists only 3 strings of length 3, which has exactly 1 symbol, equal to “1”. These strings are: s1=“100”, s2=“010”, s3=“001”. The values of f for them are: f(s1)=3,f(s2)=4,f(s3)=3, so the maximum value is 4 and the answer is 4.

In the second test case, the string s with the maximum value is “101”.

In the third test case, the string s with the maximum value is “111”.

In the fourth test case, the only string s of length 4, which has exactly 0 symbols, equal to “1” is “0000” and the value of f for that string is 0, so the answer is 0.

In the fifth test case, the string s with the maximum value is “01010” and it is described as an example in the problem statement.

**题意**  
给定一个长度为n的只包含0和1字符串，其中有m个1，要求在字符串人取两个数l,r，l<=r，并且在\[l,r\]的范围内至少有一个1。  
问最多有几种取l和r的取法。

**思路**  
以内对字符串任意排列，我们很容易得知，所有的1分散开得到的一定最多。  
假设有7个，2个0。  
我们有两种排法：0101000或者0010100  
我们知道  
 C 3 2 > 2 ∗ C 2 2 C\_3^2>2\*C^2\_2 C32>2∗C22  
所以根据贪心规则，将所有的0平分去插1的空是最多的。  
用一点容斥的思想。  
 a n s = C n 2 − s i g m a ( 每 个 空 0 的 组 合 数 ) + n u m ( 1 ) ans=C\_n^2-sigma(每个空0的组合数)+num(1) ans=Cn2−sigma(每个空0的组合数)\+num(1)

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define sd(n) scanf("%d", &n)
    #define sdd(n, m) scanf("%d%d", &n, &m)
    #define sddd(n, m, k) scanf("%d%d%d", &n, &m, &k)
    #define sld(n) scanf("%lld", &n)
    #define sldd(n, m) scanf("%lld%lld", &n, &m)
    #define slddd(n, m, k) scanf("%lld%lld%lld", &n, &m, &k)
    #define sf(n) scanf("%lf", &n)
    #define sff(n, m) scanf("%lf%lf", &n, &m)
    #define sfff(n, m, k) scanf("%lf%lf%lf", &n, &m, &k)
    #define pd(n) printf("%d\n", (n))
    #define pdd(n, m) printf("%d %d\n", n, m)
    #define pld(n) printf("%lld\n", n)
    #define pldd(n, m) printf("%lld %lld\n", n, m)
    #define rep(i, a, n) for(int i=a; i<=n; i++)
    #define per(i, n, a) for(int i=n; i>=a; i--)
     
    int T;
    ll n,m,ans;
     
    int main()
    { 
        scanf("%d",&T);
        while(T--)
        { 
            sldd(n,m);
            if(m==0)
            { 
                cout<<0<<endl;
                continue;
            }
            ans=n*(n-1)/2;
            ll tmp=n-m;
            ll xx=tmp/(m+1);
            //cout<<xx<<endl;
            ll tt=tmp%(m+1);
            //cout<<tt<<endl;
            ll cnt=(m+1-tt)*(xx-1)*xx/2+tt*(xx+1)*xx/2;
            ans-=cnt;
            ans+=m;
            cout<<ans<<endl;
        }
        return 0;
    }