序列
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;
}
同余方程
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;
}
WM
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;
}