[CZYZ2016]day8
序列
Description
给定一个长度为\(n\)的正整数序列\(a\)。可以将序列分成若干段,定义第\(i\)段的权值\(x_i\)为这一段中所有数的最大值,特殊地,\(x_0=0\)。求\(\sum_{i=1}^{m}|x_i-x_{i-1}|\)的最小值以及划分方案数,\(\sum_{i=1}^{m}(x_i-x_{i-1})^2\) 的最小值以及划分方案数,其中\(m\)为划分的段数。
Input
第一行一个整数\(n\)。第二行\(n\)个正整数\(a_1-a_n\)。
Output
按顺序输出四个非负整数表示答案,其中两个方案数均对\(10^9+7\)取模。
Sample Input
4
10 30 20 30
Sample Output
30
6
500
3
HINT
\(n\;\leq\;10^5,1\;\leq\;a_i\;\leq\;10^9\).
Solution
从后往前单调栈维护一个不上升序列,记为序列\(s\)。
记\(s\)的长度为\(l\),\(s[l+1]=0\)。将\(s\)在\(a\)的位置记为\(d\)。
显然,对于一个序列\(a\),\(\sum_{i=1}^{m}|x_i-x_{i-1}|\)的最小值为序列中最大的数。
在\(s_i\)与\(s_{i+1}\)之间,定一个断点有\((d_i-d_{i+1})\)种方案,不定断点,有\(1\)种方案。
所以总方案数为\(\prod_{i=1}^{m-1}(d_{i}-d_{i+1}+1)\)。
易证\(\sum_{i=1}^{m}(x_{i}-x_{i-1})^2\)的最小值为\(\sum_{i=1}^{l}(s_{i}-s_{i+1})^2\)。
显然,s中的每一种值至少需要出现一次,所以对于每种值的情况进行考虑。
在\([d_{i-1},d_i)\)这段区间内定一个断点,有\((d_i-d_{i-1})\)种方案,不定断点,有\(1\)种方案。
由于每个值都必须出现一次,所以不能出现都不定断点的情况。
记所有不同的值为\(b\),则总方案数为\(\prod_{i=1}^{|b|}(\prod_{s[j]=b[i]}(d_{j-1}-d_{j}+1)-1)\)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 1000005
#define M 1000000007ll
using namespace std;
typedef long long ll;
ll ans,tot=1,sum;
int a[N],s[N],x[N],t,n;
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=ret*10+c-'0';
c=getchar();
}
return ret;
}
inline ll sqr(ll k){
return k*k;
}
inline void init(){
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=n;i;--i){
while(t&&a[i]>s[t]) --t;
s[++t]=a[i];x[t]=i;
}
s[t+1]=0;
for(int i=1;ij&&k>1;--k)
sum=sum*(x[k-1]-x[k]+1)%M;
if(j) --sum;
tot=tot*(sum)%M;
}
printf("%lld\n%lld\n",ans,tot);
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return 0;
}
同余方程
Description
给定一个质数\(p\),构造出一个模\(p\)意义下的\(n\)次同余方程,使得该方程在\([0,p)\)中的解尽可能少。
Input
一行两个整数\(n,p\)。
Output
依次输出\(x^n,x^{n-1},…,x^0\)前的系数。
Sample Input
1 97
Sample Output
1 0
HINT
\(n\;\leq\;100,n 为质数。 Solution 高次同余方程的概念:\(f(x)=0(mod\;m)\)(\(f(x)\)为次数大于\(1\)的整式) 显然\(n=1\)时,显然所有方程都有\(1\)个解,任意构造方程即可; \(n>1\)时,设\(f(x)=x^n+(p-1)x\)。则\(f(0)=f(1)\),所以一定存在一个数\(y\)使得\(f(x)\not=y\)。 答案即为\(x^n+(p-1)x+(p-t)\)即可。 Description 给定一个序列\(A\),选择\(i,j\),记糟糕指数为\(A_i|A_{i+1}|A_{i+2}|…|A_j\),其中|为二进制或运算。 求有多少组\((i,j)\)使得糟糕指数小于\(M\)。 Input 第一行两个正整数\(N,M\)。 Output 一行一个整数表示选择方案数。 Sample Input Sample Output HINT \(1\;\leq\;N\;\leq\;10^5,0\;\leq\;M\;\leq\;2^{30},1\;\leq\;A_i\;\leq\;2^{30}\) Solution 除非有人和我一样因为迷之断句看不懂题目,不然肯定会觉得是一道水题。 把每个数转成二进制,尺取法即可。#include
WM
第二行为\(N\)个正整数\(A_1,A_2,…,A_n\)。4 6
1 3 5 1
2
#include