T1

我已经被拉格朗日插值蒙蔽了双眼，变得智障无比。

第一反应就是拉格朗日插值，然后就先放下了它。

模数那么小，指数那么大，这是一套noip模拟题，拉格朗日，你脑袋秀逗了？

无脑暴力20分贼开心。

正解：

因为模数很小，所有大于模数的数可以先mod再算，就相当于多次用了从0到mod-1的答案。

对于0到mod-1（相当于1到mod）可以只算素数，由于这个函数是积性函数，所以可以在 线性筛素数 的时候顺便求i的k次方

//Serene#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn=3e6+10;long long n,m,mod,ans;long long f[maxn];long long rs;long long qp(long long x,long long k) { if(x<=1) return x; rs=1; while(k&&rs) { if(k&1) rs=rs*x%mod; x=x*x%mod;k>>=1; } return rs;}bool ok[maxn];int prime[maxn/5],tot_p;void get_p() { f[1]=1; for(int i=2;i<=mod;++i) { if(!ok[i]) prime[++tot_p]=i,f[i]=qp(i,m); for(int j=1;j<=tot_p&&prime[j]<=mod/i;++j) { ok[i*prime[j]]=1;f[i*prime[j]]=f[i]*f[prime[j]]%mod; if(i%prime[j]==0) break; } }}int main() { freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); cin>>mod>>m>>n; get_p(); for(int i=1;i<=mod;++i) f[i]=(f[i-1]+f[i])%mod; ans=(f[mod]*(n/mod)+f[n%mod])%mod; cout<
          
         
        
       
      
     

　　

 

T2

二分，线段覆盖，很裸，具体见代码：

//Serene#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn=1e5+10;const double pi=acos(-1);int n;double L,R,maxh=0;double dn[maxn][4];struct Node{ double x,y;}node[maxn];bool cmp(const Node& a,const Node& b) { return a.y
           
            R||dn[i][1]+x
            
             L||maxr
             
              1;--i) { minl=min(minl,node[i].x); if(node[i-1].y
              
               
                L)) return 0; } return 1;}int main() { freopen("light.in","r",stdin); freopen("light.out","w",stdout); cin>>n>>L>>R; for(int i=1;i<=n;++i) { scanf("%lf%lf%lf",&dn[i][1],&dn[i][2],&dn[i][3]); maxh=max(maxh,dn[i][2]); } double l=0,r=maxh,mid; while(r-l>=1e-7) { mid=(l+r)/2.0; if(check(mid)) l=mid; else r=mid; } printf("%.7lf",l); fclose(stdin);fclose(stdout); return 0;}
               
              
             
            
           
          
         
        
       
      
     

　　

T3：

我写的线段树你不会杀了我吧（所以竟然比pyh跑得快？！）。

我建了n颗线段树（不要问我为什么建这么多），但是并不用把所有节点开完，每次修改的时候再新建节点。

对于第i颗线段树的第j个位置表示把前i个数合并，且合并后最大数为j，需要的最小合并次数。

我们知道，如果最后合并出来的东西是确定的，无论合并顺序是否相同，合并次数是确定的。

具体地说：如果我把第 x 到第 y 共（ y - x +1）个数合并需要合并（ y - x ）次。

那么我们每次从前到后扫一遍，扫到一个 i ，我们从 i - 1 到 0逆序枚举 j ，我们把从第 j+1到i的所有数合并，（在第j颗线段树里面查询<=合并后的值的最小合并次数）并计算答案（插入第i颗线段树）。

关于优化：就是为什么从 i - 1 到 0逆序枚举 j ，我们知道如果存在一个 k （ k > j ）所以sum[i]-sum[k]<sum[i]-sum[j]，那么如果第i颗线段树中 最大数为sum[i]-sum[k]的点的需要的最小合并次数比 最大数为sum[i]-sum[j]的点的需要的最小合并次数 要小，那么再更新最大数为sum[i]-sum[j]的点就不必要了。

//Serene#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn=1500+10,INF=1e6;int n,a[maxn],sum[maxn],maxnum=0,ans,tot;int aa;char cc;int read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}struct Node{ int l,r,minnum,son[2];}node[maxn*4000];void chge(int pos,int t,int x) { node[pos].minnum=min(node[pos].minnum,x); if(node[pos].l==node[pos].r) return; int mid=(node[pos].l+node[pos].r)>>1; if(t<=mid) { if(!node[pos].son[0]) { node[pos].son[0]=++tot; node[tot].l=node[pos].l; node[tot].r=mid; node[tot].minnum=INF; } chge(node[pos].son[0],t,x); } else { if(!node[pos].son[1]) { node[pos].son[1]=++tot; node[tot].l=mid+1; node[tot].r=node[pos].r; node[tot].minnum=INF; } chge(node[pos].son[1],t,x); }}int q(int pos,int r) { if(!pos) return INF; if(node[pos].r<=r) return node[pos].minnum; int mid=(node[pos].l+node[pos].r)>>1; if(r<=mid) return q(node[pos].son[0],r); else return min(q(node[pos].son[0],mid),q(node[pos].son[1],r));}int main() { freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); n=read();int x,y; ans=n-1; for(int i=1;i<=n;++i) a[i]=read(),sum[i]=a[i]+sum[i-1]; for(int i=1;i<=n;++i) node[i].l=1,node[i].r=sum[i],node[i].minnum=INF; tot=n;int ff; for(int i=1;i<=n;++i) { ff=ans; for(int j=i-1;j>=0;--j) { x=sum[i]-sum[j]; if(j) y=q(j,x)+i-j-1; else y=i-j-1; if(y>=ff) continue;//优化 chge(i,x,y);ff=y; } } ans=min(ans,q(n,sum[n])); cout<
          
         
        
       
      
     

　　

其实那个线段树并不必要，直接用n平方算法过，证明在代码下面。

//Serene#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn=1500+10,INF=1e6;int n,sum[maxn],ans[maxn],g[maxn];int aa;char cc;int read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}int main() { freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); n=read();int x,y; for(int i=1;i<=n;++i) sum[i]=read()+sum[i-1]; for(int i=1;i<=n;++i) { for(int j=i-1;j>=0;--j) { g[i]=x=sum[i]-sum[j]; if(x>=g[j]) { ans[i]=ans[j]+i-j-1; break; } } } cout<
          
         
        
       
      
     

　　

zyh说这道题可以加一个单调队列变成nlogn，但是实际运行比n²慢。%%%

题解（来源：）：

形成非降序列的最少合并次数

给定一个序列，你每次可以合并相邻两个元素，新的元素为这两个元素的和。你需要使得若干次合并之后的序列非降，求最小合并次数。

[LYP的并，tyvj2008tower，QW的CCL]

解析：设f[i]表示以i结尾的所有数分成的组数,g[i]存第i个数结尾的数它这组的数的值,那么转移为:

f[i]=max{f[j]+1}(j<i,s[i]-s[j]>=g[j]),转移f[i]的同时转移g[i]为s[i]-s[j],

初始f[i]=1,g[i]=s[i]. 

通过观察我们发现,设当前分了k组,第i个数,最坏分到第k组,所以,f数组一定是不减的,所以j只要倒着循环,找到第一个满足s[i]-s[j]>=g[j]的j,转移f[i].

开始认为此方程有问题 {

存在p，使得f[p]在所有已得到的f值中最大；若存在q满足f[q]<f[p]且q>p，则此方程有bug。但是这种情况不存在！f值单调非降！}，

另外有单调队列做法。