QDC DAY1

　　暴毙了，比较自闭的心理，有点崩溃..

LINK：幸福一道曾经的我肯定能写出来的但是我心态崩了所以没有推出来。

当然还是我比较垃圾但同时也不垃圾。。。

求 $T_n =\displaystyle \sum_{i=0}^{n}F_n$ 其中 $Fn=\displaystyle \sum_{i=0}^{n}f_i \times f_{n-i}$

其中$f$是斐波那契数列 $f_0=1,f_1=1$... 求 $F_n$ 其中n<=1e18

一个比较显然的思路是把Tn 写出来不断化简最后发现是一个前缀和的形式然后发现可以O(n)计算了。

这样只有70分的垃圾成绩。

//#include<bits/stdc++.h>

#include<iomanip>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<deque>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<stack>

#include<algorithm>

#include<vector>

#include<cctype>

#include<utility>

#include<set>

#include<bitset>

#include<map>

#define INF 1000000010

#define ll long long

#define mp(x,y) make_pair(x,y)

#define un unsigned

#define db double

#define EPS 1e-5

#define mod 998244353

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const ll MAXN=;

ll n;

ll ans,sum;

ll f[MAXN];

signed main()

{

    //freopen("1.in","r",stdin);

    n=read();

    f[]=;f[]=;

    for(ll i=;i<=n;++i)f[i]=(f[i-]+f[i-])%mod;

    if(n<=)

    {

        for(ll i=;i<=n;++i)

        {

            for(ll j=;j<=i;++j)

                ans=(ans+f[j]*f[i-j])%mod;

        }

        printf("%lld\n",ans);

        return ;

    }

    if(n<=)

    {

        for(int i=;i<=n;++i)sum=(sum+f[i])%mod;

        for(int i=;i<=n;++i)

        {

            sum=((sum-f[n-i+])+mod)%mod;

            ans=(ans+f[i]*sum%mod)%mod;

        }

        printf("%lld\n",ans);

        return ;

    }

    //考虑 100分 容斥还没有想好 自闭

    printf("%lld\n",ans);

    return ;

}

继续思考如何优化发现这个其实是倒三角求和扩大两倍是不正确的所以我当时算2h然后弃疗了。思考方向不是太对。

观察一下$F_n$这个式子。简单的化简成 $F_n=\sum_{i=0}^{n-2f_i \times f_{n-i}+f_{n-1}f_1+f_n+f_0$

比较显然的是这个东西显然可以化简为 $F_n=F_{n-1}+F_{n-2}+f_n$;

//#include<bits/stdc++.h>

#include<iomanip>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<deque>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<stack>

#include<algorithm>

#include<vector>

#include<cctype>

#include<utility>

#include<set>

#include<bitset>

#include<map>

#define INF 1000000010

#define mod 998244353

typedef long long ll;

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const ll MAXN=;

ll n,m=;

struct wy

{

    ll f[MAXN];

    ll b[MAXN][MAXN];

    wy(){memset(f,,sizeof(f));memset(b,,sizeof(b));}

    friend wy operator *(wy A,wy B)

    {

        wy tmp;

        for(ll i=;i<=m;++i)

            for(ll j=;j<=m;++j)

                for(ll k=;k<=m;++k)

                    tmp.b[i][j]=(tmp.b[i][j]+A.b[i][k]*B.b[k][j])%mod;

        for(int i=;i<=m;++i)tmp.f[i]=A.f[i];

        return tmp;

    }

    friend wy operator -(wy A,wy B)

    {

        wy tmp;

        for(ll i=;i<=m;++i)

            for(ll j=;j<=m;++j)

                tmp.f[i]=(tmp.f[i]+A.f[j]*B.b[j][i])%mod;

        for(int i=;i<=m;++i)

            for(int j=;j<=m;++j)tmp.b[i][j]=A.b[i][j];

        return tmp;

    }

    friend wy operator ^(wy A,ll p)

    {

        while(p)

        {

            if(p&)A=A-A;

            A=A*A;

            p=p>>;

        }

        return A;

    }

}C;

signed main()

{

    //freopen("1.in","r",stdin);

    n=read();

    C.b[][]=;C.b[][]=;C.b[][]=;C.b[][]=;

    C.b[][]=;C.b[][]=;C.b[][]=;C.b[][]=;

    C.b[][]=;C.b[][]=;C.b[][]=;

    C.f[]=;C.f[]=;C.f[]=;C.f[]=;C.f[]=;

    C=C^(n-);

    printf("%lld\n",C.f[m]);

    return ;

}

所以就有了矩阵乘法的优化以后要敏感一点或者从不同的方向推一下。

LINK：树链刨分简单的树形dp但需要一些小细节。当时可能有一点点慌所以题目没怎么看的懂。

想想当时还是比较蠢的。但是过后做法还是很容易就看出来的了。

首先是代价的问题这个进行简单的树上差分即可解决。考虑求答案不知道哪个点是根。

很好那么直接就直接一点以 1 为根那么答案我们显然可以贪心的统计出来。

考虑换根。这里值得注意的是我们是将边权转点权了看起来很不形象的样子其实可以直接放到边权上不过那也应该是点权的样子存在着。

直接换根吧然后有一个细节其实主要过程是 x 到 y的换根这里维护一个最大值和次大值就是为了防止y是x的最大值什么的。

还有一点是换过根之后的话 x就光荣的成为了y的儿子了在y 继续向下换根的过程中 y的最大值和次大值应该要被x所更新。（重点不要像我这个sb一样没注意到）

当然这个swap是必要的qwq 。。因为 swap x y 是要把x变成y的儿子再swap回来是为了保证原本的关系因为x其他儿子还需要转移。

//#include<bits/stdc++.h>

#include<iomanip>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<deque>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<stack>

#include<algorithm>

#include<vector>

#include<cctype>

#include<utility>

#include<set>

#include<bitset>

#include<map>

#define max(x,y) ((x)>(y)?(x):(y))

#define INF 1000000010

#define ll long long

#define mp(x,y) make_pair(x,y)

#define un unsigned

#define db double

#define EPS 1e-5

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const ll MAXN=;

ll n,len,m,sum,cnt;

ll lin[MAXN],nex[MAXN<<],ver[MAXN<<];

ll sz[MAXN],vis[MAXN],f[MAXN],s[MAXN],son[MAXN],sx[MAXN];

struct wy

{

    ll x,y,lca;

}t[MAXN];

vector<ll>g[MAXN],id[MAXN];

inline void add(ll x,ll y)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

}

inline ll getfather(ll x){return x==f[x]?x:f[x]=getfather(f[x]);}

inline void dfs(ll x)

{

    vis[x]=;f[x]=x;

    for(ll i=lin[x];i;i=nex[i])

    {

        ll tn=ver[i];

        if(vis[tn])continue;

        dfs(tn);

        f[tn]=x;

    }

    for(unsigned ll i=;i<g[x].size();++i)

    {

        ll tn=g[x][i];

        ll ID=id[x][i];

        if(vis[tn])t[ID].lca=getfather(tn);

    }

}

inline void dfs(ll x,ll father)

{

    f[x]=;

    for(ll i=lin[x];i;i=nex[i])

    {

        ll tn=ver[i];

        if(tn==father)continue;

        dfs(tn,x);

        sz[x]+=sz[tn];

        if(sz[son[x]]<sz[tn])son[x]=tn;

        f[x]+=f[tn];

    }

    for(ll i=lin[x];i;i=nex[i])

    {

        ll tn=ver[i];

        if(tn==father)continue;

        if(son[x]==tn)continue;

        if(sz[sx[x]]<sz[tn])sx[x]=tn;

    }

    f[x]+=sz[son[x]];sum+=sz[x];

}

inline void dp(ll x,ll father)

{

    for(ll i=lin[x];i;i=nex[i])

    {

        ll tn=ver[i];

        if(tn==father)continue;

        s[tn]=f[tn]-sz[son[tn]]+s[x]-f[tn];

        if(son[x]==tn)s[tn]=s[tn]-sz[tn]+sz[sx[x]];

        swap(sz[x],sz[tn]);

        if(sz[x]>sz[son[tn]])

        {

            sx[tn]=son[tn];

            son[tn]=x;

        }

        else if(sz[x]>sz[sx[tn]])sx[tn]=x;

        s[tn]+=sz[son[tn]];

        dp(tn,x);

        swap(sz[x],sz[tn]);

    }

}

signed main()

{

    //freopen("1.in","r",stdin);

    //freopen("1.out","w",stdout);

    n=read();m=read();

    for(ll i=;i<n;++i)

    {

        ll x,y;

        x=read();y=read();

        add(x,y);add(y,x);

    }

    for(ll i=;i<=m;++i)

    {

        ll x,y;

        x=read();y=read();

        t[i]=(wy){x,y};

        if(x==y){t[i].lca=x;continue;}

        g[x].push_back(y);

        g[y].push_back(x);

        id[x].push_back(i);

        id[y].push_back(i);

    }

    dfs();

    for(ll i=;i<=m;++i)

    {

        ++sz[t[i].x];++sz[t[i].y];

        --sz[t[i].lca];--sz[t[i].lca];

    }

    dfs(,);s[]=f[];

    dp(,);

    for(ll i=;i<=n;++i)cnt=max(cnt,s[i]);

    printf("%lld\n",sum-cnt);

    return ;

}

巴特西

QDC DAY1

最新文章

热门文章