牛客第四场
新学期开始了，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; }
版权声明：本文为EVANGELION-01原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。