2020杭电多校联合训练(第五场)
in 杭电多校多校训练 with 0 comment

2020杭电多校联合训练(第五场)

in 杭电多校多校训练 with 0 comment

摘要

/ABCDEFGHIJKLM
场上
zyj
wrf
lmj

题目

A.Tetrahedron

wrf+zyj (01:36:44) +0

题意

从 [1,n] 里重复地选出三个数作为直三棱锥的三边长,求斜面上高的平方倒数的期望。

题解

做法

$$ Ans=\sum_{i=1}^n \frac{1}{i^2} \cdot \frac{3}{n} $$

证明

$$ \begin{aligned} V&=\frac{abc}{3} \\ \\ S&=\frac{1}{2} \left |\begin{array}{cccc} 1 &1 & 1 \\ a &-b& 0 \\ 0 & b &-c \\ \end{array}\right| \\ &={ab+ac+bc \over 2} \\ \\ \frac{1}{h^2}&=(\frac{2S}{3V})^2 \\ &={3(ab+ac+bc) \over 2abc} \\ &=\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2} \\ \\ E(\frac{1}{h^2})&=\sum_{i=1}^n \frac{1}{i^2} \cdot \frac{3}{n} \end{aligned} $$

时间复杂度

$O(n)$

推广

对于 $n$ 维情况:
令每个坐标轴上选取的截距分别为$[w_1,w_2,...w_n]$,则斜面可以被表示为:

$$ F(\vec{x}):1=\sum_{i=1}^{n} \frac{x_i}{w_i} $$

显然斜面法向量 $\vec{w}=[\frac{1}{w_1},\frac{1}{w_2},...,\frac{1}{w_n}]$
记原点在斜面上的投影到原点本身的向量为 $\vec{h}$,显然 $\vec{w}$ 与 $\vec{h}$ 平行,那么有:

$$ 1=\sum_{i=1}^{n} \frac{h_i}{w_i}=\vec{w}\cdot\vec{h}=||\vec{w}||\cdot||\vec{h}||=\sqrt{\sum_{i=1}^{n} {1 \over {w_i^2}}}\cdot d $$

所求的高就可以被表示为:

$$ \frac{1}{d^2}=\sum_{i=1}^{n} {1 \over {w_i^2}} $$

代码

#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=6000020;

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;
}

ll v[N];
ll tv[N];

int main(void)
{
    
    v[0]=0;
    v[1]=1;
    for(ll i=2;i<N;i++)
    {
        v[i]=(mod-mod/i)*v[mod%i]%mod;
    }
    for(int i=1;i<N;i++) tv[i]=(v[i]*v[i]%mod+tv[i-1])%mod;
    for(int _=read();_>0;_--)
    {
        int n=read();
        printf("%lld\n",tv[n]*v[n]%mod*3%mod);
    }
}

B.Funny String

题意

题解

代码


C.Boring Game

wrf (02:50:05) +1

题意

将 n 张纸重叠,一起向右折叠 k 次,将每层从上到下标号。
最后将这张纸展开,从左到右分别读出每张纸的符号。
image

题解

做法

大模拟。
对每一层建立一个链表,存放当前层上的标号。
每次合并时分别取对称的两个链表,反向标号较小的那个,接到标号较大的前面。
然后收集所有标号在后一半的所有链表。
重复上述 k 次,最后会剩下 2n 个链表,按顺序输出即可。

证明

考虑展开一张纸的过程。
纸的上半部分会被反向,所以反向标号最小的那个。
纸的下半部分没有动,所以只收集标号在后一半的。

时间复杂度

$O(kn \cdot 2^k)$
通过一些奇技淫巧(比如给交换打上 lazy 标记)可以实现单次合并 $O(1)$,此时时间复杂度为 $O(n \cdot 2^k)$。

代码

#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;
}

ll qpow(ll a,ll b,ll m)
{
    ll ans=1;
    while(b>0)
    {
        if(b&1)
        {
            ans=ans*a%m;
        }
        a=a*a%m;
        b>>=1; 
    } 
    return ans;
}

int main(void)
{
    
    for(int _=read();_>0;_--)
    {
        int n=read(),k=read();
        int s=2*n*qpow(2,k,mod);
        vector<list<int> > v(s);
        for(int i=0;i<s;i++) v[i].push_back(read());


        int ns=s;
        for(int __=0;__<k;__++)
        {
            vector<list<int> > tv(ns/2);
            for(int i=ns/2-1;i>=0;i--)
            {
                for(auto j:v[ns-i-1]) tv[ns/2-i-1].push_back(j);
                for(auto j:v[i]) tv[ns/2-i-1].push_front(j);
            }
            for(int i=0;i<ns/2;i++) v[i].assign(tv[i].begin(),tv[i].end());
            ns/=2;
        }
        bool qq=false;

        for(int i=0;i<ns;i++)
        {
            for(auto j:v[i]) 
            {
                if(qq) printf(" ");
                printf("%d",j);
                qq=true;
            }
        }
        printf("\n");
    }
    
    return 0;
}

D.Expression

题意

题解

代码


E.Array Repairing

题意

题解

代码


F.Alice and Bob

题意

题解

代码


G.Tree

lmj (赛后)

题意

给一棵树,求一个子图,使得子图中只有一个点的度数是大于k的,求边权总和的最大值

题解

换根dp动态维护第k大和第k-1大维护到死,还是用标程做法吧。
$dp[x][0]$代表x为根节点,所有节点的度数都小于k的最大边权和
$dp[x][1]$代表x为根节点,有一个节点的度数大于等于k,其他节点度数小于k的最大边权和。
转移方式:$dp[x][0]$就是儿子中前k-1大的和加边权。
$dp[x][1]$需要分两种情况,x作为度数大于等于k的点,那么就是所有儿子的$dp[i][0]$的和加边权。
x的儿子作为度数大于等于k的点。因为要继续往上转移,所以x的度数要小于等于k-2,那么如果选的那个点在前k-1大,那么就是前k-1大的$dp[i][0]$再加上对应点的$dp[i][1]$减掉对应点的$dp[i][0]$,如果选的那个点不在前k-1大,那么就是前k-2个的$dp[i][0]$再加上对应点的$dp[i][0]$。
需要额外考虑不往上转移的情况,即x的儿子作为度数大于等于k的点,此时x的度数取到k-1,计入答案。其他的就是各个点的$dp[i][1]$

代码

#pragma comment(linker, "/STACK:102400000,102400000") 
#include <bits/stdc++.h>
using namespace std;
#define paii pair<ll,ll>
#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 n,k;
ll pre[N];
ll pre1[N];
vector<paii>v[N];
ll dp[N][2];
paii q[N];
ll ans=0;
bool cmp(paii x,paii y)
{
    if(x.fr!=y.fr)return x.fr>y.fr;
    else return x.sc>y.sc;
}
ll cal(int cnt,int n)
{
    if(n<=0)return 0;
    ll tmp=0;
    for(int i=1;i<=min(cnt,n);i++){
        tmp+=q[i].fr;
    }
    if(cnt<=n)return tmp+pre[cnt];
    return  max(tmp+pre[n],tmp-q[n].fr+pre1[n+1]);
}
void dfs(int x,int past)
{
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].fr==past)continue;
        dfs(v[x][i].fr,x);
    }
    int cnt=0;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].fr==past)continue;
        q[++cnt]={dp[v[x][i].fr][0]+v[x][i].sc,dp[v[x][i].fr][1]+v[x][i].sc};
    }
    sort(q+1,q+cnt+1,cmp);
    ll tmp=0;
    for(int i=1;i<=min(k-1,cnt);i++){
        tmp+=q[i].fr;
    }
    dp[x][0]=tmp;
    for(int i=min(k-1,cnt)+1;i<=cnt;i++){
        tmp+=q[i].fr;
    }
    dp[x][1]=tmp;
    for(int i=1;i<=cnt;i++){
        pre[i]=max(pre[i-1],q[i].sc-q[i].fr);
    }
    pre1[cnt+1]=0;
    for(int i=cnt;i>=1;i--){
        pre1[i]=max(pre1[i+1],q[i].sc);
    }
    dp[x][1]=max(dp[x][1],cal(cnt,k-1));
    ans=max(ans,cal(cnt,k));
    ans=max(ans,dp[x][1]);
}
void work()
{
    ans=0;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        dp[i][0]=dp[i][1]=0;
        v[i].clear();
    }
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    if(k==0){
        printf("0\n");return;
    }
    dfs(1,0);
    printf("%lld\n",ans);
}
int main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

H.Set2

lmj 赛后

题意

给定1到n,每次删除最小的一个数,并且依次删除随机k个数,直到剩下的数少于k个,求每个数被留下来的概率

题解

考虑dp,$dp[i][j]$代表第$i$次操作后还需要随机删除$j$个数,转移方式为,做一次删除最小的数,$dp[i+1][j+k]+=dp[i][j]$,做一次删任意数,$dp[i+1][j-1]+=dp[i][j]$
然后考虑最后剩下的$n\%k$个数,设$f[i]$代表当前剩下的数中最小的为i,$j=n-i+1-(n\%k)$,$f[i]=dp[i-1][j]*j!*C_{n-i}^j$,$cnt[i]$代表最小元素为i时,元素$x>i$被留下来的概率,$cnt[i]=dp[i-1][j]*j!*C_{n-i-1}^j$
总方案数为$\sum_{i=1}^ncnt[i]$,每个数留下的方案数为$\sum_{j=1}^{i-1}cnt[j]+f[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=998244353;
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;}
ll dp[5005][5005];
ll f[5005];
ll cnt[5005];
ll ans[5005];
ll pre[5005];
ll inv[5005];
ll C(int n,int m)
{
    if(n<m)return 0;
    return pre[n]*inv[m]%p*inv[n-m]%p;
}
void work()
{
    int n,k;
    scanf("%d%d",&n,&k);
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    int r=n%(k+1);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j+k<=n-i-1){
                dp[i+1][j+k]=(dp[i+1][j+k]+dp[i][j])%p;
            }
            if(j){
                dp[i+1][j-1]=(dp[i+1][j-1]+dp[i][j]*j)%p;
            }
        }
    }
    for(int i=1;i<=n;i++){
        int j=n-i+1-r;
        //printf("%d %d\n",i,j);
        f[i]=dp[i-1][j]*pre[j]%p*C(n-i,j)%p;
        //printf("%lld %lld %lld\n",dp[i-1][j],pre[j],C(n-1,j));
        cnt[i]=dp[i-1][j]*pre[j]%p*C(n-i-1,j)%p;      
    }
    // for(int i=1;i<=n;i++){
    //     printf("%lld %lld\n",f[i],cnt[i]);
    // }
    ll tmp=0;   
    ll sum=0;
    for(int i=1;i<=n;i++){
        ans[i]=(f[i]+tmp)%p;
        tmp=(tmp+cnt[i])%p;
        sum=(sum+f[i])%p;
    }
    sum=qpow(sum,p-2);
    for(int i=1;i<=n;i++){
        printf("%lld%c",ans[i]*sum%p,i<n?' ':'\n');
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    pre[0]=1;
    for(int i=1;i<=5000;i++){
        pre[i]=pre[i-1]*i%p;
    }
    inv[5000]=qpow(pre[5000],p-2);
    for(int i=4999;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%p;
    }
    //cin>>T;
    while(T--){
        work();
    }
}

I.Paperfolding

wrf (12:31:39) +0

题意

将一张纸对折 n 次,每次等概率地可能横着或竖着对折。折完后在中央横竖各剪一刀,求最终得到的块的个数期望。

题解

做法

$$ Ans=2^n+2\cdot(\frac{3}{2})^n+1 $$

证明

首先最终得到的块的个数=(横向被分割的次数+1)*(纵向被分割的次数+1)
而每次折叠,都会使得这个方向上存在的段加倍,每一段都会被分割一次。

假设横着对折 $k$ 次,那么答案自然等于 $(2^k+1)(2^{n-k}+1)$。
则所求为:

$$ \begin{aligned} 2^nE(x)&=\sum_{k=0}^n \dbinom{n}{k} (2^k+1)(2^{n-k}+1) \\ &=\sum_{k=0}^n \dbinom{n}{k} (2^n+2^k+2^{n-k}+1) \\ &=(2^n+1)\sum_{k=0}^n \dbinom{n}{k}+2\sum_{k=0}^n \dbinom{n}{k}(2^k \cdot 1^k) \\ &=(2^n+1)2^n+2(2+1)^n \\ \\ E(x)&=2^n+2\cdot(\frac{3}{2})^n+1 \end{aligned} $$

时间复杂度

$O(n \log n)$

代码

#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;
}

ll qpow(ll a,ll b,ll m)
{
    ll ans=1;
    while(b>0)
    {
        if(b&1)
        {
            ans=ans*a%m;
        }
        a=a*a%m;
        b>>=1; 
    } 
    return ans;
}

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);

    const ll i32=499122178;
    
    for(int _=read();_>0;_--)
    {
        ll n=read();

        printf("%lld\n",(qpow(2,n,mod)+1+2*qpow(i32,n,mod))%mod);
    }
    
    return 0;
}

J.Function

题意

题解

代码


K.Exam

zyj (赛后) +1

题意

$n$门考试,每门考试有两个可选时间$[a_i,a_i+at_i],[b_i,b_i+bt_i]$,问在不冲突的情况下每门考试都考完的最少时间是多少,没有方案输出$−1$。$(n \leq 10^5)$

题解

每门考试要从两个时间段选一个,并且不能有冲突,这很像一道2-set的题目。
此处简单说一下2-set如何实现:2-set并不是NP完全的,因此可以通过tarjan或dfs的方式暴力求出,连有向边表示此关系必选,通过tarjan缩点后如果一对关系在同一个连通分量中则说明无解,否则dfs一次即可以得到方案。
但是2-set只能判断是否可行,并不能找到时间最小的方案,于是考虑二分答案,然后用2-set去$check$。

不妨令区间$[a_i,a_i+at_i]$为点$i$,区间$[b_i,b_i+bt_i]$为点$i'$,假设当前二分的结束时间为$mid$,则有:

很显然边数是$N^2$的,总的时间复杂度为$N^2 logN$无法通过此题,于是考虑优化建边。

说明:接下来的区间都将写成$[l_i,r_i]$而不是$[a,a+at]$的形式,请注意区分。

我们将所有的$2N$个区间按照结束时间排序后,不难发现对于一个区间$[l_i,r_i]$,和他有冲突的区间是一段连续区间。具体地,只需在$j \in [1,i-1]$中二分搜索第一个满足$r_j \geq l_i$的$j$,此时$[j,i-1]$即为和区间$i$有冲突的区间编号,不难想到可以用线段树优化建边(想不到真的有人出这么毒瘤的题)。

接下来重点讲一下线段树优化建图。
标志说明:接下来出现的$lson$为线段树当前节点的左儿子编号,$rson$同理。

首先我们建两颗线段树,令为$t_1$和$t_2$,其中$t_1$表示正边,$t_2$表示反边。

规定:一门考试有两个时间段,假设我们选出一个时间段$i$,则令未选出那个为$i'$。

通过前面的讲解我们知道:对于一个时间段$i$,会有一个区间$[j,i-1]$的时间段和其冲突,也就是说我们原本需要连边$for$ $k \in [j,i-1], add(i,k'),add(k,i')$。前面这条边$(i,k')$转为了将点$i$连向「线段树$t_2$对应区间$[j,i-1]$的节点」,同样对于边$(k,i')$,需要将「线段树$t_1$对应区间$[j,i-1]$的节点」连向点$i'$。
边的方向也就解释了我们上面说的两颗树内部的连边方向问题,同时不难发现对于每个时间区间,其所连边数是在$logN$级别的,此时边数为$N log N$,时间复杂度为$N log ^2 N$,可以通过此题。

代码

#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;
struct node{
    int l,r,id;
    bool operator<(const node &a)const{return r<a.r;}
}p[maxn];
int lson[maxn<<4],rson[maxn<<4],tot,rt,n;
vector<int> g[maxn<<1];
void add(int u,int v){g[u].pb(v);}
void del(int u){if(g[u].size()) g[u].pop_back();}
int id(int x,int op){return op?(op==1?n+x:n+tot+x):x;}
void build(int &rt,int l,int r){
    if(rt==-1) rt=tot++,lson[rt]=rson[rt]=-1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lson[rt],l,mid);build(rson[rt],mid+1,r);
}
void link(int rt,int l,int r){
    if(l==r){
        add(p[l].id,id(rt,1));add(id(rt,2),p[l].id^1);
        return;
    }int mid=(l+r)>>1;
    add(id(lson[rt],1),id(rt,1));add(id(rson[rt],1),id(rt,1));
    add(id(rt,2),id(lson[rt],2));add(id(rt,2),id(rson[rt],2));
    link(lson[rt],l,mid);link(rson[rt],mid+1,r);
}
void query(int ql,int qr,int v,int rt,int l,int r){
    if(ql>r||l>qr) return;
    if(ql<=l&&r<=qr){
        add(id(rt,1),v^1);add(v,id(rt,2));
        return;
    }int mid=(l+r)>>1;
    query(ql,qr,v,lson[rt],l,mid);query(ql,qr,v,rson[rt],mid+1,r);
}
struct TARJAN{
    int sz,dfn[maxn],low[maxn],vis[maxn],belong[maxn],scc;
    stack<int> sta;
    void init(int n){
        rep(i,0,n) vis[i]=0,dfn[i]=0;
        while(!sta.empty()) sta.pop();
        scc=sz=0;
    }
    void tarjan(int u){
        dfn[u]=low[u]=++sz; vis[u]=1; sta.push(u);
        for(auto v:g[u]){
            if(!dfn[v]){
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }else if(vis[v]&&low[u]>dfn[v]) low[u]=dfn[v];
        }
        if(low[u]==dfn[u]){scc++;
            while(1){
                int id=sta.top(); sta.pop();
                vis[id]=0;belong[id]=scc;
                if(id==u) break;
            }
        }
    }
}ta;
int search(int r,int x){
    int l=0;
    while(l<r){
        int mid=(l+r)>>1;
        if(p[mid].r>=x) r=mid;
        else l=mid+1;
    }return r;
}
bool check(int mid){
    rep(i,0,n-1) if(p[i].r>p[mid].r) add(p[i].id,p[i].id^1);
    ta.init(n+tot*2-1);
    rep(i,0,n+tot*2-1) if(!ta.dfn[i]) ta.tarjan(i);
    rep(i,0,n-1) if(p[i].r>p[mid].r) del(p[i].id);
    for(int i=0;i<n;i+=2) if(ta.belong[i]==ta.belong[i+1]) return 0;
    return 1;
}
void solve(){
    scanf("%d",&n);n<<=1;
    tot=0;rt=-1;
    rep(i,0,n-1){
        scanf("%d%d",&p[i].l,&p[i].r);
        p[i].r+=p[i].l;p[i].id=i;
    }sort(p,p+n);build(rt,0,n-1);
    rep(i,0,n+tot*2-1) g[i].clear();
    link(rt,0,n-1);
    rep(i,0,n-1){
        int pos=search(i,p[i].l);
        if(pos<i) query(pos,i-1,p[i].id,rt,0,n-1);
    }
    int l=0,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }printf("%d\n",r>=n?-1:p[r].r);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

L.Set1

lmj (00:57:36) +3

题意

n个数每次删除最小的数并且随机删一个其他数,直到只剩下1个数,求每个数留下来的概率。

题解

打表找规律即可
对于第$i$个数,他后面的$n-i$个数一定是被随机删掉,那么就是在前$i-1$个数里面选$n-i$个将后面数删掉,然后后面$n-i$个数是可以任意顺序选择,所以为$C_{i-1}^{n-i}*A_{n-i}^{n-i}$。
然后对于剩下的$i-1-(n-i)$个数,两两配对即可,$C_{i-1-(n-i)}^2*C_{i-1-(n-i)-2}^2*……$,因为这样会得到$(i-1-(n-i))/2$对2个的数,所以要除掉$A_{(i-1-(n-i))/2}^{(i-1-(n-i))/2}$ 去重。
$$cnt[i]=C_{i-1}^{n-i}*A_{n-i}^{n-i}*\frac{(2*i-n-1)!}{2^{(2*i-n-1)}*((2*i-n-1)/2)!}$$

代码

#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=5e6+5;
const int p=998244353;
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;}
ll pre[N];
ll pre1[N];
ll inv[N];
void work()
{
    int n;
    scanf("%d",&n);
    if(n==1){
        printf("1\n");return;
    }
    ll sum=pre[n-1]*qpow(pre1[n-1],p-2)%p;
    sum=qpow(sum,p-2);
    for(int i=1;i<=n/2;i++){
        printf("%d ",0);
    }
    int now=0;
    for(int i=1;i<=n/2;i++){
        printf("%lld ",pre1[now]*inv[now]%p*pre[n/2+now/2]%p*sum%p);
        now+=2;
    }
    now-=2;
    printf("%lld\n",pre1[now]*inv[now]%p*pre[n/2+now/2]%p*sum%p);
}
int main()
{
    //freopen("1.out","w",stdout);
    int T=1;
    pre[0]=1;
    for(int i=1;i<N;i++){
        pre[i]=pre[i-1]*i%p;
    }
    inv[N-1]=qpow(pre[N-1],p-2);
    for(int i=N-2;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%p;
    }
    pre1[0]=1;
    for(int i=1;i<N;i++){
        pre1[i]=pre1[i-1];
        if(i&1){
            pre1[i]=pre1[i]*i%p;
        }
    }
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

M.An Easy Matrix Problem

题意

题解

代码

Responses