T1
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<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#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;i<t;++i)
tot=tot*(ll)(x[i]-x[i+1]+1)%M;
printf("%d\n%lld\n",s[1],tot);
for(int i=1;i<=t;++i)
ans+=sqr((ll)(s[i]-s[i+1]));
tot=1;
for(int i=t,j;i;i=j){
sum=1;
for(j=i-1;j&&s[j]==s[i];--j);
for(int k=i;k>j&&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;
}
T2
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<p<10^5,p$为质数。
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)$即可。
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100005
using namespace std;
typedef long long ll;
ll n,p;
bool b[N];
inline ll read(){
ll ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=ret*10+c-'0';
c=getchar();
}
return ret;
}
inline void init(){
scanf("%lld%lld",&n,&p);
if(n==1){
printf("1 0\n");return;
}
for(ll i=2,k;i<p;++i){
k=i;
for(ll j=1;j<n;++j)
k=k*i%p;
k=(k+(p-1)*i)%p;
b[k]=true;
}
printf("1 ");
for(ll i=2;i<n;++i)
printf("0 ");
printf("%lld ",p-1);
for(ll i=1;i<p;++i)
if(!b[i]){
printf("%lld\n",p-i);break;
}
}
int main(){
freopen("equation.in","r",stdin);
freopen("equation.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return 0;
}
T3
Description
给定一个序列$A$，选择$i,j$，记糟糕指数为$A_i|A_{i+1}|A_{i+2}|…|A_j$,其中|为二进制或运算。
求有多少组$(i,j)$使得糟糕指数小于$M$。
Input
第一行两个正整数$N,M$。
第二行为$N$个正整数$A_1,A_2,…,A_n$。
Output
一行一个整数表示选择方案数。
Sample Input
4 6
1 3 5 1
Sample Output
2
HINT
$1\;\leq\;N\;\leq\;10^5,0\;\leq\;M\;\leq\;2^{30},1\;\leq\;A_i\;\leq\;2^{30}$
Solution
除非有人和我一样因为迷之断句看不懂题目，不然肯定会觉得是一道水题。
把每个数转成二进制，尺取法即可。
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 32
#define N 1000005
using namespace std;
typedef long long ll;
ll ans;
int s[N][M],n,m,t;
inline bool chk(int l,int r){
int ret=0;
for(int i=1,k=1;i<M;++i,k<<=1)
if(s[r][i]-s[l][i]) ret+=k;
return ret<=m;
}
inline void init(){
scanf("%d%d",&n,&m);
for(int i=1,k;i<=n;++i){
scanf("%d",&k);
for(int j=1;j<M;++j,k>>=1){
s[i][j]=s[i-1][j];
if(k&1) ++s[i][j];
}
}
for(int i=1;i<=n;++i){
t=max(t,i);
while(t<n&&chk(i-1,t+1)) ++t;
ans+=(ll)(t-i);
}
printf("%lld\n",ans);
}
int main(){
freopen("evolve.in","r",stdin);
freopen("evolve.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return 0;
}