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 %lld ",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 %lld ",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) ot=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 ");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 ",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 ",ans); } int main(){ freopen("evolve.in","r",stdin); freopen("evolve.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }