C. Ayoub's function

题目大意：

长度为 n ，含有 m 个 1 的 01串含有 1 的子串个数 最多是多少

思路：

既然是要求含有 1 的子串个数要最多，也就是要让含有 0 的子串个数要最少

长度为 n 的字符串它的子串总个数是 n * (n + 1)  / 2

我们考虑全为0的子串个数

我们有m个1，相当于有m+1的空隙可以用来放0。那么显然我们把这n-m个0匀着放到这m+1个空隙，可以使得每个0的部分尽可能短，进而使得全为0的子串尽可能少。 

所以每个空隙放 a = (n-m)/(m+1) 因为不能整除，所有有 b = (n-m) % (m+1)个空隙实际上还要再多一个0。

如果每个空隙都放a = (n-m)/(m+1)个，那么显然每个空隙产生  a * (a + 1) / 2，一共产生(m + 1) * a * (a + 1) / 2 个全为0的子串。但是有b个空隙实际上还有一个0，所以还要在多产生b * (a+1)个串。

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <math.h>
#include <cstdio>
#include <iomanip>
#include <time.h>
#include <bitset>
#include <cmath>

#define LL long long
#define INF 0x3f3f3f3f
#define ls nod<<1
#define rs (nod<<1)+1

const double eps = 1e-10;
const int maxn = 1e5 + 10;
const LL mod = 1e9 + 7;

int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;}
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n,m;
        cin >> n >> m;
        LL tot = 1ll*n*(n+1)/2;
        LL a = (n-m)/(m+1);
        LL b = (n-m)%(m+1);
        cout << tot-a*(a+1)/2*(m+1)-(a+1)*b << endl;
    }
    return 0;
}