寒假学习计划

比赛地址

牛客

官方题解

[A] honoka和格点三角形

题意

给出一个n*m的点阵,相邻两点距离为1.求能构成多少个不同的格点三角形,使得三角形面积为1,且至少有一条边平行于坐标轴.

题解

分两种情况考虑.

一种是边平行于y轴,这时又分两种情况,这条边的边长是1还是2.平行x轴的情况类似.注意平行于x轴和y轴的三角形只需要统计一次.

最后未化简的式子是

2(n(n-1)(m-2)+n(n-2)(m-1)+(m-1)(m-2)(n-2)+(n-1)(m-2)^{2})

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
using namespace std;

LL n,m,Ans,x,cnt,sum;

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline LL read(){
    LL p=0,f=1; char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();
    n--;    m--;
    cnt=n*(n+1)%MOD;    cnt=cnt*(m-1)%MOD;
    Ans+=cnt;
    cnt=(n+1)*(n-1)%MOD;    cnt=cnt*m%MOD;
    Ans+=cnt;
    cnt=m*(m-1)%MOD;    cnt=cnt*(n-1);
    Ans+=cnt;
    cnt=(m-1)*(m-1)%MOD;    cnt=cnt*n%MOD;
    Ans+=cnt;
    Ans=Ans*2%MOD;
    cout<<Ans<<endl;
    return 0;
}

[B] kotori和bangdream

题意

一段乐曲有n个音符,每个音符有两种可能的状态,每种状态会带来不同的分数.求最后分数的期望.

题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n;
double ans,cnt,a,b,x;

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d%lf%lf%lf",&n,&x,&a,&b);
    cnt=x/100*a+(100-x)/100*b;
    ans=cnt*n;
    printf("%.2lf\n",ans);
    return 0;
}

[C] umi和弓道

题意

给出坐标平面的n个目标和射手的坐标,现在要求射手能够射击到的目标数不超过k个,问能否通过在某个坐标轴铺设一段连续的木板来实现这个任务.如果可以,输出木板的最短长度.

题解

首先和射手同一象限的目标一定不会被挡到,直接排除.

剩下的目标和射手的连线会和坐标轴相交于一点,将这一点的横坐标或纵坐标分别记录下来,然后对x轴以及y轴上的这些点的坐标排序.按顺序枚举即可.

注意,有些交点其实是在射手与目标的反向延长线上,这种情况应舍去.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define EPS 1e-8
#define INF 0x3f3f3f3f
using namespace std;

int i,tot,k,n,tot1,tot2;
double y[N],x[N];

struct Vector{
    double x,y;
    void Clean(void){x=y=0;}
    void Write(void){printf("%.3lf %.3lf\n",x,y);}
    Vector operator +(Vector p){return (Vector){x+p.x,y+p.y};}
    Vector operator -(Vector p){return (Vector){x-p.x,y-p.y};}
    double operator *(Vector p){return x*p.y-y*p.x;}
    double operator &(Vector p){return x*p.x+y*p.y;}
};
typedef Vector V;

struct Point{
    double x,y;
    void Clean(void){x=y=0.0;}
    void Write(void){printf("%.3lf %.3lf\n",x,y);}
    Vector operator +(Point p){return (Vector){x+p.x,y+p.y};}
    Vector operator -(Point p){return (Vector){x-p.x,y-p.y};}
};
typedef Point P;

P s,w,a[N];

inline double Min(double a,double b){return (a<b)?a:b;}
inline double Max(double a,double b){return (a>b)?a:b;}
inline double Fabs(double x){return (x<-EPS)?-x:(x>EPS)?x:0;}
inline int Equ(double x,double y){return (Fabs(x-y)<EPS);}
inline double Norm(double x){return (x>0)? (x>EPS)?x:0 : (x<-EPS)?x:0;}

inline bool Point_On_Line(P x,P y,P z){return (Fabs((x-y)*(x-z)) == 0);}

inline bool Point_On_Seg(P x,P y,P z){
    double s;
    s=(x-y)*(x-z);
    if (Fabs(s)>EPS)    return 0;
    if (Min(y.x,z.x)-EPS>x.x||Max(y.x,z.x)+EPS<x.x) return 0;
    if (Min(y.y,z.y)-EPS>x.y||Max(y.y,z.y)+EPS<x.y) return 0;
    return 1;
}

inline int LineCross(P a,P b,P c,P d,P &e){
    V A=b-a,B=d-c;  e=a;
    if (Fabs(A*B) == 0)
        return (Point_On_Line(a,b,c))?0:-1;
    double l=((c-a)*B)/(A*B);
    e.x+=(b.x-a.x)*l;   e.y+=(b.y-a.y)*l;
    return 1;
}

inline void Ready(){
    register int i=0,flag=0;
    P c,d;
    c.x=0;  c.y=0;  d.x=0;  d.y=1;
    for (i=1;i<=tot;i++){
        flag=LineCross(s,a[i],c,d,w);
        if (flag==1 && Point_On_Seg(w,s,a[i]))  y[++tot1]=w.y;
    }
    sort(y+1,y+1+tot1);
    d.x=1;  d.y=0;
    for (i=1;i<=tot;i++){
        flag=LineCross(s,a[i],c,d,w);
        if (flag==1 && Point_On_Seg(w,s,a[i]))  x[++tot2]=w.x;
    }
    sort(x+1,x+1+tot2);
}

inline void Work(){
    register int i=0,sum=tot-k;
    double Ans=-1,l=0;
    for (i=1;i+sum-1<=tot2;i++){
        l=x[i+sum-1]-x[i];
        if (Ans > 0)    Ans=Min(Ans,l);
        else Ans=l;
    }
    for (i=1;i+sum-1<=tot1;i++){
        l=y[i+sum-1]-y[i];
        if (Ans > 0)    Ans=Min(Ans,l);
        else Ans=l;
    }
    if (Equ(Ans,-1))    puts("-1");
    else printf("%.10lf\n",Ans);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%lf%lf",&s.x,&s.y);
    scanf("%d%d",&n,&k);
    for (i=1;i<=n;i++){
        scanf("%lf%lf",&w.x,&w.y);
        if (w.x*s.x>0 && w.y*s.y>0) {k--;   continue;}
        a[++tot]=w;
    }
    if (k<0)    {puts("-1");    return 0;}
    Ready();    Work();
    return 0;
}

[D] hanayo和米饭

题意

n个数字,从1到n,现在有一个数字被抹去了,求这个数是多少.

题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i;
int a[100010];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();
    for (i=1;i<n;i++)   a[i]=read();
    sort(a+1,a+n);
    if (a[1]==2)    {puts("1"); return 0;}
    for (i=1;i<n;i++){
        if (a[i]!=i)    {
            printf("%d",i);
            return 0;
        }
    }
    printf("%d",n);
    return 0;
}

[E] rin和快速迭代

题意

定义f(x)x的约数个数.求给出n,求f(n)在迭代几次后能达到2.

题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

LL n,Ans;

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline LL read(){
    LL p=0,f=1; char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline void Dfs(LL x){
    register LL i=0,l=(long long)(sqrt(x)),cnt=0;
    if (x==2)   return;
    if (l*l>x)  l--;
    //cout<<x<<" "<<l<<endl;
    Ans++;
    for (i=1;i<=l;i++){
        if (!(x%i)) cnt++;
        if (!(x%i) && i*i!=x)   cnt++;
    }
    Dfs(cnt);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();
    Dfs(n);
    cout<<Ans<<endl;
    return 0;
}

[F] maki和tree

题意

给出一棵树,树上每个点为黑白两种颜色之一.求有多少个不同的点对,使得两点间的路径上只有一个黑点.

题解

树分治裸题.

找到重心后,统计从重心向下走的纯白路径数和只含一个黑点的路径数,然后根据重心节点的颜色统计答案.

官方题解是把白色的连通块缩点,然后符合条件的路径一定是白-黑-白或黑-白这样的组合,直接根据缩点后的大小统计答案即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;

int n,i,x,y,root,lsum=1,tot;
LL white,black,B,W,Ans=0;
char c[N];
int msize[N],size[N],col[N],head[N],v[N];

struct Edge{
    int t,next,l;
}e[N*8];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline void Add(int s,int t){
    e[lsum].t=t;    e[lsum].next=head[s];   head[s]=lsum++;
}

inline void FindRoot(int x,int fa){
    int i=0;
    size[x]=1;  msize[x]=0;
    for (i=head[x];i;i=e[i].next)
        if (!v[e[i].t]&&e[i].t!=fa) {
            FindRoot(e[i].t,x); msize[x]=Max(msize[x],size[e[i].t]);
            size[x]+=size[e[i].t];
        }
    msize[x]=Max(msize[x],tot-msize[x]);
    if (msize[x]<msize[root])   root=x;
}

inline void Dfs(int x,int fa,int p){
    register int i=0;
    p+=col[x];
    if (p>=2)   return;
    (p)?++black:++white;
    for (i=head[x];i;i=e[i].next){
        if (v[e[i].t] || e[i].t==fa)    continue;
        Dfs(e[i].t,x,p);
    }
}

inline void Calc(int x){
    register int i=0;
    B=W=0;
//  cout<<x<<" "<<Ans<<endl;
    for (i=head[x];i;i=e[i].next){
        if (v[e[i].t])  continue;
        black=white=0;
        Dfs(e[i].t,x,0);
        if (col[x]) Ans+=W*white;
            else Ans+=W*black+B*white;
//      cout<<e[i].t<<" "<<black<<" "<<white<<" "<<Ans<<endl;
        B+=black;   W+=white;
    }
    if (col[x]) Ans+=W; else Ans+=B;
}

inline void Solve(int x){
    register int i=0;
    v[x]=1; Calc(x);
    for (i=head[x];i;i=e[i].next)
        if (!v[e[i].t]){
            root=0; tot=size[e[i].t];
            FindRoot(e[i].t,0); Solve(root);
        }
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();
    scanf("%s",&c);
    for (i=1;i<=n;i++)  col[i]=(c[i-1]=='W')?0:1;
    for (i=1;i<n;i++){
        x=read();   y=read();
        Add(x,y);   Add(y,x);
    }
    msize[root=0]=INF;  tot=n;
    FindRoot(1,0);  Solve(root);
    cout<<Ans<<endl;
    return 0;
}

[G] eli和字符串

题意

给出一个字符串,求其中的最短子串,满足其中含有至少k个相同字母.

题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;

int n,k,Ans,i,j,x;
char c[N];
int w[27][N],sum[27];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   k=read();
    scanf("%s",&c);
    if (k==1){
        puts("1");  return 0;
    }
    for (i=0;i<n;i++){
        x=c[i]-'a'; sum[x]++;
        w[x][sum[x]]=i;
    }
    Ans=INF;
    for (i=0;i<26;i++)  w[i][0]=1;
    for (i=0;i<26;i++)
        for (j=k;j<=sum[i];j++)
            Ans=Min(Ans,w[i][j]-w[i][j-k+1]+1);
    if (Ans!=INF)
    cout<<Ans<<endl;
    else cout<<-1<<endl;
    return 0;
}

[H] nozomi和字符串

题意

给出一个01串,可以执行k次翻转操作:每次操作选择某一位,然后把0变成1,或是1变成0.求能获得的最长全0或全1子串是多少.

题解

签到题.

二分答案+前缀和.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;

int n,k,Ans=0;
int s[N];
char c[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline void Ready(){
    register int i=0,x=0;
    for (i=1;i<=n;i++){
        x=c[i-1]-48;    s[i]=s[i-1]+x;
    }
}

inline bool Check(int pos,int l){
    int sum=0;
    if (pos+l-1>n)  return 0;
    sum=s[pos+l-1]-s[pos-1];
    if (sum<=k || (l-sum) <= k) return 1;
    return 0;
}

inline void Work(){
    register int i=0,low=1,high=n,mid=0,ans=0;
    for (i=1;i<=n;i++){
        low=1;  high=n; ans=0;
        while (low<high){
            mid=(low+high)>>1;
            if (Check(i,mid))   ans=mid,low=mid+1;
            else high=mid-1;
        }
        while (Check(i,ans+1))  ans++;
        while (!Check(i,ans))   ans--;
        Ans=Max(Ans,ans);
    }
    printf("%d\n",Ans);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   k=read();
    if (n==1){
        puts("1");
        return 0;
    }
    scanf("%s",&c);
    Ready();    Work();
    return 0;
}

[I] nico和niconiconi

题意

给出一个字符串,对三种子串进行计数:nico,niconi,niconiconi.最后每一种子串可以带来a,b,c的得分.计数过程中,不允许被统计的子串有重叠的情况.求最大得分.

题解

DP.

分三种情况从前向后转移即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 300010
#define INF 0x3f3f3f3f
using namespace std;

int n,i;
LL a,b,c,Ans=0;
char s[N];
LL f[N];
string name[3];

inline LL Max(LL a,LL b){return (a>b)?a:b;}

inline LL read(){
    LL p=0,f=1; char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline LL Check(int A,int B){
    register int p=0,i=0;
    if (B-A==3) p=0;
    else if (B-A==5)    p=1;
    else p=2;
    for (i=A;i<=B;i++)
        if (s[i]!=name[p][i-A]) return 0;
    if (!p) return a;
    else if (p==1)  return b;
    else return c;
} 

inline void DP(){
    register int i=0;
    memset(f,0,sizeof(f));
    for (i=1;i<=n;i++){
        f[i]=Ans;
        if (i>=4)   f[i]=Max(f[i],f[i-4]+Check(i-3,i));
        if (i>=6)   f[i]=Max(f[i],f[i-6]+Check(i-5,i));
        if (i>=10)  f[i]=Max(f[i],f[i-10]+Check(i-9,i));
        Ans=Max(f[i],Ans);
    }
    for (i=1;i<=n;i++)  Ans=Max(Ans,f[i]);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   a=read();   b=read();   c=read();
    scanf("%s",s+1);
    if (n<4)    {puts("0"); return 0;}
    name[0]="nico";     name[1]="niconi";   name[2]="niconiconi";
    DP();
    cout<<Ans<<endl;
    return 0;
}

[J] u's的影响力

题意

已知f(1)=x,f(2)=y,f(n)=f(n-1)f(n-2)a^{b}.求 f(n)

题解

手算前几项后不难得出,答案为

x^{Fib(n-2)}y^{Fib(n-1)}a^{g(n-3)b}

Fib(n)表示斐波那契数列第n项. g(1)=1,g(2)=2,g(3)=4,g(n)=2g(n-1)-g(n-3)

有了g(n)的递推式后,就可以套矩阵快速幂去做了.

注意因为答案要对1e9+7取模,所以需要对指数进行欧拉降幂.也就是说,在计算指数的过程中需要对1e9+6取模.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<unordered_map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL unsigned long long
#define N 4
#define MO  1000000007
#define MOD 1000000006
#define INF 0x3f3f3f3f
using namespace std;

LL n,x,y,a,b,i,cnt,Ans,sum,Sum;
unordered_map<LL,LL> M;

LL Fib(LL x){
    if (M.count(x)) return M[x];
    LL a=(x+1)/2,b=x/2+1;
    return M[x]=((Fib(a)*Fib(b))%MOD+(Fib(a-1)*Fib(b-1)))%MOD;
}

inline LL Mi(LL x,LL y){
    LL p=x,t=1,Res=1;
    for (;t<=y;(t&y)?Res=(Res*p)%MO:0,p=(p*p)%MO,t<<=1);
    return Res;
}

class Matrix{
    public:
        int sz;
        LL a[N][N];
        void Init(int x){sz=x;}
        void Clear(void){memset(a,0,sizeof(a));}
}A,B,C;

Matrix operator *(Matrix x,Matrix y){
    int i=0,j=0,k=0,Sz=x.sz;
    Matrix c;   c.Clear();  c.Init(Sz);
    for (i=1;i<=Sz;i++)
        for (j=1;j<=Sz;j++)
            for (k=1;k<=Sz;k++)
                c.a[i][j]=(c.a[i][j]+x.a[i][k]*y.a[k][j]%MOD+MOD)%MOD;
    return c;
}

inline LL Array(LL n){
    register LL i=n-3,j=1;
    if (n==1)   return 1;
    if (n==2)   return 2;
    if (n==3)   return 4;
    A.Init(3);  B.Init(3);
    A.Clear();  B.Clear();
    B.a[1][1]=B.a[2][2]=B.a[3][3]=1;
    A.a[1][1]=2;    A.a[1][3]=MOD-1;
    A.a[2][1]=1;    A.a[3][2]=1;
    for (;j<=i;j<<=1){
        if (j&i)    B=B*A;
        A=A*A;
    }
    return (4*B.a[1][1]%MOD+2*B.a[1][2]%MOD+B.a[1][3])%MOD;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%llu%llu%llu%llu%llu",&n,&x,&y,&a,&b);
    if (n<=2){
        if (n==1)   cout<<x%MO;
        if (n==2)   cout<<y%MO;
        return 0;
    }
    if (a%MO==0 || x%MO==0 || y%MO==0){
        puts("0");  return 0;
    }
    a%=MO;  x%=MO;  y%=MO;  b%=MOD;
    M[1]=M[2]=1;
    cnt=Array(n-2); cnt=Mi(a,(cnt*b)%MOD);
    sum=Fib(n-2);   sum=Mi(x,sum);
    Sum=Fib(n-1);   Sum=Mi(y,Sum);
    Ans=(cnt*sum)%MO;   Ans=(Ans*Sum)%MO;
    cout<<Ans<<endl;
    return 0;
}

总结

寒假基础训练第一场,感觉难度并不是很高,考察的都是很基本的东西.

比赛途中也暴露了一些问题,比如计算几何里判断点在线段上的板子是有错的,里面的式子不知为什么套了个绝对值.也明显感觉到做计几的题不是很熟练,手感有待提高.

下午也犯了n多智障错误,比如最后一题特判前两项忘了取模导致最后WA了6发;F题其实有简单解法,结果没有细想直接拿树分治莽了上去,浪费了一些时间.希望以后几场可以改进.

说点什么
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...