2020牛客暑期多校训练营(第七场)
in 牛客多校多校训练 with 0 comment

2020牛客暑期多校训练营(第七场)

in 牛客多校多校训练 with 0 comment

摘要

/ABCDEFGHIJ
场上
zyj
wrf
lmj

题目

A.Social Distancing

zyj (赛后) +0

题意

给一个半径为$r$的圆,你需要在圆内确定$n$个整数点,使得$\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^{n} \operatorname{dis}(i, j)^{2}$最大,其中$\operatorname{dis}(i, j)$为点$i$与点$j$之间的欧几里得距离。

题解

快来看rls啊

太长不想看版本:

$$\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^{n} \operatorname{dist}(i, j)^{2} = n \sum\limits_{i=1}^{n}\left(x_{i}^{2}+y_{i}^{2}\right)-\left(\sum\limits_{i=1}^{n} x_{i}\right)^{2}-\left(\sum\limits_{i=1}^{n} y_{i}\right)^{2}$$

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
#define ti tuple<int,int,int>
typedef long long ll;
const int maxn=(int)1e4+100;
const int mod=(int)1e9+7;
int dp[9][666][666];//前i个点,横坐标和为j,纵坐标和为k时距离平方的max
int f[9][33];//放i个点,半径为r的max
vector<ti> v;
void precal(){
    int st=288;
    rep(i,-30,30) rep(j,-30,30) v.pb(make_tuple(i*i+j*j,i,j));
    sort(v.begin(),v.end());memset(dp,-0x3f,sizeof dp);
    dp[0][st][st]=0;int sz=v.size(),pos=0;
    rep(r,1,30){
        while(pos<sz&&get<0>(v[pos])<=r*r){
            ti p=v[pos++];
            rep(i,1,8) rep(j,-r*i+st,r*i+st) rep(k,-r*i+st,r*i+st)
            dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-get<1>(p)][k-get<2>(p)]+get<0>(p));
        }
        rep(i,1,8) rep(j,-r*i+st,r*i+st) rep(k,-r*i+st,r*i+st)
        f[i][r]=max(f[i][r],i*max(dp[i][j][k],0)-(j-st)*(j-st)-(k-st)*(k-st));
    }
}
int main(){
    precal();
    int t;scanf("%d",&t);
    while(t--){
        int n,r;scanf("%d%d",&n,&r);
        printf("%d\n",f[n][r]);
    }
}

B.Mask Allocation

lmj+wrf (01:32:01) +4

题意

将n*m分成数量最少的数,使得可以变成m个n和n个m

题解

辗转相除法即可

代码

#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
  
const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;
  
const int N=100020;
  
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int v[10000200];
int cnt=0;
  
int main(void)
{
    //ios::sync_with_stdio(false);
      
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
      
    for(int _=read();_>0;_--)
    // for(int _=100000000-1;_>0;_--)
    {
        int n=read(),m=read();
// int n=_/10000+1,m=_%10000+1;
// int tn=n,tm=m;
cnt=0;
        // vector<int> v;
        int s=n*m;
  
        do
        {
            if(n>m) swap(n,m);
            for(int i=0;i<m/n*n;i++) v[cnt++]=n,s-=n;
            m%=n;
        } while (n!=0 && m!=0);
        int g=__gcd(n,m);
        for(int i=0;i<s;i+=g) v[cnt++]=g;
        printf("%d\n",cnt);
         for(int i=0;i<cnt;i++) printf("%d ",v[i]);
         printf("\n");
    }
      
    return 0;
}

C.A National Pandemic

zyj (赛后) +2

题意

一棵树,三种操作:
1.一个中心城市$x$,所有城市y的值$+=w-dist(x,y)$;
2.将城市$x$的值与$0$取$min$
3.询问单点的值。

题解

首先解决操作2,不难发现这个操作只会影响单点,对于其他点没有影响。因此我们只需要对每个点开一个数组$w[x]$表示点$x$需要额外加的值,每次进行操作2时先算一下当前$x$的值$res$,如果这个值大于0就把$w[x]-=res$,最后询问答案时再加上$w[x]$即可。

接下来解决操作1,我们考虑一次修改对$y$来说会增加$w-\operatorname{dis}(x, y)$,又有:
$$w-\operatorname{dis}(x, y)=w-\left(\operatorname{dep}(x)+\operatorname{dep}(y)-2 {*} \operatorname{dep}(l c a)\right)=w-\operatorname{dep}(x)-\operatorname{dep}(y)+2^{*} \operatorname{dep}(l c a)$$
不难发现$w-\operatorname{dep}(x)$是一个定值,相当于对全局每个点都要加一个这个值,用一个全局的$now$记一下即可。接下来是$\operatorname{dep}(y)$,相当于对每个点都要减去一个$\operatorname{dep}(y)$,同样地用一个$num$记一下每个点要减几次自己的$dep$即可。
处理${*} \operatorname{dep}(l c a)$可以用树上差分解决,具体就是每次将$x$到$root$的路径上加2,询问的时候需要加上点$y$到$root$的路径和。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
#define lson rt<<1
#define rson rt<<1|1
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
struct Edge{
    int v,w,nxt;
}g[maxn<<1];
int head[maxn],edge_tot,n,m;
void init(){rep(i,0,n) head[i]=0;edge_tot=1;}
void addedge(int u,int v,int w=1){g[edge_tot]={v,w,head[u]};head[u]=edge_tot++;}
struct TP{
    ll a[maxn],cnt=0;
    ll dep[maxn],fa[maxn],son[maxn],siz[maxn],top[maxn],dfn[maxn],rk[maxn];
    struct node{ll l,r,w,siz,lz;}tr[maxn<<2];
    void init(){
        cnt=0;
        for(int i=0;i<=n;++i) dep[i]=siz[i]=son[i]=0;
    }
    void dfs1(int u,int Fa,int Dep){
        dep[u]=Dep;fa[u]=Fa;siz[u]=1;son[u]=0;
        int tmp=-1; 
        for(int i=head[u],v;i;i=g[i].nxt){
            if((v=g[i].v)==Fa) continue;
            dfs1(v,u,Dep+1); siz[u]+=siz[v];
            if(siz[v]>tmp) tmp=siz[v],son[u]=v;
         }
    }
    void dfs2(int u,int v){
        top[u]=v;dfn[u]=++cnt;rk[cnt]=u;
        if(!son[u]) return;
        dfs2(son[u],v);
        for(int i=head[u],v;i;i=g[i].nxt)
            if((v=g[i].v)!=son[u]&&v!=fa[u]) dfs2(v,v);
    }

    void push_up(int rt){
        tr[rt].w=tr[lson].w+tr[rson].w;
    }
    void build(int rt,int l,int r){
        tr[rt].l=l;tr[rt].r=r;tr[rt].siz=r-l+1;tr[rt].w=tr[rt].lz=0;
        if(l==r){
            tr[rt].w=tr[rt].lz=0;
            return;
        }int mid=(l+r)>>1;
        build(lson,l,mid);build(rson,mid+1,r);push_up(rt);
    }
    void push_down(int rt){
        if(tr[rt].lz==0) return;
        tr[lson].w=tr[lson].w+tr[lson].siz*tr[rt].lz;
        tr[rson].w=tr[rson].w+tr[rson].siz*tr[rt].lz;
        tr[lson].lz=tr[lson].lz+tr[rt].lz;
        tr[rson].lz=tr[rson].lz+tr[rt].lz;
        tr[rt].lz=0;
    }
    void Interadd(int rt,int l,int r,int val){
        //线段树区间加
        //x为根的子树加y:Interadd(1,tp.dfn[x],tp.dfn[x]+tp.siz[x]-1,y);
        if(l<=tr[rt].l&&tr[rt].r<=r){
            tr[rt].w+=tr[rt].siz*val;
            tr[rt].lz+=val;
            return;
        } push_down(rt);
        int mid=(tr[rt].l+tr[rt].r)>>1;
        if(l<=mid) Interadd(lson,l,r,val);
        if(r>mid) Interadd(rson,l,r,val);
        push_up(rt);
    }
    ll Insum(int rt,int l,int r){
        //查询线段树区间和
        //查询x为根的子树:Insum(1,tp.dfn[x],tp.dfn[x]+tp.siz[x]-1);
        ll ans=0;
        if(l<=tr[rt].l&&tr[rt].r<=r) return tr[rt].w;
        push_down(rt);
        int mid=(tr[rt].l+tr[rt].r)>>1;
        if(l<=mid) ans=ans+Insum(lson,l,r);
        if(r>mid) ans=ans+Insum(rson,l,r);
        return ans;
    }
    void treeadd(int x,int y,int val){
        //x到y的路径加val:treeadd(x,y,z);
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            Interadd(1,dfn[top[x]],dfn[x],val);x=fa[top[x]];
        }
        if(dep[x]>dep[y]) swap(x,y);
        Interadd(1,dfn[x],dfn[y],val);
    }
    ll querysum(int x,int y){
        //查询x到y的路径权值和:querysum(x,y);
        ll ans=0;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            ans=ans+Insum(1,dfn[top[x]],dfn[x]);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y]) swap(x,y);
        ans=ans+Insum(1,dfn[x],dfn[y]);
        return ans;
    }
    //tp.init();tp.dfs1(root,0,1);tp.dfs2(root,root);tp.build(1,1,n);
}tp;
ll w[maxn],num,now;
void solve(){
    scanf("%d%d",&n,&m);
    init();tp.init();
    rep(i,1,n) w[i]=num=now=0;
    rep(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        addedge(u,v);addedge(v,u);
    }tp.dfs1(1,0,0);tp.dfs2(1,1);tp.build(1,1,n);
    while(m--){
        int op,x;scanf("%d%d",&op,&x);
        if(op==1){
            ll w;scanf("%lld",&w);
            num--;now+=w-tp.dep[x]-2;
            tp.treeadd(1,x,2);
        }else{
            ll ans=now+w[x]+1ll*tp.dep[x]*num;
            ans+=tp.querysum(1,x);
            if(op==3) printf("%lld\n",ans);
            else if(op==2&&ans>0) w[x]-=ans;
        }
    }
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

D.Fake News

zyj (00:05:35) +0

题意

$\sum\limits_{k=1}^n k^2$是不是完全平方数。

题解

打表可知除了$n=1$或$n=24$之外其他所有数都不满足。
具体可见知乎证明
以下是简要证明:

按$n$的奇偶性讨论。当$n$是偶数时,运用勾股方程、无穷递降等一系列的理论,这种情况是较为简单的;当$n$是奇数时,运用$Pell$方程、二次剩余等一系列的理论,这种情况是较为困难的。以下是完整过程:

原问题等价于求$n(n+1)(2 n+1)=6 k^{2}$的正整数解, 下面按$n$的奇偶性进行讨论。

情形一,$n=2m$为偶数时,原问题即为求$m(2 m+1)(4 m+1)=3 k^{2}$的正整数解。 简单分析知$(m, 2 m+1,4 m+1)$只能形如$\left(3 a^{2}, b^{2}, c^{2}\right)$, 其中$a, b, c \in \mathbb{N}$。 可设$c=2 d+1$, 则$4 m+1=4 d^{2}+4 d+1 \Rightarrow 3 a^{2}=m=d(d+1), b^{2}=2 m+1=d^{2}+(d+1)^{2}$。 利用勾股方程的结论,可设$b^{2}=r^{2}+s^{2}$, 并分两种情况讨论:

  • (1)$d=2 r s, d+1=r^{2}-s^{2}$, 相减可得$(r-s)^{2}-2 s^{2}=1$。 再利用$3 a^{2}=d(d+1)$并简单分析可知$(r+s)(r-s)=d+1$为完全平方数,因此$r-s=t^{2}$是完全平方数。方程就化为了$t^{4}-2 s^{2}=1$。由熟知结论,无解。(注:该结论将于最后证明)
  • (2)$d=r^{2}-s^{2}, d+1=2 r s$, 相减可得$(r+s)^{2}-2 r^{2}=1$。 再由$d+1$为完全平方数可知$r=t^{2}$或$2 t^{2}$。 于是原方程化为了$(r+s)^{2}-2 t^{4}=1 \text { 和 }(r+s)^{2}-8 t^{4}=1$。 由此可以推出$r=2, s=1, d=3, m=12, n=24$, 得到了第一个解。

情形二,$n=2 m+1$为奇数时,原问题即为求$(m+1)(2 m+1)(4 m+3)=3 k^{2}$的正整数解。 简单分析知,$(m+1,2 m+1,4 m+3)$只能形如$\left(a^{2}, b^{2}, 3 c^{2}\right)$, 其中$a, b, c \subseteq \mathbb{N}$。 则有$\left(4 b^{2}+3\right)^{2}-3(4 a c)^{2}=\left(6 a^{2}+1\right)^{2}-48 a^{2} c^{2}=12 c^{2}\left(3 c^{2}+1-4 a^{2}\right)+1=1$。 下证:$Pell$方程$X^{2}-3 Y^{2}=1$在$X$可表示为$4 t^{2}+3$的形式时,只有一组解$(7,4)$。

记$\alpha=2+\sqrt{3}, \beta=2-\sqrt{3}$, 且设$x_{n}=\frac{\alpha^{n}+\beta^{n}}{2}, y_{n}=\frac{\alpha^{n}-\beta^{n}}{2 \sqrt{3}}$, 则$\left(x_{n}, y_{n}\right)$是上述Pell方程的第$n$组解。 若$x_{n}=4 t^{2}+3$, 考查数列$\left\{x_{n}\right\}$模4的余数可知$n \equiv 2 \quad(\bmod 4)$。 因此,当$n>2$时,$n$一定可以表示为$2^{s} q \pm 2$, 其中$s \geq 3$且$q$是奇数。 则由$Pell$方程解的递推性质可知:$x_{n}=x_{2}^{s} q \pm 2=x_{2^{s}} q^{x_{2}} \pm 3 y_{2^{s}} q^{y_{2}}$。 再结合$Pell$的递推性质,$x_{2^{s-1}}\left|x_{2^{s-1} q}, x_{2^{s-1}}\right| y_{2^{s} q}$,进而$x_{2^{s} q}=2 x_{2^{s-1} q}^{2}-1 \equiv-1 \quad\left(\bmod x_{2^{s-1}}\right)$。 因此,$4 t^{2}=x_{n}-3 \equiv\left(-x_{2}+0\right)-3 \equiv-10 \quad\left(\bmod x_{2^{s-1}}\right)$。

下面引入Jacobi符号。为了方便书写,记$2^{s-1}=r$。 结合由递推公式给出的$x_{r}$模8和5的余数,$\left(\frac{-2}{x_{r}}\right)=(-1)^{\frac{x_{r}-1}{2}} \cdot(-1)^{\frac{\mu_{r}^{2}-1}{8}}=1,\left(\frac{5}{x_{r}}\right)=\left(\frac{x_{r}}{5}\right) \cdot(-1)^{\frac{5-1}{2} \cdot \frac{x_{r}-1}{2}}=-1$。 因此$-1=\left(\frac{-2}{x_{r}}\right) \cdot\left(\frac{5}{x_{r}}\right)=\left(\frac{-10}{x_{r}}\right)=\left(\frac{4 t^{2}}{x_{r}}\right)=1$, 矛盾!
因此$4 b^{2}+3=7, b=1, m=0, n=1$, 我们便得到了第二个解。

综上,原方程的解只有1或24。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n;
void solve(){
    scanf("%d",&n);
    if(n==1||n==24) puts("Fake news!");
    else puts("Nobody knows it better than me!");
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

E.NeoMole Synthes

题意

题解

代码


F.Tokens on the Tree

题意

题解

代码


G.Topo Counting

zyj (赛后) +1

题意

给出一张烤肉图。参数只由点数控制,问你拓扑序的种数。

题解

构造出的图形如这样:
F7C43BADE20AFB49DFD4C09A4C4BDD3D.jpg
首先我们需要知道一个引理:

如果一个 $DAG$ 是由两个完全不相关的子图组合而成的, 不妨设这两个子图的大小分别是 $S_1$和 $S_2$, 对应拓扑序列个数为 $P_1$ 和 $P_2$, 那么这个 $DAG$ 的拓扑序列个数为$\left(\begin{array}{c} S_{1}+S_{2} \\ S_{1}\end{array}\right) P_{1} P_{2}$

我们可以发现每个肉片只受制于架子上的两个节点, 当对应的两个节点被删除之后, 肉片就会与整个 $DAG$ 分离. 由于肉片作为一个子图的拓扑序列是非常容易计算的,所以本题做法的核心就是只维护架子以及连在架子上的肉片的形态.

我们可以发现, 在删除节点的过程中, 架子和与架子相连的肉片的整体形态, 只有大致三种情况:

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e3+100;
const int N=(int)2e7+100;
int n,mod;
ll qpow(ll x,int n){
    ll res=1;
    while(n){
        if(n&1) res=(res*x)%mod;
        x=(x*x)%mod;n>>=1;
    } return res;
}
int fac[N+10],inv[N+10];
void init(){
    fac[0]=1;
    rep(i,1,N-1) fac[i]=1ll*fac[i-1]*i%mod;
    inv[N-1]=qpow(fac[N-1],mod-2);
    dep(i,N-2,0) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int C(int a,int b){
    if(a<b) return 0;
    return 1ll*fac[a]*inv[a-b]%mod*inv[b]%mod;
}
int h[maxn],f[maxn][maxn],g[maxn][maxn],c[maxn][maxn];
int main(){
    scanf("%d%d",&n,&mod);init();
    //对于单个肉片,左边i个点,右边j个点的序列数
    rep(i,0,n) rep(j,i,n) c[i][j]=i?(c[i-1][j]+(j>i?c[i][j-1]:0))%mod:1;
    //枚举第一行点数,最终答案即为h[n-1]
    rep(i,0,n-1){
        if(i) rep(j,0,n){
            g[i][j]=j?g[i][j-1]:0;
            int num=2*i-1+(i-1)*2*n;//肉片点数
            g[i][j]=(g[i][j]+1ll*c[j][n]*h[i-1]%mod*C(num+j+n,num)%mod)%mod;
        }
        h[i]=i?((f[i-1][i+1]+g[i][n])%mod):1;
        rep(j,i+2,n){
            if(i) f[i][j]=f[i-1][j];
            int num=i+j-1+(j-2)*2*n;
            f[i][j]=(f[i][j]+1ll*c[n][n]*(j==i+2?h[i]:f[i][j-1])%mod*C(num+n*2,num)%mod)%mod;
        }
    }printf("%d\n",h[n-1]%mod);
}

H.Dividing

lmj (01:00:51) +0

题意

$(1,k)$算答案,如果$(n,k)$算入答案,那么$(n+k,k)$和$(n*k,k)$也算入答案,求n从1-N,k从1-K的答案总数

题解

显然可以发现就是求$n mod k==0||1$的数量和。可以发现就是$\sum_{i=1}^n[n/i]$的向下取整和向上取整相加。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
void work()
{
    ll n,k;
    scanf("%lld%lld",&n,&k);
    ll N=n;
    ll ans=0;
    for(ll i=1,j;i<=min(N,k);i=j+1){
        j=N/(N/i);
        j=min({N,k,j});
        ans+=(j-i+1)*(N/i);
        ans%=p;
    }
    //printf("%lld\n",ans);
    for(ll i=2,j;i<=min(n,k);i=j+1){
        ll tmp=(n+i-1)/i;
        if(tmp==1){
            j=min(n,k);
        }else{
            j=(n-1)/(tmp-1);
            j=min({j,n,k});
        }
        ans+=(j-i+1)*((n+i-1)/i);
    }
    ans+=max(k-n,0ll);
    printf("%lld\n",ans%p);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

I.Valuable Forests

wrf (赛后)

题意

求 n 个点能形成的所有带标号森林点权平方和的和。

题解

做法:

首先考虑 n 个点能形成的带标号树的点权平方和,记为 $T(n)$。
每一棵树都能用如下方法生成:首先规定一个点为根,然后选择若干个点作为第一级儿子,再将其他点连向这个连通块除根之外的部分:

所以有:

$$ T(n)=n\sum_{k=0}^{n-2}k^3(n-1)^{n-k-2}\dbinom{n-1}{k} $$

然后考虑 n 个点形成的带标号森林个数,记为 $fo(n)$。#cayley-cayleys-formula),这一部分的答案为 $n^{n-2}$。
考虑 dp,每次将新增的点加入一棵树。枚举这棵树可能有 $k$ 个节点,显然有 $1 \leq k < n$(不是从 $0$ 开始,因为已经包含新增节点了)。而其他部分则已被计算过。
所以有

$$ fo(n)=fo(n-1)+\sum_{k=1}^{n-1}\dbinom{n-1}{k-1}k^{k-2}fo(n-k)) $$

再考虑最终答案,记为 $dp(n)$
同样每次考虑将新增节点加入一棵树,那么总贡献就等于该树的贡献*剩余点形成的森林个数+树的个数*剩余点的贡献.
由此同样可以列出转移方程如下:

$$ dp(n)=T(n)+\sum_{k=1}^{n-1}\dbinom{n-1}{k-1}(T(k)fo(i-k)+k^{k-2}dp(i-j)) $$

进行适当的预处理后转移即可。

时间复杂度

$O(n^2)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=5020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int c[N][N],p[N][N];
int qp[N],t[N],dp[N],fo[N];

int main(void)
{
    int _=read();
    int mod=read();

    for(int i=0;i<N;i++)
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++) c[i][j]=1ll*(c[i-1][j-1]+c[i-1][j])%mod;
    }
    for(int i=0;i<N;i++)
    {
        p[i][0]=1;
        for(int j=1;j<N;j++)
        {
            p[i][j]=1ll*p[i][j-1]*i%mod;
        }
    }
    t[0]=0,t[1]=0,t[2]=2;
    for(int i=3;i<N;i++)
    {
        for(int j=1;j<=i-2;j++)
        {
            t[i]=(t[i]+1ll*j*j*j%mod*p[i-1][i-j-2]%mod*c[i-1][j]%mod)%mod;
        }
        t[i]=1ll*(t[i]+(i-1)*(i-1))*i%mod;
    }
    fo[0]=1,fo[1]=1;
    for(int i=2;i<N;i++)
    {
        fo[i]=p[i][i-2];
        for(int j=1;j<i;j++)
        {
            fo[i]=(fo[i]+1ll*c[i-1][j-1]*(j>=2?p[j][j-2]:1)%mod*fo[i-j]%mod)%mod;
        }
    }
    for(int i=2;i<N;i++)
    {
        dp[i]=t[i];
        for(int j=1;j<i;j++)
        {
            dp[i]=(dp[i]+1ll*c[i-1][j-1]*t[j]%mod*fo[i-j]%mod)%mod;
            dp[i]=(dp[i]+1ll*c[i-1][j-1]*(j>=2?p[j][j-2]:1)%mod*dp[i-j]%mod)%mod;
        }
    }

    for(;_>0;_--)
    {
        printf("%lld\n",dp[read()]);
    }
    
    return 0;
}

J.Pointer Analysis

lmj (赛后) +1e5

题意

咕噜咕噜咕噜

题解

阿巴阿巴阿巴

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[205],b[205],c[205],d[205];
set<char>s[27];
set<char>s1[27][27];
void work()
{
    int n;
    scanf("%d",&n);
    getchar();
    for(int i=0;i<26;i++){
        s1[i][26].insert(i+'a');
    }
    for(int i=1;i<=n;i++){
        char x=getchar();
        a[i]=x-'A';
        b[i]=26;
        x=getchar();
        if(x=='.'){
            x=getchar();
            b[i]=x-'a';
            getchar();
        }
        getchar();
        getchar();
        x=getchar();
        c[i]=x-'A';
        d[i]=26;
        char y;
        y=getchar();
        if(y!='\n'){
            y=getchar();
            getchar();
            d[i]=y-'a';
        }
        if(c[i]>=32){
            int tmp=c[i]+'A';
            s[a[i]].insert(tmp);
        }
    }
    for(int t=1;t<=n;t++){
        for(int i=1;i<=n;i++){
            if(c[i]>=32)continue;
            if(b[i]==26){
                for(auto x:s[c[i]]){
                    for(auto y:s1[x-'a'][d[i]]){
                        s[a[i]].insert(y);
                    }
                }
            }else{
                for(auto x:s[c[i]]){
                    for(auto y:s[a[i]]){
                        for(auto z:s1[x-'a'][d[i]]){
                            s1[y-'a'][b[i]].insert(z);
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<26;i++){
        printf("%c: ",'A'+i);
        for(auto x:s[i]){
            printf("%c",x);
        }
        printf("\n");
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}
Responses