牛客第四场

本文主要是介绍牛客第四场，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

新学期开始了，Bob 需要开始选课了。

 学校有n门课程，第i门课的学分是si 。  Bob在同一门课程中可以选择多次，如果他为第i门课程选择ki 次，他的总学分是∑i=1到n ki*si

 而且 Bob 的培训计划有一些局限性。  训练计划是这些n课程的有根树，每个限制意味着x子树中的总学分需要至少为cx 。

 现在Bob想知道满足培训计划限制的选课方式的数量，总学分是w。

 两种方式不同当且仅当存在至少一个 i∈[1,n]满足第 i 个课程的选择次数在这两个计划。

 答案可能很大，你只需要输出答案模块998244353即可。

输入描述：
第一行有两个整数 n,Q。 那么有n-1行来描述训练程序的有根树，每行有两个整数a,b表示a是b的父节点。 下一行有 n个整数 s1...n 。 下一行有 n 个整数 c1...n 。 然后是Q行，每一行有一个整数wi 表示第i个查询的总积分。

输出描述：

输出Q行，每一行有一个整数表示第i个查询的答案。

#include<bits/stdc++.h>
using namespace std;
const int N=105, mo=998244353, P=mo;
#define pb push_back
#define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
#define per(i,j,k) for(int i=(int)(j);i>=(int)(k);i--)
#define se second
#define fi first
typedef long long ll;
ll pw(ll x,int p){
    ll ans=1;do{if(p&1)ans = ans*x%mo; x = x*x%mo;
    }while(p>>=1);
    return ans;
}
 
vector<int>to[N];
int n,Q, sc[N], lw[N];
 
struct ply{
    vector<int> f;
    ply(int l=0){
        f.resize(l);
        for(int i=0;i<l;++i)f[i]=0;
    }
    ply(int l, ply &g){
        f.resize(l);
        for(int i=0,j=min(l,g.sz());i<j;++i)f[i]=g[i];
        for(int i=g.sz();i<l;++i)f[i]=0;
    }
    ply(const ply &g){
        f.resize(g.sz());
        for(int i=0,j=g.sz();i<j;++i)f[i]=g.f[i];
    }
    int sz() const {return f.size();}
    void pb(int x){f.push_back(x);}
     
    int& operator[](int x){return f[x];}
     
    ply operator^(ply g){
        int sum = 0; for(auto x:g.f)sum += x;
        ply b(sz() + sum, *this);
        for(auto x:g.f){
            for(int i=b.sz()-1;i;--i){
                if(i>=x)b[i] = (b[i] + mo - b[i-x]) % mo;
            }
        }
        return b;
    }
     
    ply operator-(ply b){
        ply c(max(sz(), b.sz()), *this);
        for(int i=0,j=b.sz();i<j;++i)c[i] = (c[i] + mo - b[i]) % mo;
        return c;
    }
     
    ply operator*(ply b){
        ply c(sz() + b.sz() - 1);
        for(int i=0, ik=sz(); i<ik; ++i)
            for(int j=0, jk=b.sz(); j<jk; ++j)
                c[i+j] = (c[i+j] + 1ll * f[i] * b[j]) % mo;
        return c;
    }
};
 
pair<ply, ply> operator/(ply a, ply b){
    if(a.sz() < b.sz()){
        return make_pair(ply(1), ply(b.sz(), a));
    }
    ply c(a.sz()-b.sz() + 1);
    for(int i=a.sz()-1, j=b.sz()-1;i>=j;--i){
        int w = 1ll * a[i] * pw(b[j], mo-2) % mo;
        c[i-j] = w;
        for(int k=0; k<=j; ++k)a[i-k] = (a[i-k] + mo - 1ll * w * b[j-k] % mo) % mo;
    }
    ply r(b.sz(), a);
    return make_pair(c,r);
}
 
ply mpw(ply x, int p, ply md){
    ply r;r.pb(1);
    do{
        if(p&1)r = ((x * r) / md).second;
        x = ((x * x) / md).second;
    }while(p>>=1);
    return r;
}
 
int calc(ply f, ply g, int n){
    if(g.sz() - 1 == 0)return (n <= f.sz() -1)? f[n] : 0;
    ///////////////////////
    assert(f.sz()==g.sz());
    assert(f[g.sz()-1]==0);
    f.f.pop_back();
    ply t(2);t[1]=1;
    ply r = mpw(t,n,g);
    int ans = 0;
    for(int i = 1; i < r.sz(); ++i){
        for(int j = 1; j <= i; ++j)f[i] = (f[i] + 1ll * f[i-j] * (mo - g[j])) % mo;
    }
    for(int i = 0; i < r.sz(); ++i){
        ans = (ans + 1ll * r[i] * f[i]) % mo;
    }
    return ans;
}
 
struct Poly{
    ply f,g;
    void unit(){
        f.pb(1);
    }
    int get(int x){
        ply d;d.pb(1);
        d = d ^ g;
 
        auto e=f/d;
        int ans=0;if(e.fi.sz()>=x+1)ans=e.fi[x];
 
        ans=(ans+calc(e.se,d,x))%P;
 
        return ans;
    }
     
    void mrg(Poly b){
        for(int x:b.g.f)g.pb(x);
        f = f * b.f;
    }
     
    void drp(int k){
        ply d(k, f);
        for(auto x:g.f){
            for(int i=x;i<k;++i)d[i] = (d[i-x] + d[i]) % mo;
        }
        f = f - (d^g);
    }
} dp[N];
 
void dfs(int x){
    dp[x].unit();
    dp[x].g.pb(sc[x]);
    for(int y:to[x]){
        dfs(y);
        dp[x].mrg(dp[y]);
    }
    dp[x].drp(lw[x]);
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>Q;
    for(int i=1,a,b;i<n;++i){
        cin>>a>>b;
        to[a].pb(b);
    }
    for(int i=1;i<=n;++i)cin>>sc[i];
    for(int i=1;i<=n;++i)cin>>lw[i];
    dfs(1);
    while(Q--){
        int v;cin>>v;
        cout<<dp[1].get(v)<<'\n';
    }
    return 0;
}

B

Bob 有一个随机数生成器，它会以 px的概率生成 x。

现在 Bob 将执行以下操作：

步骤 1. 通过随机数生成器生成一个数字 x。

步骤 2 如果 x 是生成数中最大的数（即 x 不小于任何先前生成的数），则转至步骤 1，否则转至步骤 3。

步骤 3. 如果 Bob 总共生成 x 个数字，Bob 将得到 x^2的分数。

现在鲍勃想知道他将得到的分数的期望值。

如果答案是不可约分数 x/y ，则需要在 [0,998244352] 中输出一个整数 d，满足 d×y mod 998244353=x mod 998244353。保证y mod 998244353≠0。

输入：

第一行有一个整数n，表示随机数生成器只能生成[1,n]中的整数。

第二行有 n个正整数 w1...n ，表示 pi=wi/∑j=1到n wj 。 2≤n≤100。 1≤wi≤10^6

输出：

输出答案

#include<stdio.h>
#include<stdlib.h>
void exgcd(long long a,long long &x0,long long b,long long &y0,long long &d)
{
    if(b==0)
    {
        x0=1,y0=0,d=a;
        return;
    }
    long long x1,y1;
    exgcd(b,x1,a%b,y1,d);
    x0=y1;
    y0=x1-(a/b)*y1;
}
long long inv(long long a,long long mod)
{
    long long x,y,d;
    exgcd(a,x,mod,y,d);
    if(d!=1)
        return -1;
    return (x%mod+mod)%mod;
}
int main()
{
    long long f1=1,f2=0,p[100],sum=0,w[100];
    int i,n;
    const long long mod=998244353;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%lld",&w[i]);
        sum+=w[i];
    }
    int invsum=inv(sum,mod);
    for(i=0;i<n;i++)
    {
        f1=(f1*sum%mod)*inv(sum-w[i],mod)%mod;
        f2=(w[i]*inv(sum-w[i],mod)%mod+f2)%mod;
    }
    int res=(2*f1*f2%mod+f1)%mod;
    printf("%lld",res);
}

C

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b, c, n;
    cin >> a >> b >> c >> n;
 
    int l1 = min(a, min(b, c)), l2, l3;
 
    if (l1 == a) l2 = min(b, c), l3 = max(b, c);
    if (l1 == b) l2 = min(a, c), l3 = max(a, c);
    if (l1 == c) l2 = min(a, b), l3 = max(a, b);
    // l1 < l2 < l3
 
    int ok = l1 + (l2 - l1) + (l3 - l1);
 
    if (ok > n)
    {
        cout << "NO" << endl;
        return 0;
    }
 
    string s1 = string(l1, 'a'), s2 = s1, s3 = s1;
 
    l2 -= l1, l3 -= l1, a -= l1, b -= l1, c -= l1;
 
    if (l2 == a) s1 += string(l2, 'b'), s2 += string(l2, 'b'), s3 += string(l2, 'c');
    if (l2 == b) s2 += string(l2, 'b'), s3 += string(l2, 'b'), s1 += string(l2, 'c');
    if (l2 == c) s1 += string(l2, 'b'), s3 += string(l2, 'b'), s2 += string(l2, 'c');
 
    if (l3 == a) s1 += string(l3, 'd'), s2 += string(l3, 'd'), s3 += string(l3, 'e');
    if (l3 == b) s2 += string(l3, 'd'), s3 += string(l3, 'd'), s1 += string(l3, 'e');
    if (l3 == c) s1 += string(l3, 'd'), s3 += string(l3, 'd'), s2 += string(l3, 'e');
 
    int len = n - l1 - l2 - l3;
    s1 += string(len, 'x'), s2 += string(len, 'y'), s3 += string(len, 'z');
 
    cout << s1 << endl << s2 << endl << s3 << endl;
 
    return 0;
}

D

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
#define eps 1e-8
#define N 50010
#define M 100010
#define MOD 998244353
 
using namespace std;
 
int n, K;
int idc = 0;
int head[N];
int siz[N];
LL dp[N][105][2];
LL tmp[105][2];
 
struct Edge{
    int to;
    int nxt;
}ed[N * 2];
 
LL quickmuit(LL a, LL b) {
    LL ans = 1;
    for( ; b; b >>= 1, (a *= a) %= MOD)
        if (b & 1)
            (ans *= a) %= MOD;
    return ans;
}
 
void adde(int u, int v) {
    ed[++idc].to = v;
    ed[idc].nxt = head[u];
    head[u] = idc;
}
 
void DP(int u, int fa) {
    siz[u] = 1;
    dp[u][0][0] = 1; dp[u][0][1] = 1;
    for(int k = head[u]; k; k = ed[k].nxt) {
        int v = ed[k].to;
        if (v == fa) continue;
        DP(v, u);
        memset(tmp, 0, sizeof(tmp));
        for(int i = 0; i < siz[u] && i <= K; i ++) {
            for(int j = 0; j < siz[v] && i + j <= K; j ++) {
                tmp[i + j][0] += dp[u][i][0] * dp[v][j][0] % MOD;
                tmp[i + j][0] %= MOD;
                tmp[i + j][1] += (dp[u][i][1] * dp[v][j][0] + dp[u][i][0] * dp[v][j][1]) % MOD;
                tmp[i + j][1] %= MOD;
                if (i + j == K) continue;
                tmp[i + j + 1][0] += dp[u][i][0] * dp[v][j][1] % MOD;
                tmp[i + j + 1][0] %= MOD;
                tmp[i + j + 1][1] += dp[u][i][1] * dp[v][j][1] % MOD;
                tmp[i + j + 1][1] %= MOD;
            }
        }
        memcpy(dp[u], tmp, sizeof(tmp));
        siz[u] += siz[v];
    }
}
 
int main() {
    cin >> n >> K;
    for (int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        adde(u, v); adde(v, u);
    }
    DP(1, 0);
    LL ans = dp[1][K][1] * quickmuit(n, K - 1) % MOD;
    cout << ans << endl;
    return 0;
}

 E

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define pii pair<int,int>
const int N = 1e6;
vector<pii>v[N];
vector< pii > ans;
int w[N], L[N], R[N];
bool vis[N];
void dfs(int now, int pre, int ww)
{
    for(auto it : v[now])
    {
        if(it.first == pre) continue;
        w[it.first] = ww ^ it.second;
        dfs(it.first, now, w[it.first]);
    }
}
 
void insert(int L, int R, int l, int r, int w)
{
     
    if(l <= L && r >= R)
    {
        int LL = L ^ (w & (~(R - L)) ) ;
        int RR = LL + (R-L);
//        cout<<l << " " << r << " "<< LL  << " " << RR << endl;
        ans.push_back(make_pair(LL, 1));
        ans.push_back(make_pair(RR+1, -1));
        return;
    }
    int mid = L + R >> 1;
    if(l <= mid) insert(L, mid, l, r, w);
    if(r > mid)  insert(mid+1, R, l, r, w);
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> L[i] >> R[i];
    }
    for(int i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c)), v[b].push_back(make_pair(a, c));
    }
    dfs(1,0,0);
    for(int i = 1; i <= n; i++)
    {
        insert(0, (1<<30)-1, L[i], R[i], w[i]);
    }
    sort(ans.begin(), ans.end());
    int res = 0, all = 0;
    for(int i = 0; i < ans.size() - 1; i++)
    {
        all += ans[i].second;
        if(all == n)
        res += ans[i+1].first - ans[i].first;
    }
    cout << res;
}

这篇关于牛客第四场的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！