分糖果
链接：https://www.nowcoder.com/acm/contest/173/B
来源：牛客网
题目描述
(N) 个小朋友围成一圈，你有无穷个糖果，想把其中一些分给他们。
从某个小朋友开始，我们顺时针给他们标号为(1) ~ (N)。第 (i) 个小朋友可以得到至多 (a[i])，至少 (1) 个糖果。
问，有多少种分配方案使得每一对相邻的小朋友拿到的糖果数不同。答案对 (10^9 + 7) 取模。
输入描述:
第一行一个整数 (N)。
接下来一行 (N) 个整数，第 (i) 个数表示 (a[i])。
输出描述:
一行一个整数，表示答案。
说明:
对全部的测试数据，(n <= 10^6, a_i <= 10^9)
- (10) 分的数据，(n <= 4)
- (10) 分的数据，(n <= 100,a_i <= 20)
- (20) 分的数据，(n <= 100,a_i <= 100)
- (10) 分的数据，(n <= 10^5,a_i) 全部相等
- (30) 分的数据，(n <= 10^5,a_i) 为随机生成
- (20) 分的数据，(n <= 10^6).
UPDATA：10.16 发现自己的想法可能很不优美，可能回来更改。
当时讲得视频本蒟蒻死活听不懂，回来花了好几天的语文课总算是能够自己理解了，和视频里面讲得并不太一样，也许是我理解麻烦了说不定
40pts的普通区间DP就不说了，不过吐槽一下没有(N^2)的档，事实上不用容斥是可以做到(N^2)的，只需要一些断环的技巧
下面正题
- 大致分为三个步骤：
1 链上答案的统计
2 化链为环
3 单调栈优化
现在仅考虑为链的情况
先回归一下问题的本质，我们可以这样描述这个问题，我们要填满一个长度为(n)的数组，要求每两个相邻的位置填的数不能相等，每个位置(i)的可填集合为(1)-(a_i)的整数。（这看起来有变吗？？
行吧，根据正难则反，换成容斥的话，先不管条件，求总方案，然后按照填了几个相等的数作为容斥系数，直接统计？听起来好像非常有道理，然而一点也说不到重点
这里直接给出状态转移方程进行分析了（事实上文字描述说起来不清楚，还容易产生误导
(dp_i)表示前(i)个位置构成的合法的方案数
(dp_i=sum_{i=0}^{i-1} dp_j imes min_{k=j+1}^i a_k imes (-1)^{i-j-1})
(dp_0=1)
从(i-1)位置的转移开始理解
我们在(i)位置上对前面所有的情况填取(a_i)中可能
产生的不合法情况只有(i)与(i-1)位置相等的一些情况，我们需要减去它们
那我们不妨把这两个状态相等的情况通过(dp_{i-2})递推过来，但这样我们就多减去了后三个相等的情况，就是容斥了
于是，我们就得到了一个优秀的在链上的(O(N^2))算法了
怎么搞到环上？减去第一段和最后一段相等的情况。
为了方便，让第一段为最小的元素，这样可以用(a_1)统计方案了
这里我没有用到特别容斥的方案来理解（事实上感觉也是
首先，长度为2的链直接就是一个环了
长度为3的链减去长度为2的环就可以拼成环了
原理是对第三个位置填上和第一个位置相等的元素，每种情况只能填一个，(a_1)最小保证一定有的填
类推 长度为(n)的链减去一个长度为(n-1)的环可以拼成一个长为(n)的环
好啦，于是得到了一个优秀的(O(N^2))完整版
事实上第三部分的思维难度最低（但是写起来恶心啊
转移方程有
(dp_i=sum_{i=0}^{i-1} dp_j imes min_{k=j+1}^i a_k imes (-1)^{i-j-1})
化简一下
(dp_i=(-1)^{i} imes sum_{i=0}^{i-1} dp_j imes min_{k=j+1}^i a_k imes (-1)^{j+1})
发现后面很多段(dp_i)乘的都是一个(a_k)，而且(a_k)是按位置递增的
单调栈了
实现细节因人而异，不多说了
Code:
#include <cstdio>
#define ll long long
const int N=1e6+10;
const int inf=0x7fffffff;
const ll mod=1e9+7;
int n,a[N],b[N],mi=inf,id,s[N],tot;
ll dp[N],ans,f[N],sum;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",b+i);
if(b[i]<mi)
mi=b[i],id=i;
}
int cnt=0;
while(cnt<n)
{
a[++cnt]=b[id++];
id==n+1&&(id=1);
}
f[0]=1,f[1]=1-a[1],sum=a[1],dp[1]=a[1],s[++tot]=1;
for(int las,i=2;i<=n;i++)
{
while(tot&&a[s[tot]]>=a[i])
(sum-=a[s[tot]]*(f[s[tot]-1]-(tot-1?f[s[tot-1]-1]:0)))%=mod,--tot;
(sum+=a[i]*(f[i-1]-(tot?f[s[tot]-1]:0)))%=mod;
dp[i]=sum*(i&1?1:-1);
(f[i]=f[i-1]+dp[i]*(i&1?-1:1))%=mod;
s[++tot]=i;
}
for(int i=n;i>1;i--)
(ans+=dp[i]*(n-i&1?-1:1))%=mod;
printf("%lld
",(ans+mod)%mod);
return 0;
}
2018.9.21