Enigmatic Partition

大意：

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

• 是整数，对于 ，。

• 对于任意 ， 。

• 。
  令f(n)为n的神秘分区的数量。给定l和r，请计算。
  输入描述：
  自己看原题。
  输出描述：
  对于每个测试用例，以“ Case #x：y”形式输出一行，其中x是测试用例编号，y是答案。

思路：

• 数n的拆分，需要满足最大和最小差2，相邻两个数差不能超过1

-f(n)表示拆分的个数，给定l,r求区间和

• 拆分肯定由三种连续的数构成，比如l,l+1,l+2

• 可以通过枚举l去初始化f(i);

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll cnt[maxn*5];
int main(){
    freopen("azw.txt","r",stdin);
    memset(cnt,0,sizeof(cnt));
    for (int i=3;i<=maxn;i++)
        for (int j=1;i*j<=maxn;j++){
            cnt[i*j+3]++;
            cnt[i*j+i+1]--;
            cnt[i*j+i+2]--;
            cnt[i*(2+j)]++;
        }
    for (int i=3;i<=maxn;i++)
        cnt[i]+=cnt[i-1];
    for (int i=3;i<=maxn;i++)
        cnt[i]+=cnt[i-2];
    for (int i=3;i<=maxn;i++)
        cnt[i]+=cnt[i-1];
    int T;
    scanf("%d",&T);
    for (int t=1;t<=T;t++){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("Case #%d: %lld\n",t,cnt[r]-cnt[l-1]);
    }
    return 0;
}