「NOI.AC」NOI挑战赛第三场

Author： RainAir
发布时间：July 18, 2020
1078views
No comments
968 words
Categories：题解

A. T1

先观察一个性质：对于两个区间 $[l_i,r_i],[l_j,r_j]$，如果有 $l_i \leq l_j < r_j \leq r_i$，那么在最终的方案中不可能出现 $i$ 区间和 $j$ 区间不在一组，却和其他区间在一组的情况（可以把 $i$ 移动到 $j$ 所在的组，那么 $i$ 组答案不变劣，$j$ 组答案不变）

于是我们考虑将区间分成两个集合：$A$ 集合内的区间不包含任意一个区间，$B$ 集合的区间至少包含了一个其他的区间。

发现 $A$ 集合如果按照左端点排好序，右端点一定是有序的（只有相交和相离两种关系）。

所以考虑对 $A$ 集合排序后搞个 dp：$f[i][j]$ 考虑前 $i$ 个线段分成 $j$ 组的最大收益，转移的时候枚举最后的一段划组就行了（因为跨越选在无重叠关系的情况下不优）

然后 $B$ 集合的区间只有两个去处：

和它包含的区间分成一组，对答案无贡献
自成一组，对答案贡献长度。

于是枚举一下多少个 $B$ 集合的线段自称一组，贪心选择大的计算答案即可。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;

int n,m;
P c[MAXN];
std::vector<P> a,b;
int f[MAXN][MAXN];
int sm[MAXN];
bool used[MAXN];

inline bool cmp(P x,P y){
    return x.se-x.fi > y.se-y.fi;
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d%d",&c[i].fi,&c[i].se);
    FOR(i,1,n){
        bool flag = 1;
        FOR(j,1,n) if(i != j && c[i].fi <= c[j].fi && c[j].se <= c[i].se && !used[j]) {flag = 0;break;}
        if(flag) a.pb(c[i]);
        else b.pb(c[i]),used[i] = 1;
    }
    std::sort(all(a));std::sort(all(b),cmp);
    CLR(f,-0x3f);f[0][0] = 0;
    FOR(i,1,(int)a.size()){
        FOR(j,1,std::min(i,m)){
            FOR(k,1,i){
                if(a[k-1].se <= a[i-1].fi) continue;
                f[i][j] = std::max(f[i][j],f[k-1][j-1]+a[k-1].se-a[i-1].fi);
            }
        }
    }
    int ans = 0;
    FOR(i,1,(int)b.size()) sm[i] = sm[i-1]+(b[i-1].se-b[i-1].fi);
    FOR(i,0,m) ans = std::max(ans,f[(int)a.size()][i]+sm[m-i]);
    printf("%d\n",ans);
    return 0;
}

B. T2

这题我感觉比较神秘，，我构造不出来那个式子。如果有神仙能从正面想出如何构造这个式子的话求评论或私聊教育我/kk

对于每一个装备，我们维护一个集合的集合 $S$，其元素为 $A$，$A$ 是一个 $2^k$ 的状态（初始物品的集合）

我们定义物品 $y$ 的价值为：

$$ \max_{A \in S} \min_{i \in A} i_y $$

每个初始物品的 $S$ 是所有包含它的集合 $A$ 的集合。

那么发现取最大值就是求并，最小值就是求交（画个例子理解一下就知道了）。

bitset 维护。注意查询答案的时候可以从小往大删除看在哪个地方突然不行来优化复杂度。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
std::bitset<4096> S[MAXN];
int n,k,q;
int a[13][MAXN];
std::vector<P> G[MAXN];

int main(){
    scanf("%d%d%d",&n,&k,&q);
    FOR(i,1,k) FOR(j,1,n) scanf("%d",&a[i][j]),G[j].pb(MP(a[i][j],i));
    FOR(i,1,n) std::sort(all(G[i]));//,std::reverse(all(G[i]));
    FOR(i,1,k){
        FOR(S,0,(1<<k)-1){
            if((S>>(i-1))&1) ::S[i][S] = 1;
        }
    }
    int now = k;
    FOR(i,1,q){
        int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
        if(opt == 1){
            S[++now] = S[x]|S[y];
        }
        if(opt == 2){
            S[++now] = S[x]&S[y];
        }
        if(opt == 3){
            int state = (1<<k)-1;
            FOR(i,0,k-1){
                state ^= (1<<(G[y][i].se-1));
                if(!S[x][state]){
                    printf("%d\n",G[y][i].fi);
                    break;
                }
            }
        }
    }
    return 0;
}

C. T3

完全想不出来，给出题人跪了！！1！！！

首先由于每次删除多个人之后概率会变比较烦，于是我们可以把没有恐龙套装就被删除的猫打上标记，我们定义轮数为删除的猫的次数（注意与题目中的定义不同，题目中轮数的定义是恐龙套装的猫的个数），每次随机一个猫如果有标记就直接扔掉就好，删除的时候把这个猫经过的时间的概率都算起来乘进去，这样答案是不变的（经典套路 1）

那么我们考虑对着这个东西搞一个 dp：$f[i][j]$ 表示考虑选了 $i$ 轮，有 $j$ 个恐龙套装猫的概率，也就是现在有 $i-j$ 个标记猫。

$$ \begin{aligned} f[i][j] &= f[i-1][j-1]p^{j-1}\frac{n-i}{n-i}+f[i-1][j](1-p^{j})\frac{n-i}{n-i}\\ &=f[i-1][j-1]p^{j-1}+f[i-1][j](1-p^{j}) \end{aligned} $$

（$\frac{n-i}{n-i}$ 下面那个是这次选中它当做套装的概率，上面那个是方案数，所以约掉了）

最后答案就是

$$ \frac{\sum_{i=0}^{n-1} f[i][t-1]p^{t-1}}{n} $$

也就是枚举他是在哪一轮被带走的，乘上之前操作的概率，$\frac{1}{n}$ 是因为你要确定一只猫，但是我们 dp 算的是任意一只猫。

接下来考虑如何去优化这个 dp。这个 $p^{j-1}$ 和 $j-1$ 是相同的，所以考虑令 $g[i][j] = f[i][j]p^j$，解出 $f[i][j]=\frac{g[i][j]}{p^j}$。代入可以得到

$$ g[i][j] = g[i-1][j-1]p^j + g[i-1][j](1-p^j) $$

设 $h_k(x)$ 为 $g[i][k]$ 的 OGF，即 $h_k(x)=\sum_{i=0}^{n-1} g[i][k]x^i$，那么转移就可以写成

$$ \begin{aligned} h_k(x) &= h_{k-1}(x)\times p^k\times x + h_k(x)\times (1-p^j)\times x\\ &= \frac{h_{k-1}(x)\times p^k \times x}{1-(1-p^j)\times x}\\ h_0(x) &= 1 \end{aligned} $$

所以进一步可以得到

$$ h_k(x) = \prod_{i=1}^k \frac{p^i \times x}{1-(1-p^i)x}=x^kp^{\frac{k(k+1)}{2}}\prod_{i=1}^k \frac{1}{1-(1-p^i)x} $$

由于下面的分子是齐次的，我们裂项可得一定存在一组数 $G_i$，满足：

$$ \prod_{i=1}^k \frac{1}{1-(1-p^i)x} = \sum_{i=1}^k \frac{G_i}{1-(1-p^i)x} $$

考虑一下通分就行了，总归可以消到 $1$的（不过我想不到，经典套路 2）

假设我们会算 $G_i$ 了我们考虑如何算答案：

$$ \begin{aligned} ans_{k+1} &= \sum_{j=0}^{n-1} [x^j]h_k(x)\\ &= \sum_{j=0}^{n-1}[x^j] (x^k p^{\frac{k(k+1)}{2}}\sum_{i=1}^k \frac{G_i}{1-(1-p^i)x})\\ &= p^{\frac{k(k+1)}{2}}\sum_{j=0}^{n-k-1}[x^j]\sum_{i=1}^k \frac{G_i}{1-(1-p^i)x}\\ &= p^{\frac{k(k+1)}{2}}\sum_{j=0}^{n-k-1}[x^j]\sum_{i=1}^k G_i \sum_{l \geq 0}(1-p^i)^lx^l\\ &= p^{\frac{k(k+1)}{2}}\sum_{j=0}^{n-k-1}\sum_{i=1}^k G_i(1-p^i)^j\\ &= p^{\frac{k(k+1)}{2}}\sum_{i=1}^kG_i\sum_{j=0}^{n-k-1} (1-p^i)^j\\ &= p^{\frac{k(k+1)}{2}}\sum_{i=1}^kG_i\frac{1-(1-p^i)^{n-k}}{1-p^i}\\ \end{aligned} $$

所以如果处理出 $G_i$，就能 $O(k\log k)$ 算答案。

现在考虑如何求 $G_i$。

考虑 $G_i$ 的定义：

$$ \begin{aligned} \frac{G_i}{1-(1-p^i)x}+\sum_{j=1,j \neq i}^{n} \frac{G_j}{1-(1-p^j)x}&=\prod_{j=1}^k \frac{1}{1-(1-p^j)x}\\ G_i+(1-(1-p^i)x)\sum_{j=1,j \neq i}^{n} \frac{G_j}{1-(1-p^j)x}&=\prod_{j=1,j \neq i}^k \frac{1}{1-(1-p^j)x}\\ \end{aligned} $$

令 $x=\frac{1}{1-p^i}$，可以得到：

$$ \begin{aligned} G_i&=\prod_{j=1,j \neq i}^k \frac{1}{1-\frac{1-p^j}{1-p^i}}\\ &= \prod_{j=1,j \neq i}^k \frac{1-p^i}{p^j-p^i}\\ &= (\frac{1-p^i}{p^i})^{k-1}\prod_{j=1,j \neq i}^k \frac{1}{p^{j-i}-1}\\ \end{aligned} $$

预处理 $\frac{1}{p_i-1}$ 和 $\frac{1}{p^{-i}-1}$ 的前缀积，可以 $O(k\log k)$ 时间计算 $G_i$。

这种题我下辈子再想出来吧（悲

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
const int ha = 1e9 + 7;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int G[MAXN];
int n,p;
int pp[MAXN],ipp[MAXN];
int pw1[MAXN],pw2[MAXN];
// pw1: 1/(1-p^i) pw2:1/(1-p^{-i})

int main(){
    int x,y;scanf("%d%d%d",&n,&x,&y);p = 1ll*x*qpow(y)%ha;
    pp[0] = 1;FOR(i,1,MAXN-1) pp[i] = 1ll*pp[i-1]*p%ha;
    ipp[MAXN-1] = qpow(pp[MAXN-1]);
    ROF(i,MAXN-2,0) ipp[i] = 1ll*ipp[i+1]*p%ha;
    pw1[0] = pw2[0] = 1;
    FOR(i,1,MAXN-1) pw1[i] = 1ll*pw1[i-1]*qpow((pp[i]-1+ha)%ha)%ha;
    FOR(i,1,MAXN-1) pw2[i] = 1ll*pw2[i-1]*qpow((ipp[i]-1+ha)%ha)%ha;
    int q;scanf("%d",&q);
    int inv = qpow(n);
    FOR(cwdw,1,q){
        int k;scanf("%d",&k);--k;
        if(k == 0){
            printf("%d\n",inv);
            continue;
        }
        if(k == 1) G[1] = 1;
        else FOR(i,1,k) G[i] = 1ll*qpow((1-pp[i]+ha),k-1)%ha*qpow(ipp[i],k-1)%ha*pw1[k-i]%ha*pw2[i-1]%ha;
        int ans = 0;
        FOR(i,1,k){
            int t = (qpow((1-pp[i]+ha)%ha,n-k)+ha-1)%ha;
            t = 1ll*t*qpow(ha-pp[i])%ha;
            (ans += 1ll*t*G[i]%ha) %= ha;
        }
        ans = 1ll*ans*qpow(p,(1ll*k*(k+1)/2) % (ha-1))%ha*inv%ha;
        printf("%d\n",ans);
    }
    return 0;
}

Last modification：August 26th, 2020 at 08:48 am

如果觉得我的文章对你有用，请随意赞赏

「NOI.AC」NOI挑战赛第三场

RainAir • 2020 年 07 月 18 日

A. T1

于是我们考虑将区间分成两个集合：$A$ 集合内的区间不包含任意一个区间，$B$ 集合的区间至少包含了一个其他的区间。

发现 $A$ 集合如果按照左端点排好序，右端点一定是有序的（只有相交和相离两种关系）。

然后 $B$ 集合的区间只有两个去处：

和它包含的区间分成一组，对答案无贡献
自成一组，对答案贡献长度。

于是枚举一下多少个 $B$ 集合的线段自称一组，贪心选择大的计算答案即可。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;

int n,m;
P c[MAXN];
std::vector<P> a,b;
int f[MAXN][MAXN];
int sm[MAXN];
bool used[MAXN];

inline bool cmp(P x,P y){
    return x.se-x.fi > y.se-y.fi;
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d%d",&c[i].fi,&c[i].se);
    FOR(i,1,n){
        bool flag = 1;
        FOR(j,1,n) if(i != j && c[i].fi <= c[j].fi && c[j].se <= c[i].se && !used[j]) {flag = 0;break;}
        if(flag) a.pb(c[i]);
        else b.pb(c[i]),used[i] = 1;
    }
    std::sort(all(a));std::sort(all(b),cmp);
    CLR(f,-0x3f);f[0][0] = 0;
    FOR(i,1,(int)a.size()){
        FOR(j,1,std::min(i,m)){
            FOR(k,1,i){
                if(a[k-1].se <= a[i-1].fi) continue;
                f[i][j] = std::max(f[i][j],f[k-1][j-1]+a[k-1].se-a[i-1].fi);
            }
        }
    }
    int ans = 0;
    FOR(i,1,(int)b.size()) sm[i] = sm[i-1]+(b[i-1].se-b[i-1].fi);
    FOR(i,0,m) ans = std::max(ans,f[(int)a.size()][i]+sm[m-i]);
    printf("%d\n",ans);
    return 0;
}

B. T2

这题我感觉比较神秘，，我构造不出来那个式子。如果有神仙能从正面想出如何构造这个式子的话求评论或私聊教育我/kk

对于每一个装备，我们维护一个集合的集合 $S$，其元素为 $A$，$A$ 是一个 $2^k$ 的状态（初始物品的集合）

我们定义物品 $y$ 的价值为：

$$ \max_{A \in S} \min_{i \in A} i_y $$

每个初始物品的 $S$ 是所有包含它的集合 $A$ 的集合。

那么发现取最大值就是求并，最小值就是求交（画个例子理解一下就知道了）。

bitset 维护。注意查询答案的时候可以从小往大删除看在哪个地方突然不行来优化复杂度。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
std::bitset<4096> S[MAXN];
int n,k,q;
int a[13][MAXN];
std::vector<P> G[MAXN];

int main(){
    scanf("%d%d%d",&n,&k,&q);
    FOR(i,1,k) FOR(j,1,n) scanf("%d",&a[i][j]),G[j].pb(MP(a[i][j],i));
    FOR(i,1,n) std::sort(all(G[i]));//,std::reverse(all(G[i]));
    FOR(i,1,k){
        FOR(S,0,(1<<k)-1){
            if((S>>(i-1))&1) ::S[i][S] = 1;
        }
    }
    int now = k;
    FOR(i,1,q){
        int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
        if(opt == 1){
            S[++now] = S[x]|S[y];
        }
        if(opt == 2){
            S[++now] = S[x]&S[y];
        }
        if(opt == 3){
            int state = (1<<k)-1;
            FOR(i,0,k-1){
                state ^= (1<<(G[y][i].se-1));
                if(!S[x][state]){
                    printf("%d\n",G[y][i].fi);
                    break;
                }
            }
        }
    }
    return 0;
}

C. T3

完全想不出来，给出题人跪了！！1！！！

那么我们考虑对着这个东西搞一个 dp：$f[i][j]$ 表示考虑选了 $i$ 轮，有 $j$ 个恐龙套装猫的概率，也就是现在有 $i-j$ 个标记猫。

$$ \begin{aligned} f[i][j] &= f[i-1][j-1]p^{j-1}\frac{n-i}{n-i}+f[i-1][j](1-p^{j})\frac{n-i}{n-i}\\ &=f[i-1][j-1]p^{j-1}+f[i-1][j](1-p^{j}) \end{aligned} $$

（$\frac{n-i}{n-i}$ 下面那个是这次选中它当做套装的概率，上面那个是方案数，所以约掉了）

最后答案就是

$$ \frac{\sum_{i=0}^{n-1} f[i][t-1]p^{t-1}}{n} $$

也就是枚举他是在哪一轮被带走的，乘上之前操作的概率，$\frac{1}{n}$ 是因为你要确定一只猫，但是我们 dp 算的是任意一只猫。

接下来考虑如何去优化这个 dp。这个 $p^{j-1}$ 和 $j-1$ 是相同的，所以考虑令 $g[i][j] = f[i][j]p^j$，解出 $f[i][j]=\frac{g[i][j]}{p^j}$。代入可以得到

$$ g[i][j] = g[i-1][j-1]p^j + g[i-1][j](1-p^j) $$

设 $h_k(x)$ 为 $g[i][k]$ 的 OGF，即 $h_k(x)=\sum_{i=0}^{n-1} g[i][k]x^i$，那么转移就可以写成

$$ \begin{aligned} h_k(x) &= h_{k-1}(x)\times p^k\times x + h_k(x)\times (1-p^j)\times x\\ &= \frac{h_{k-1}(x)\times p^k \times x}{1-(1-p^j)\times x}\\ h_0(x) &= 1 \end{aligned} $$

所以进一步可以得到

$$ h_k(x) = \prod_{i=1}^k \frac{p^i \times x}{1-(1-p^i)x}=x^kp^{\frac{k(k+1)}{2}}\prod_{i=1}^k \frac{1}{1-(1-p^i)x} $$

由于下面的分子是齐次的，我们裂项可得一定存在一组数 $G_i$，满足：

$$ \prod_{i=1}^k \frac{1}{1-(1-p^i)x} = \sum_{i=1}^k \frac{G_i}{1-(1-p^i)x} $$

考虑一下通分就行了，总归可以消到 $1$的（不过我想不到，经典套路 2）

假设我们会算 $G_i$ 了我们考虑如何算答案：

所以如果处理出 $G_i$，就能 $O(k\log k)$ 算答案。

现在考虑如何求 $G_i$。

考虑 $G_i$ 的定义：

令 $x=\frac{1}{1-p^i}$，可以得到：

预处理 $\frac{1}{p_i-1}$ 和 $\frac{1}{p^{-i}-1}$ 的前缀积，可以 $O(k\log k)$ 时间计算 $G_i$。

这种题我下辈子再想出来吧（悲

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
const int ha = 1e9 + 7;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int G[MAXN];
int n,p;
int pp[MAXN],ipp[MAXN];
int pw1[MAXN],pw2[MAXN];
// pw1: 1/(1-p^i) pw2:1/(1-p^{-i})

int main(){
    int x,y;scanf("%d%d%d",&n,&x,&y);p = 1ll*x*qpow(y)%ha;
    pp[0] = 1;FOR(i,1,MAXN-1) pp[i] = 1ll*pp[i-1]*p%ha;
    ipp[MAXN-1] = qpow(pp[MAXN-1]);
    ROF(i,MAXN-2,0) ipp[i] = 1ll*ipp[i+1]*p%ha;
    pw1[0] = pw2[0] = 1;
    FOR(i,1,MAXN-1) pw1[i] = 1ll*pw1[i-1]*qpow((pp[i]-1+ha)%ha)%ha;
    FOR(i,1,MAXN-1) pw2[i] = 1ll*pw2[i-1]*qpow((ipp[i]-1+ha)%ha)%ha;
    int q;scanf("%d",&q);
    int inv = qpow(n);
    FOR(cwdw,1,q){
        int k;scanf("%d",&k);--k;
        if(k == 0){
            printf("%d\n",inv);
            continue;
        }
        if(k == 1) G[1] = 1;
        else FOR(i,1,k) G[i] = 1ll*qpow((1-pp[i]+ha),k-1)%ha*qpow(ipp[i],k-1)%ha*pw1[k-i]%ha*pw2[i-1]%ha;
        int ans = 0;
        FOR(i,1,k){
            int t = (qpow((1-pp[i]+ha)%ha,n-k)+ha-1)%ha;
            t = 1ll*t*qpow(ha-pp[i])%ha;
            (ans += 1ll*t*G[i]%ha) %= ha;
        }
        ans = 1ll*ans*qpow(p,(1ll*k*(k+1)/2) % (ha-1))%ha*inv%ha;
        printf("%d\n",ans);
    }
    return 0;
}

「NOI.AC」NOI挑战赛第三场

A. T1

B. T2

C. T3

Leave a Comment Cancel reply

I'm back

NOI2021 退役记

SDOI2020 退役记

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「ZR 18 省选 3」题解

「ARC080F」Prime Flip

「NOI.AC」NOI挑战赛第三场

「八省联考2018」林克卡特树

线性基学习笔记

「NOI.AC」NOI挑战赛第三场

A. T1

B. T2

C. T3