题解归档 - P2482本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：P2482本地来源：problems/P2482/idea.md原始标题：P2482 猪国杀思路P2482 猪国杀大模拟，核心是把“真实身份”和“当前公开身份”分开：role 是真实身份：MP / ZP / FP。seen 是公开阵营：未知 / 跳忠 / 跳反，主猪初始视为跳忠。suspect 是主猪眼里的“类反猪”：隐藏身份者用 N/W 实际伤害主猪后标记；一旦跳身份就清掉。出牌阶段不能只线性扫一次。每次使用后都要从左到右重新寻找“当前最左可用牌”，因为装备连弩、摸奖励、主猪杀忠惩罚、死亡都会改变后续可用性。无懈可击用递归奇偶链：对某个锦囊即将作用到 target 时，从锦囊使用者开始找第一张愿意“献殷勤”的 J。若有人出了 J，这个 J 又可以被敌对 J 抵消，于是递归查找相反立场。当前 J 是否生效等于“没有被下一层抵消”。死亡处理顺序：掉血后先自动吃桃救到 hp >= 1。救不回则死亡，弃手牌和装备。立即检查胜利；若已胜利，不再执行摸三张或主猪弃牌惩罚。否则反猪死亡给伤害来源摸三张；忠猪被主猪杀死则主猪弃所有手牌和装备。复杂度主要来自手牌扫描和无懈递归。n <= 10, m <= 2000，直接 vector<char> 维护手牌足够。代码来源：problems/P2482/solution.cpp#include <bits/stdc++.h> using namespace std; struct Player { string role; int hp = 4; bool alive = true; bool weapon = false; vector<char> hand; int seen = 0; // 0 unknown, 1 loyal side, -1 rebel side bool suspect = false; // only used by MP: damaged MP by N/W while hidden }; int n, m; vector<Player> pig; vector<char> deck; int deck_pos; int rebel_alive; bool finished; string winner; char draw_card() { if (deck_pos < (int)deck.size()) { return deck[deck_pos++]; } return deck.back(); } void draw_cards(int u, int cnt) { while (cnt--) { pig[u].hand.push_back(draw_card()); } } int next_alive(int u) { int v = u; do { v = (v + 1) % n; } while (!pig[v].alive); return v; } bool has_card(int u, char c) { for (char x : pig[u].hand) { if (x == c) { return true; } } return false; } bool erase_first(int u, char c) { auto &h = pig[u].hand; for (auto it = h.begin(); it != h.end(); ++it) { if (*it == c) { h.erase(it); return true; } } return false; } void check_winner() { if (!pig[0].alive) { finished = true; winner = "FP"; } else if (rebel_alive == 0) { finished = true; winner = "MP"; } } void reveal_loyal(int u) { if (u == 0 || pig[u].role == "ZP") { pig[u].seen = 1; pig[u].suspect = false; } } void reveal_rebel(int u) { if (pig[u].role == "FP") { pig[u].seen = -1; pig[u].suspect = false; } } void express_kindness(int u, int target) { if (pig[u].role == "ZP" && (target == 0 || pig[target].seen == 1)) { reveal_loyal(u); } else if (pig[u].role == "FP" && pig[target].seen == -1) { reveal_rebel(u); } } void express_hostility(int u, int target) { if (pig[u].role == "ZP" && pig[target].seen == -1) { reveal_loyal(u); } else if (pig[u].role == "FP" && (target == 0 || pig[target].seen == 1)) { reveal_rebel(u); } } bool can_kind(int u, int target) { if (!has_card(u, 'J')) { return false; } if (pig[u].role == "MP") { return target == 0 || pig[target].seen == 1; } if (pig[u].role == "ZP") { return target == 0 || pig[target].seen == 1; } return pig[target].seen == -1; } bool can_hostile(int u, int target) { if (!has_card(u, 'J')) { return false; } if (pig[u].role == "MP") { return pig[target].seen == -1; } if (pig[u].role == "ZP") { return pig[target].seen == -1; } return target == 0 || pig[target].seen == 1; } bool nullify(int source, int target, bool kind) { for (int step = 0; step < n; ++step) { int u = (source + step) % n; if (!pig[u].alive) { continue; } bool ok = kind ? can_kind(u, target) : can_hostile(u, target); if (!ok) { continue; } erase_first(u, 'J'); if (kind) { express_kindness(u, target); } else { express_hostility(u, target); } bool countered = nullify(u, target, !kind); return !countered; } return false; } void try_save_with_peach(int u) { while (pig[u].hp <= 0 && erase_first(u, 'P')) { ++pig[u].hp; } } void damage(int target, int source) { if (finished || !pig[target].alive) { return; } --pig[target].hp; if (pig[target].hp <= 0) { try_save_with_peach(target); } if (pig[target].hp > 0) { return; } pig[target].alive = false; pig[target].weapon = false; pig[target].hand.clear(); if (pig[target].role == "FP") { --rebel_alive; } check_winner(); if (finished) { return; } if (pig[target].role == "FP" && source != -1 && pig[source].alive) { draw_cards(source, 3); } if (pig[target].role == "ZP" && source == 0 && pig[0].alive) { pig[0].hand.clear(); pig[0].weapon = false; } } bool duel_discard_kill(int u, int opponent) { if (pig[u].role == "ZP" && opponent == 0) { return false; } return erase_first(u, 'K'); } void slash(int source, int target) { express_hostility(source, target); if (erase_first(target, 'D')) { return; } damage(target, source); } void duel(int source, int target) { express_hostility(source, target); if (nullify(source, target, true)) { return; } int cur = target; int other = source; while (!finished) { if (duel_discard_kill(cur, other)) { swap(cur, other); } else { damage(cur, other); return; } } } void aoe(int source, char need) { int u = next_alive(source); while (u != source && !finished) { int cur = u; u = next_alive(u); if (nullify(source, cur, true)) { continue; } if (!erase_first(cur, need)) { damage(cur, source); if (!finished && cur == 0 && pig[source].seen == 0) { pig[source].suspect = true; } } } } bool attackable_by_mp(int target) { return pig[target].seen == -1 || (pig[target].seen == 0 && pig[target].suspect); } int first_target(int source, function<bool(int)> ok) { int u = next_alive(source); while (u != source) { if (ok(u)) { return u; } u = next_alive(u); } return -1; } int kill_target(int source) { int target = next_alive(source); if (target == source) { return -1; } if (pig[source].role == "MP") { return attackable_by_mp(target) ? target : -1; } if (pig[source].role == "ZP") { return pig[target].seen == -1 ? target : -1; } return (target == 0 || pig[target].seen == 1) ? target : -1; } int duel_target(int source) { if (pig[source].role == "MP") { return first_target(source, [](int u) { return attackable_by_mp(u); }); } if (pig[source].role == "ZP") { return first_target(source, [](int u) { return pig[u].seen == -1; }); } return pig[0].alive ? 0 : -1; } bool try_use_card(int u, int pos, bool &used_kill) { char c = pig[u].hand[pos]; if (c == 'P') { if (pig[u].hp == 4) { return false; } pig[u].hand.erase(pig[u].hand.begin() + pos); ++pig[u].hp; return true; } if (c == 'K') { if (!pig[u].weapon && used_kill) { return false; } int target = kill_target(u); if (target == -1) { return false; } pig[u].hand.erase(pig[u].hand.begin() + pos); used_kill = true; slash(u, target); return true; } if (c == 'F') { int target = duel_target(u); if (target == -1) { return false; } pig[u].hand.erase(pig[u].hand.begin() + pos); duel(u, target); return true; } if (c == 'N') { pig[u].hand.erase(pig[u].hand.begin() + pos); aoe(u, 'K'); return true; } if (c == 'W') { pig[u].hand.erase(pig[u].hand.begin() + pos); aoe(u, 'D'); return true; } if (c == 'Z') { pig[u].hand.erase(pig[u].hand.begin() + pos); pig[u].weapon = true; return true; } return false; } void play_turn(int u) { draw_cards(u, 2); bool used_kill = false; while (!finished && pig[u].alive) { bool used = false; for (int i = 0; i < (int)pig[u].hand.size(); ++i) { if (try_use_card(u, i, used_kill)) { used = true; break; } } if (!used) { break; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; pig.assign(n, Player()); deck.clear(); deck.reserve(m); deck_pos = 0; rebel_alive = 0; finished = false; for (int i = 0; i < n; ++i) { cin >> pig[i].role; if (pig[i].role == "FP") { ++rebel_alive; } for (int j = 0; j < 4; ++j) { string s; cin >> s; pig[i].hand.push_back(s[0]); } } for (int i = 0; i < m; ++i) { string s; cin >> s; deck.push_back(s[0]); } pig[0].seen = 1; check_winner(); int cur = 0; while (!finished) { if (pig[cur].alive) { play_turn(cur); } if (!finished) { cur = next_alive(cur); } } cout << winner << '\n'; for (int i = 0; i < n; ++i) { if (!pig[i].alive) { cout << "DEAD\n"; continue; } for (int j = 0; j < (int)pig[i].hand.size(); ++j) { if (j) { cout << ' '; } cout << pig[i].hand[j]; } cout << '\n'; } return 0; }
题解归档 - NC20099本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：NC20099本地来源：problems/NC20099/idea.md原始标题：NC20099 [HNOI2012] 矿场搭建思路NC20099 [HNOI2012] 矿场搭建题意无向图，在若干点放救援出口；任意单点坍塌后，剩余每个连通块内都要有出口。求最少出口数与方案数（多测，N 为边数，N=0 结束）。思路Tarjan 求割点 + 点双连通分量。每个点双内割点数 c：c>=2：不额外放出口；c==1：放 1 个（不能放割点上），方案乘 |DCC|-1；c==0：整图一个点双，放 2 个，方案乘 C(|DCC|,2)。代码来源：problems/NC20099/solution.cpp#include<bits/stdc++.h> #define ll long long #define ull unsigned long long using namespace std; const ll maxn=1010; vector<ll>ss[maxn+5]; vector<ll>cccc[maxn+5]; ll dfn[maxn+5],low[maxn+5],st[maxn+5],top,timer,mx,cccc_cnt; bool cut[maxn+5]; void tarjan(ll u,ll root){ ll i,v,sz,cnt; dfn[u]=++timer; low[u]=timer; st[++top]=u; sz=ss[u].size(); if(u==root and sz==0){ cccc_cnt++; cccc[cccc_cnt]={u}; top--; return; } cnt=0; for(i=0;i<sz;i++){ v=ss[u][i]; if(!dfn[v]){ cnt++; tarjan(v,root); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]){ if(u!=root or cnt>=2) cut[u]=true; cccc_cnt++; cccc[cccc_cnt].clear(); while(st[top]!=v){ cccc[cccc_cnt].push_back(st[top]); top--; } cccc[cccc_cnt].push_back(st[top]); top--; cccc[cccc_cnt].push_back(u); } }else low[u]=min(low[u],dfn[v]); } } void clear_graph(){ ll i; for(i=1;i<=mx;i++){ ss[i].clear(); dfn[i]=0; low[i]=0; cut[i]=false; } for(i=1;i<=cccc_cnt;i++) cccc[i].clear(); top=0; timer=0; cccc_cnt=0; mx=0; } int main(){ ll n,i,j,k,u,v,sz,ccnt,ans1,tc; ull ans2; scanf("%lld",&n); for(tc=1;n!=0;tc++){ clear_graph(); for(i=1;i<=n;i++){ scanf("%lld%lld",&u,&v); ss[u].push_back(v); ss[v].push_back(u); mx=max(mx,max(u,v)); } for(i=1;i<=mx;i++){ if(!dfn[i]){ top=0; tarjan(i,i); } } ans1=0; ans2=1; for(i=1;i<=cccc_cnt;i++){ ccnt=0; sz=cccc[i].size(); for(j=0;j<sz;j++){ if(cut[cccc[i][j]]) ccnt++; } if(ccnt>=2) continue; if(ccnt==1){ ans1++; ans2*=max(sz-1,1ll); }else{ ans1+=2; ans2*=1ull*sz*(sz-1)/2; } } printf("Case %lld: %lld %llu\n",tc,ans1,ans2); scanf("%lld",&n); } return 0; }
题解归档 - NC19981本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：NC19981本地来源：problems/NC19981/idea.md原始标题：NC19981 [HAOI2010] 软件安装思路NC19981 [HAOI2010] 软件安装题意$n$ 个软件，容量 $m$；软件 $i$ 占 $w_i$、价值 $v_i$，依赖 $d_i$（$d_i=0$ 无依赖）。只有依赖链上的软件都装了，$i$ 才计入价值。求容量内最大总价值。思路依赖边 $i\to d_i$，每点出度 $\le1$ → 函数图，可能有环。Tarjan 缩点：环上软件必须整体选/不选，合并 $w,v$。缩点后成森林，树上背包：$f[u][j]$ 为以 $u$ 为根的子树、必须选 $u$、容量 $j$ 的最大价值；儿子逐个合并。多棵树的根再做一个背包合并进 dp[]。强度经典 HAOI2010 / 依赖背包 + 缩点，约 紫题 / 提高+ 水平。代码来源：problems/NC19981/solution.cpp#include<bits/stdc++.h> #define ll long long using namespace std; const ll maxn=110; const ll maxm=510; const ll inf=1e18; vector<ll>ss[maxn+5],zczc[maxn+5],dqdq; ll w[maxn+5],v[maxn+5],d[maxn+5],dfn[maxn+5],low[maxn+5],bel[maxn+5],sw[maxn+5],sv[maxn+5],p[maxn+5],f[maxn+5][maxm+5],dp[maxm+5]; bool ins[maxn+5]; ll timer,scc_cnt,m; void tarjan(ll u){ ll i,j,k,zc; dfn[u]=low[u]=++timer; dqdq.push_back(u); ins[u]=true; for(i=0;i<(ll)ss[u].size();i++){ zc=ss[u][i]; if(!dfn[zc]){ tarjan(zc); low[u]=min(low[u],low[zc]); }else if(ins[zc]){ low[u]=min(low[u],dfn[zc]); } } if(low[u]==dfn[u]){ scc_cnt++; while(true){ zc=dqdq.back(); dqdq.pop_back(); ins[zc]=false; bel[zc]=scc_cnt; sw[scc_cnt]+=w[zc]; sv[scc_cnt]+=v[zc]; if(u==zc) break; } } } void dfs(ll u){ ll i,j,k,zc; for(j=0;j<=m;j++) f[u][j]=-inf; f[u][sw[u]]=sv[u]; for(i=0;i<(ll)zczc[u].size();i++){ zc=zczc[u][i]; dfs(zc); for(j=m;j>=0;j--){ for(k=0;k<=j;k++){ if(f[zc][k]>-inf/2 and f[u][j-k]>-inf/2) f[u][j]=max(f[u][j],f[u][j-k]+f[zc][k]); } } } } int main(){ ll n,i,j,k,zc,ans; scanf("%lld%lld",&n,&m); for(i=1;i<=n;i++) scanf("%lld",&w[i]); for(i=1;i<=n;i++) scanf("%lld",&v[i]); for(i=1;i<=n;i++) scanf("%lld",&d[i]); for(i=1;i<=n;i++){ if(d[i]) ss[i].push_back(d[i]); } for(i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } for(i=1;i<=scc_cnt;i++) p[i]=0; for(i=1;i<=n;i++){ if(d[i] and bel[i]!=bel[d[i]]) p[bel[i]]=bel[d[i]]; } for(i=1;i<=scc_cnt;i++){ if(p[i]) zczc[p[i]].push_back(i); } for(i=1;i<=scc_cnt;i++){ if(!p[i]){ dfs(i); for(j=m;j>=0;j--){ for(k=0;k<=j;k++){ if(f[i][k]>-inf/2) dp[j]=max(dp[j],dp[j-k]+f[i][k]); } } } } ans=0; for(i=0;i<=m;i++) ans=max(ans,dp[i]); printf("%lld\n",ans); return 0; }
题解归档 - cf932G本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：cf932G本地来源：problems/cf932G/idea.md题目链接：https://codeforces.com/contest/932/problem/G原始标题：cf932G — Palindrome Partition思路cf932G — Palindrome Partition题意给定偶长字符串 s，将其切成偶数段 p1,…,pk，要求 pi = p_{k-i+1}（段序列本身是回文）。求方案数 mod 1e9+7。转化构造 t = s1 s_n s2 s_{n-1} …（首尾交替取字符，|t|=|s|）。结论：原串的合法划分 ↔ 对 t 做「偶数个回文串」的划分（每段是回文，段数为偶数）。直觉：外层对称段 (p1,pk) 在 t 里对应一段偶长回文；向内递归同理。DPdp[i] = 前 i 个字符的合法划分方案数。朴素：对每个以 i 结尾的回文后缀长度 len，dp[i] += dp[i-len]。约束：段数必须为偶数 ⇒ 若 i 为奇数，强制 dp[i]=0。初始 dp[0]=1。回文自动机优化对每个位置 i，以 i 结尾的所有回文后缀在 PAM 上形成 O(log n) 条「等差长度链」（border/周期性质）。对每个结点 v 维护：dif(v) = len(v) - len(fa(v))slk(v)：沿 fail 向上第一个 dif 不同的祖先f(v)：当前等差链在「最后更新位置」上的 dp 贡献和转移（沿 slk 跳，最多 O(log n) 次）：f(v) = dp[i - slk(v).len - dif(v)] 若 slk(v) != fa(v)：f(v) += fa(v).f dp[i] += f(v)复杂度时间 O(n log n)空间 O(n)验证样例 abcdcdab → 1，abbababababbab → 3与暴力（递归匹配首尾相等前缀/后缀）对拍 70+ 小数据无分歧（Kali SSH 中断前）参考博客园题解代码来源：problems/cf932G/solution.cpp/* Author: likely * Time: 2026-06-08 03:29:27 **/ #include<bits/stdc++.h> #define ll long long using namespace std; const ll maxn=1000005; const ll mod=1000000007; struct node{ ll len,dif,f; node *slk,*ch[26],*fa; }; node pl[maxn+5],*rt1,*rt2,*ncnt; node *nd[maxn+5]; char s[maxn+5],t[maxn+5]; ll dp[maxn+5],i,j,k,len; void build(char *S,ll n){ rt1=ncnt=pl; rt2=(++ncnt); rt2->fa=rt1; rt1->len=-1; rt2->len=0; node *pre=rt1; for(i=0;i<n;i++){ while(S[i]!=S[i-pre->len-1]) pre=pre->fa; if(pre->ch[S[i]-'a']==nullptr){ node *q=(++ncnt); q->len=pre->len+2; if(pre==rt1) q->fa=rt2; else{ node *p=pre->fa; while(S[i]!=S[i-p->len-1]) p=p->fa; q->fa=p->ch[S[i]-'a']; } q->dif=q->len-q->fa->len; q->slk=(q->dif==q->fa->dif?q->fa->slk:q->fa); pre->ch[S[i]-'a']=q; } nd[i+1]=pre=pre->ch[S[i]-'a']; } } int main(){ scanf("%s",s); len=strlen(s); for(i=0;i<len/2;i++){ t[(i<<1)+1]=s[i]; t[(i<<1|1)+1]=s[len-i-1]; } build(t+1,len); dp[0]=1; for(i=1;i<=len;i++){ node *p=nd[i]; while(p!=rt2){ p->f=dp[i-p->slk->len-p->dif]; if(p->slk!=p->fa) p->f=(p->f+p->fa->f)%mod; dp[i]=(dp[i]+p->f)%mod; p=p->slk; } if(i&1) dp[i]=0; } printf("%lld\n",dp[len]); return 0; }
题解归档 - cf932F本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：cf932F本地来源：problems/cf932F/idea.md题目链接：https://codeforces.com/contest/932/problem/F原始标题：CF932F Escape Through Leaf思路CF932F Escape Through Leaf题意根为 1 的树，点 (i) 有权值 (a_i,b_i)。从 (x) 跳到子树内 (y) 代价 (a_x\cdot b_y)，路径代价为跳跃代价之和。对每个点求到任意叶子的最小代价；根即使度数为 1 也不算叶子。做法树形 DP：[dp_u=\min_{v\in subtree(u),\,v\ne u}(a_u\cdot b_v+dp_v),\quad \text{叶子 }dp=0]把 (dp_v + a_u\cdot b_v) 看成直线 (f_v(x)=b_v\cdot x+dp_v)，在 (x=a_u) 处取最小值 → 李超线段树维护子树直线集。启发式合并（按 cccc 大小 swap）：小集合并入大集合，逐条 add 进李超树。DFS 后：非叶子：dp[u]=query(a[u])插入直线 ((b_u,dp_u))复杂度 (O(n\log^2 n))。Catalog标签：Li Chao treeAC 后沉淀：lib/数据结构(LiChao树).cpp本地样例：python tools/run_exe.py cf932F --input problems/cf932F/sample.in对拍：python tools/stress.py cf932F -n 500代码来源：problems/cf932F/solution.cpp/* Author: likely * Time: 2026-06-08 02:41:27 **/ #include<bits/stdc++.h> #define ll long long using namespace std; const ll inf=1e18; const ll maxn=100005; const ll maxa=200005; vector<ll>ss[maxn]; ll a[maxn],b[maxn],dp[maxn],n,i,j,k; struct Line{ ll m,c; Line(){m=0,c=inf;} Line(ll k,ll b){m=k,c=b;} ll vl(ll x){return m*x+c;} }; struct lichao{ ll tl,tr,tm; Line val; lichao *l,*r; lichao(ll x,ll y){ tl=x,tr=y,tm=tl+(tr-tl)/2; l=r=nullptr; } void add(Line u){ if(u.vl(tm)<val.vl(tm)) swap(u,val); if(u.vl(tl)<val.vl(tl)){ if(l==nullptr) l=new lichao(tl,tm); l->add(u); } if(u.vl(tr)<val.vl(tr)){ if(r==nullptr) r=new lichao(tm+1,tr); r->add(u); } } ll query(ll x){ ll ans=val.vl(x); if(x<=tm){ if(l!=nullptr) ans=min(ans,l->query(x)); }else if(r!=nullptr) ans=min(ans,r->query(x)); return ans; } }; vector<Line>cccc[maxn]; lichao *tr[maxn]; void dfs(ll x,ll fa){ ll zc,pd=1; tr[x]=new lichao(-maxa,maxa); for(i=0;i<(ll)ss[x].size();i++){ zc=ss[x][i]; if(zc==fa) continue; pd=0; dfs(zc,x); if(cccc[zc].size()>cccc[x].size()){ swap(cccc[x],cccc[zc]); swap(tr[x],tr[zc]); } ll p; for(p=0;p<(ll)cccc[zc].size();p++){ tr[x]->add(cccc[zc][p]); cccc[x].push_back(cccc[zc][p]); } } if(pd) dp[x]=0; else dp[x]=tr[x]->query(a[x]); Line cur=Line(b[x],dp[x]); cccc[x].push_back(cur); tr[x]->add(cur); } int main(){ ll x,y; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=n;i++) cin>>b[i]; for(i=1;i<=n-1;i++){ cin>>x>>y; ss[x].push_back(y); ss[y].push_back(x); } dfs(1,0); for(i=1;i<=n;i++){ if(i>1) cout<<" "; cout<<dp[i]; } cout<<"\n"; return 0; }
题解归档 - cf932E本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：cf932E本地来源：problems/cf932E/idea.md题目链接：https://codeforces.com/contest/932/problem/E原始标题：CF932E Team Work思路CF932E Team Work题意N 个人，选任意非空子集，大小为 x 的子集代价为 x^k。求所有非空子集代价之和，模 1e9+7。做法答案为[\sum_{x=1}^{N} \binom{N}{x} x^k]用第二类 Stirling 数展开 x^k：[x^k = \sum_{j=0}^{k} S(k,j)\, x^{\underline{j}}]其中 x^{\underline{j}} = x(x-1)\cdots(x-j+1) 为下降阶乘。关键恒等式：[\sum_{x=j}^{N} \binom{N}{x} x^{\underline{j}} = (N)_j \cdot 2^{N-j}]于是[\text{ans} = \sum_{j=0}^{k} S(k,j)\,(N)_j\,2^{N-j}]S(k,j) 用 O(k^2) DP 预处理（k ≤ 5000）(N)_j 逐项乘 (N-j+1) mod MOD2^{N-j} 维护当前幂，每步乘 inv2复杂度O(k^2) 时间，O(k^2) 空间。验证样例 N=3,k=2 → 24；N=1,k=1 → 1。与暴力枚举 2^N 子集一致。代码来源：problems/cf932E/solution.cpp/* Author: likely * Time: 2026-06-08 03:25:45 **/ #include<bits/stdc++.h> #define ll long long using namespace std; const ll maxk=5005,mod=1e9+7,inv2=500000004; ll cur[maxk],pre[maxk]; ll ksm(ll a,ll b){ ll zc=1; a%=mod; while(b){ if(b&1) zc=zc*a%mod; a=a*a%mod; b>>=1; } return zc; } int main(){ ll n,k,i,j,ans,f,pw; cin>>n>>k; pre[0]=1; for(i=1;i<=k;i++){ cur[0]=0; for(j=1;j<=i;j++) cur[j]=(pre[j-1]+pre[j]*j)%mod; for(j=0;j<=i;j++) pre[j]=cur[j]; } ans=0; f=1; pw=ksm(2,n); for(j=0;j<=k;j++){ ans=(ans+pre[j]*f%mod*pw)%mod; f=f*((n-j)%mod)%mod; pw=pw*inv2%mod; } cout<<ans<<"\n"; return 0; }
题解归档 - cf932D本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：cf932D本地来源：problems/cf932D/idea.md题目链接：https://codeforces.com/contest/932/problem/D原始标题：cf932D Tree思路cf932D Tree题意动态向以 1 为根的树加叶子（带权），支持查询：从节点 R 出发沿祖先方向走，相邻两点 i→j（i 是 j 祖先）需满足 w[i]≥w[j] 且路径上无 k 使 w[k]≥w[j]；权值和 ≤ X 时最长链长。查询带 XOR 混淆（last 为上次 type2 答案）。思路树上倍增（权值单调祖先跳）：fa[v][0]：从 v 向上第一个「可接在 v 后面」的祖先 u（即 w[u]≥w[v]，且 v→u 路径上无权 ≥w[v]）。加边 pa→v：若 w[pa]≥w[v] 则 fa[v][0]=pa；否则从 pa 倍增找最远满足 w[·]<w[v] 的节点，再取其 fa[·][0]。sum[v][i]：沿 fa[v][i] 跳 2^i 步所经节点权值和（不含 v 自身）。查询：先扣 w[R]，再从高到低倍增，能跳则 ans += 2^i。复杂度预处理每点 O(log N)，查询 O(log N)，总 O(Q log N)。验证样例 4 组 + stress.py 对拍 brute.cpp（q≤12，权值≤4）。代码来源：problems/cf932D/solution.cpp/* Author: likely * Time: 2026-06-08 03:24:21 **/ #include<bits/stdc++.h> #define ll long long using namespace std; const ll inf=1e18; const ll maxn=400005; ll fa[maxn][22],sum[maxn][22],w[maxn],cnt,last,q,i,j,k,zc,pd,cur,dq,ans; void adde(ll pa,ll va){ cnt++; w[cnt]=va; if(w[pa]>=va) fa[cnt][0]=pa; else{ cur=pa; for(i=20;i>=0;i--){ if(fa[cur][i] and w[fa[cur][i]]<va) cur=fa[cur][i]; } if(fa[cur][0] and w[fa[cur][0 =va) fa[cnt][0]=fa[cur][0]; else fa[cnt][0]=0; } if(!fa[cnt][0]) sum[cnt][0]=inf; else sum[cnt][0]=w[fa[cnt][0]]; for(i=1;i<=20;i++){ fa[cnt][i]=fa[fa[cnt][i-1]][i-1]; if(fa[cnt][i]) sum[cnt][i]=sum[cnt][i-1]+sum[fa[cnt][i-1]][i-1]; else sum[cnt][i]=inf; } } ll query(ll r,ll x){ if(w[r]>x) return 0; x-=w[r]; cur=r; ans=1; for(i=20;i>=0;i--){ if(fa[cur][i] and sum[cur][i]<=x){ x-=sum[cur][i]; cur=fa[cur][i]; ans+=(1ll<<i); } } return ans; } int main(){ scanf("%lld",&q); cnt=1; w[1]=0; last=0; while(q--){ ll opr,a,b; scanf("%lld%lld%lld",&opr,&a,&b); a^=last; b^=last; if(opr==1){ adde(a,b); }else{ last=query(a,b); printf("%lld\n",last); } } return 0; }
题解归档 - cf932C本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：cf932C本地来源：problems/cf932C/idea.md题目链接：https://codeforces.com/contest/932/problem/C原始标题：932C Permutation Cycle思路932C Permutation Cycle题意给定 (N,A,B)，构造 (1\ldots N) 的排列 (P)。定义 (f(i,j)) 为从 (i) 出发沿 (P) 走 (j) 步到达的位置，(g(i)) 为最小正整数 (j) 使 (f(i,j)=i)（即 (i) 所在置换环的长度）。要求对每个 (i)，(g(i)\in{A,B})；无解输出 -1。关键观察(g(i)) 等于 (i) 在置换分解中所在环的长度。因此问题等价于：能否把 ({1,\ldots,N}) 划分成若干个不相交环，且每个环长只能是 (A) 或 (B)。充要条件：存在非负整数 (x,y) 使 (xA+yB=N)。(A=B) 时即 (N) 能被 (A) 整除。一般情况枚举 (x\in[0,\lfloor N/A\rfloor])，检查 (N-xA) 是否被 (B) 整除。构造找到一组 ((x,y)) 后，从 cur=1 依次放置：(x) 个长为 (A) 的环：p[cur..cur+A-2]=cur+1..cur+A-1，p[cur+A-1]=cur；(y) 个长为 (B) 的环，同理。复杂度时间 (O(N))，空间 (O(N))。验证样例 9 2 5 → 2 1 4 3 6 7 8 9 5；3 2 1 可取全不动点 1 2 3。代码来源：problems/cf932C/solution.cpp/* Author: likely * Time: 2026-06-08 03:24:06 **/ #include<bits/stdc++.h> #define ll long long #define maxn 1000005 using namespace std; ll p[maxn]; int main(){ ll n,a,b,i,j,k,cur,x,y,zc; cin>>n>>a>>b; if(a==b){ if(n%a){ cout<<-1<<"\n"; return 0; } x=n/a; y=0; }else{ zc=0; for(i=0;i*a<=n;i++){ if((n-i*a)%b==0){ x=i; y=(n-i*a)/b; zc=1; break; } } if(!zc){ cout<<-1<<"\n"; return 0; } } cur=1; for(i=0;i<x;i++){ for(j=0;j<a-1;j++) p[cur+j]=cur+j+1; p[cur+a-1]=cur; cur+=a; } for(i=0;i<y;i++){ for(j=0;j<b-1;j++) p[cur+j]=cur+j+1; p[cur+b-1]=cur; cur+=b; } for(i=1;i<=n;i++){ cout<<p[i]; if(i<n) cout<<" "; } cout<<"\n"; return 0; }
题解归档 - cf932B本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：cf932B本地来源：problems/cf932B/idea.md题目链接：https://codeforces.com/contest/932/problem/B原始标题：cf932B Recursive Queries思路cf932B Recursive Queries题意定义正整数上的函数：f(n)：若 n < 10 则 f(n)=n；否则 f(n) 为 n 各位非零数字之积。g(n)：若 n < 10 则 g(n)=n；否则 g(n)=g(f(n))。共 Q 组询问，每组给 l,r,k，求 x∈[l,r] 中满足 g(x)=k 的个数。做法f(n)<n（n≥10），故 g 可自底向上递推。预处理 1..10^6 的 g(i)，再对 k=1..9 建前缀和 cnt[k][i]。每次询问 O(1)：cnt[k][r]-cnt[k][l-1]。验证样例与 stress.py -n 500 对拍通过。代码来源：problems/cf932B/solution.cpp/* Author: likely * Time: 2026-06-08 05:22:29 **/ #include<bits/stdc++.h> #define ll long long using namespace std; #define maxn 1000005 ll g[maxn],s[10][maxn]; ll fpd(ll x){ ll zc=1; while(x){ if(x%10) zc*=(x%10); x/=10; } return zc; } int main(){ ll t,n,i,j,k,l,r,zc,cnt,ans; for(i=1;i<maxn;i++){ if(i<10) g[i]=i; else g[i]=g[fpd(i)]; } for(i=1;i<maxn;i++){ for(j=1;j<=9;j++) s[j][i]=s[j][i-1]; if(g[i]>=1 and g[i]<=9) s[g[i]][i]++; } cin>>t; while(t--){ cin>>l>>r>>k; cout<<s[k][r]-s[k][l-1]<<"\n"; } return 0; }
题解归档 - cf932A本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。本地编号：cf932A本地来源：problems/cf932A/idea.md题目链接：https://codeforces.com/contest/932/problem/A原始标题：932A Palindromic Supersequence思路932A Palindromic Supersequence题意给定字符串 A，构造长度 ≤ 10^4 的回文串 B，使得 A 是 B 的子序列。保证有解，输出任意合法 B。做法若 A 本身已是回文，直接输出 A。否则令 B = A + reverse(A)[1..]（即 A 接上反转串去掉首字符）。A 整体作为 B 前缀仍是子序列；后半段镜像补齐使整体回文。长度 ≤ 2|A|−1 ≤ 1999。验证样例 aba→aba，ab→aba（题面样例 aabaa 亦合法，本解更短）。代码来源：problems/cf932A/solution.cpp/* Author: likely * Time: 2026-06-08 03:20:30 **/ #include<bits/stdc++.h> #define ll long long using namespace std; string s,t; int main(){ cin>>s; t=s; reverse(t.begin(),t.end()); if(s==t) cout<<s<<"\n"; else cout<<s+t.substr(1)<<"\n"; return 0; }