A.建设城市(city)
这容斥题多难啊你们是怎么考场切掉的啊
首先可以想一下，如果没有k的限制，这题怎么做？
相信你们肯定能看出来是挡板法裸题：m个物品分给n个人，每个人至少一个。
就是$C_{m-1}^{n-1}$呗。(如果每个人可以没有就是$C_{n+m-1}^{n-1}$)
但是就这玩意我考场都打了半个小时的表才推出来
上面这个柿子在这道题里可以表示为“至少有0个城市不满足条件的方案数”
显然范围太大了，里面不合法的情况要容斥掉。那么至少有一个的呢？
先选出一个城市，然后在建设队里选出k个先分给已经选出来的那个，再把剩下的建设队分给所有城市，每个城市至少一个。这样一定可以保证之前选出的那个不合法。所以方案数就是$C_n^1 imes C_{m-k-1}^{n-1}$
之后同理，至少有i个城市不满足条件的方案数就是$C_n^i imes C_{m-i*k-1}^{n-1}$，枚举i逐步容斥奇减偶加即可。
#include<cstdio> #include<iostream> #include<cstring> #define re register using namespace std; typedef long long ll; const ll mod=998244353; const int N=1e7+5; ll n,m,K,fac[N]; ll qpow(ll a,ll b,ll mod) { ll res=1; a=a%mod; while(b) { if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; } ll C(ll x,ll y) { if(x<y)return 0; return fac[x]*qpow(fac[y],mod-2,mod)%mod*qpow(fac[x-y],mod-2,mod)%mod; } ll lucas(ll x,ll y) { if(!y)return 1; return C(x%mod,y%mod)*lucas(x/mod,y/mod)%mod; } int main() { scanf("%lld%lld%lld",&n,&m,&K); if(n==m) { puts("1"); return 0; } if(n>m) { puts("0"); return 0; } fac[0]=1; for(re int i=1;i<=m;i++) fac[i]=fac[i-1]*1LL*i%mod; ll ans=0; for(re int i=0;i<=n;i++) { if(m-i*K-1<=0)break; ll res=lucas(n,1LL*i)*lucas(m-1LL*i*K-1LL,n-1LL)%mod; if(!(i&1))ans+=res,ans%=mod; else ans-=res,ans=(ans+mod)%mod; } cout<<ans<<endl; return 0; }
B.轰炸行动
理解题意要正确，只要两个城市联通就不能一起炸，不管直接还是间接联通。
毕竟考场上像我一样理解对题意还不会做的垃圾太少了
如果没有环，显然答案就是图上最长链长度。因为一条链上每次一定只能炸一个点，不在一条链上的点可以并列炸。
有环也一样，直接缩点跑拓扑求最长链即可。注意此时更新每条链长度不是+1，而是+scc's size。
(现在想起来，我当时似乎也理解错题了，不过不是联通性。当时以为城市被炸了一次就废了原来连着它的边就断了，我真是yy能手23333)
#include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<queue> #include<algorithm> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f; } const int N=1000005; int n,m; int to[N<<1],nxt[N<<1],head[N],tot,ans[N]; void add(int x,int y) { to[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } int dfn[N],low[N],st[N],vis[N],top,ind,scc,size[N],bel[N],deg[N],maxx[N]; vector<int> g[N]; void tarjan(int x) { dfn[x]=low[x]=++ind; vis[x]=1;st[++top]=x; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]); else if(vis[y])low[x]=min(low[x],dfn[y]); } if(dfn[x]==low[x]) { scc++;int now=0; do { now=st[top--]; vis[now]=0; bel[now]=scc; size[scc]++; } while(now!=x); } } queue<int> q; int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(); add(x,y); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int x=1;x<=n;x++) for(int i=head[x];i;i=nxt[i]) if(bel[to[i]]!=bel[x]) g[bel[x]].push_back(bel[to[i]]),deg[bel[to[i]]]++; for(int i=1;i<=scc;i++) if(!deg[i])q.push(i),ans[i]=size[i]; while(!q.empty()) { int x=q.front(); q.pop();int sz=g[x].size(); for(int i=0;i<sz;i++) { int y=g[x][i]; ans[y]=max(ans[y],ans[x]+size[y]); if(!(--deg[y]))q.push(y); } } cout<<*max_element(ans+1,ans+1+scc)<<endl; return 0; }
C.石头剪刀布
这么好的题给我做真是焚琴煮鹤，弃了弃了。与其抄std还不如等撑过联赛再说。