```cpp
#include
#define ll long long
using namespace std;
const int N=3e5+10;
const int mod=1e9+7;
ll a[N],p[N];
ll sum[N];
int n;
int main()
{
//freopen("H:\\c++1\\in.txt","r",stdin);
//freopen("H:\\c++1\\out.txt","w",stdout);
p[0]=1;
for(int i=1;i>i)&1)sum[j]=sum[j-1]+1;
else sum[j]=sum[j-1];
}
ll cnt=0;
for(int j=1;j>i)&1){
cnt+=(n-j-(sum[n]-sum[j]));
}else{
cnt+=(sum[n]-sum[j]);
}
}
cnt%=mod;
ans=(ans+(1ll*cnt*p[i]%mod))%mod;
}
printf("%lld\n",ans);
return 0;
}
```

```c++
#include
#define inf 0x3f3f3f3f
using namespace std;
const int N=100;
const int M=6401;
const int Y=6400;
bitset dp[N][N];
int n,m;
int a[N][N],b[N][N];
int main()
{
//freopen("H:\\c++1\\in.txt","r",stdin);
//freopen("H:\\c++1\\out.txt","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i>cha));
dp[i][j]|=((dp[i][j-1]>cha));
}
int ans=inf;
for(int i=0;i

F - Sum Difference （数学）

题目链接

题目大意：

给一个 \(n\) 个数的等差数列，首项为 \(x\) ，公差为 \(d\) ，现在在数列中选择 \(k\) 个数，设计 \(S\) 为 \(k\) 个数的和， \(T\) 为剩下 \(n-k\) 的数的和。为共有多少个 \(S-T\) 的值。

大致思路：

假设所有数字之和为 \(sum\) ，那么 \(S-T=S-(sum-S)=2*S-sum\) ，那么其实就是求 \(S\) 的不同值的个数。假设 \(S=k*x+m*d\) ，其中 \(k\) 就是选择的数的个数， \(m\) 是一个值， \(m\) 应该在 \([0+1+...+k-1,n-k+n-(k+1)+...+n-1]\) 的范围之内。那么对于一个 \(k\) 值， \(S\) 的值就是在一个 \([L,R]\) 中，然后每一个数字间隔 \(d\) ，而且这些值 \(S\%d\) 都是相等的。那么我们就对所有的 \(S\) 用 \(d\) 将它们分成一个剩余系，不同剩余类中的元素是不会相等的，决定其位于哪个剩余类是 \(k*x\%d\) 的值。为了得到每一个剩余类的元素个数，我们将S/d，那么就会得到许多的区间，按照k*x%d分类，对于每一个类将区间排序，合并，计算即可。

感觉比较抽象，具体来说就是，一个模d余0剩余类中的数字为 \(，，，，x，x+d，x+2*d，x+3*d，...\) ，那么一个模d余1剩余类的数字为 \(，，，x+1，x+1+d，x+1+2*d，....\) ，那么我们就对每一个剩余类来求解。

代码：