2020牛客暑期多校训练营（第八场）E Enigmatic Partition

题目大意

数字n的分区是所有数字之和等于n的集合。 如果分区满足以下条件，则称为神秘分区：

• 是整数，对于，。

• 对于任意，

• 
  设为的神秘分区的个数。现对于给出的每对，求出。

  解题思路

  感谢大佬的思路：https://blog.csdn.net/tianyizhicheng/article/details/107773762

• 显而易见，这道题的做法必须为预处理每个数合法的构造数。
  由于这个构造的首尾差最大为2，所以我们可以把每个构造的都可以分成3段。现在我们设第一段数值为，那么第二段是，第三段是，设每段长度为。
  所以我们得到这样的式子：
  合并+替换：
  最后可以得到：

• 引用一段对于差分的解释：
  

  https://blog.csdn.net/zhangchizc/article/details/107784622

• 我们以时的情况为例，简单地打个表：
  

• 所以，我们只用在对应位置上加减，还原为原序列即为f(n)。
  就像上面说的，我们预处理出f(n)的前缀和，查询时无脑输出即可。

  AC代码

  #include<bits/stdc++.h>
  using namespace std;
  const int N=3e5+10,M=1e5;
  long long a[N],b[N],c[N];
  int main()
  {
    int T,l,r,x,i,j;
    for(i=3;i<=M;i++)
        for(j=1;i*j<=M;j++)
            x=i*j,a[x+3]++,a[x+i*2-1]--,b[x+i+1]++,b[x+i*2-1]--;
    //a[x+i-1+i-2+2]--,b[x+i-1+1+1]++,b[x+i-1+i-2+2]--;
    for(i=3;i<=M;i++) a[i]+=a[i-2],b[i]+=b[i-1];
    for(i=3;i<=M;i++) a[i]+=a[i-1]-b[i],c[i]=c[i-1]+a[i];
    scanf("%d",&T);
    for(i=1;i<=T;i++)
    {
        scanf("%d%d",&l,&r);
        printf("Case #%d: %lld\n",i,c[r]-c[l-1]);
    }
    return 0;
  }