CF1301C-Ayoub's function 组合数学 思维

这道题觉得很巧妙。

让含1的子串尽可能多，就是全为0的子串尽可能少。（注意是全为0，不是有0，开始这里想当然然后就卡住了=.=）。

总的子串数就是(1,1)(1,2)...(1,n)(2,2)..(2,n)..(n,n)，显然是(n+1) * n/2。

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

所以每个空隙放b=(n-m)/(m+1)。因为不能整除，所有有(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 <cstdio>
using namespace std;
typedef long long ll;
int n,m,T;
int main()
{
    for (scanf("%d",&T);T;T--)
    {
        scanf("%d%d",&n,&m);
        ll tot = (ll)n * (n + 1) / 2;
        ll a = (n - m) / (m + 1);
        ll b = (n - m) % (m + 1); 
        printf("%I64d
",tot - a * (a + 1) / 2 * (m +  1) - (a + 1) * b);
    }
    return 0;
}