G
容斥完之后发现要求一个m次多项式的n次方，并且得到\(n\times m\)项。
原本很sb地直接套了个多项式LnExp上去（即使知道大概率过不了），然后狂TLE。。。
其实但凡从常数的角度分析，Exp的常数有14倍，已经比\(log(m)\)大了，所以不如写快速幂，然后写着就会发现卷积的长度总和其实是\((n\times m),(n\times m)/2,...=O(n\times m)\)的，就随便过了。
当时不管常数还是效率都没认真分析，就直接按着常规方法套板子，而忽视了具体题目的数据范围特性，就卡了很久，很不应该！
点击查看代码
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N=(1<<23)+5,P=998244353,G[2]={3,(P+1)/3};
void inc(int& x,int y){
x+=y;
if(x>=P) x-=P;
if(x<0) x+=P;
}
int sum(int x,int y){
x+=y;
if(x>=P) x-=P;
if(x<0) x+=P;
return x;
}
void mul(int& x,int y){
x=1ll*x*y%P;
}
int prd(int x,int y){
return 1ll*x*y%P;
}
inline int fpw(int a,int x){
int s=1;
for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
return s;
}
int rv[N],gp[2][N],iv[N],fc[N],fv[N];
void init(int n){
fc[0]=1;
for(int i=1;i<n;i++) iv[i]=fpw(i,P-2),fc[i]=1ll*fc[i-1]*i%P;
fv[n-1]=fpw(fc[n-1],P-2);
for(int i=n-2;~i;i--) fv[i]=1ll*fv[i+1]*(i+1)%P;
for(int p=0;p<2;p++){
for(int i=1;i<n;i<<=1){
gp[p][i]=1;
int t=fpw(G[p],(P-1)/(i<<1));
for(int j=i+1;j<(i<<1);j++) gp[p][j]=1ll*gp[p][j-1]*t%P;
}
}
}
int Cmb(int n,int m){
return 1ll*fc[n]*fv[m]%P*fv[n-m]%P;
}
inline void dft(int* a,int n,int p){
for(int i=0;i<n;i++) if(i<rv[i]) swap(a[i],a[rv[i]]);
for(int i=1;i<n;i<<=1){
for(int j=0;j<n;j+=(i<<1)){
for(int k=0;k<i;k++){
int &A=a[i+j+k],&B=a[j+k],t=1ll*gp[p][i+k]*A%P;
A=B-t; if(A<0) A+=P;
B=B+t; if(B>=P) B-=P;
}
}
}
if(p) for(int i=0;i<n;i++) a[i]=1ll*a[i]*iv[n]%P;
}
inline int Rev(int m){
int p=0,n=1;
while(n<m) n<<=1,p++;
for(int i=0;i<n;i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(p-1));
return n;
}
inline void poly_mul(int m,int* A,int* B,int* C){
int n=Rev(m);
dft(A,n,0); dft(B,n,0);
for(int i=0;i<n;i++) C[i]=1ll*A[i]*B[i]%P;
dft(C,n,1);
fill(C+m,C+n,0);
}
void print(char name[],int n,int* a){
printf("%s n=%d\n",name,n);
for(int i=0;i<n;i++) cout<<a[i]<<" "; puts("");
}
int n,m,A[N],g[N],f[N];
int main() {
cin>>n>>m;
init(1<<22);
for(int i=0;i<=m;i++){
A[i]=prd(Cmb(m,i),prd(fc[m],fv[m-i]));
}
f[0]=1;
//print("A",n*m+1,A);
int x=n;
int len=m+1,sum=1;
for(;x;x>>=1){
if(x&1){
for(int i=0;i<len;i++) g[i]=A[i];
sum+=len;
poly_mul(sum,f,g,f);
for(int i=0;i<(sum<<1);i++) g[i]=0;
//print("f",len,f);
}
len<<=1;
int nn=Rev(len );
dft(A,nn,0);
for(int i=0;i<nn;i++) A[i]=1ll*A[i]*A[i]%P;
dft(A,nn,1);
fill(A+len,A+nn,0);
//print("A",len<<1,A);
}
//puts("");
//print("f",n*m+1,f);
int ans=0;
for(int i=0;i<=n*m;i++){
int s=prd(f[i],fc[n*m-i]);
// cout<<i<<" "<<f[i]<<" "<<s<<endl;
if(i&1) inc(ans,P-s);
else inc(ans,s);
}
cout<<ans<<endl;
return 0;
}
J
当时只发现它是个单峰的，枚举最小值及其位置之后可以判断，然后就一直陷在优化这个枚举判断的过程，发现不可做。
但这式子就是凸性的定义呀！甚至题目都把凸写上去了。。。发现这个之后就对右端点求个下凸壳，然后判断即可。
感觉是经典的，做法已经写在体面上了，然后还想偏，对自己很无语
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6e5+5;
const ll inf=1e12,P=998244353,V=(P+1)/2;
int n;
ll l[N],r[N];
struct vec{
ll x,y;
vec operator - (const vec& u){
return (vec){x-u.x,y-u.y};
}
friend ll cross (vec a,vec b){
return a.x*b.y-a.y*b.x;
}
void print(){
printf("x=%lld y=%lld\n",x,y);
}
};
vec q[N];
int t2;
void workR(){
for(int i=1;i<=n;i++){
scanf("%lld",&r[i]);
vec u=(vec){i,r[i]};
while(t2>1 && cross(q[t2]-q[t2-1],u-q[t2-1])<=0) t2--;
q[++t2]=u;
}
}
int main() {
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&l[i]);
workR();
for(int i=1,j=0;i<=n;i++){
if(j<t2 && i==q[j+1].x){
j++;
if(l[i]>q[j].y){
puts("No");
return 0;
}
continue;
}
vec u=(vec){i,l[i]};
if(cross(u-q[j],q[j+1]-q[j])<0){
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
K
这个题做法其实挺显然的，考虑枚举d，把区间平移一下，首项的方案数就是各个区间交的长度，所以要求的就是R最小与L最大，然后发现这两者肯定是分别根据d分成至多n段，每段由一个位置的值决定（和斜率优化类似），然后就把d分为分成\(O(n)\)个区间，每段里数一数就好。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6e5+5;
const ll inf=1e12,P=998244353,V=(P+1)/2;
int n;
ll l[N],r[N];
struct vec{
ll x,y;
vec operator - (const vec& u){
return (vec){x-u.x,y-u.y};
}
friend ll cross (vec a,vec b){
return a.x*b.y-a.y*b.x;
}
void print(){
printf("x=%lld y=%lld\n",x,y);
}
};
struct node{
ll l,r;
int d;
void print(){
printf("l=%lld r=%lld d=%d\n",l,r,d);
}
}a[N],b[N];
int t1,t2;
vec q[N];
ll floor(vec u){
if(u.y==0) return 0;
if(u.x<0) u.x=-u.x,u.y=-u.y;
if(u.y>0) return u.y/u.x;
return -((-u.y-1)/u.x+1);
}
ll up(vec u){
if(u.y==0) return 0;
if(u.x<0) u.x=-u.x,u.y=-u.y;
if(u.y>0) return (u.y-1)/u.x+1;
return -((-u.y)/u.x);
}
void workL(){
for(int i=1;i<=n;i++){
scanf("%lld",&l[i]);
vec u=(vec){i,l[i]};
while(t1>1 && cross(q[t1]-q[t1-1],u-q[t1-1])>=0) t1--;
q[++t1]=u;
}
a[t1+1].r=-inf-1;
for(int i=t1;i;i--){
//cout<<"i="<<i<<endl;
//q[i].print();
a[i].l=a[i+1].r+1;
if(i==1) a[i].r=inf;
else{
vec u=(vec){q[i-1].x-q[i].x,q[i-1].y-q[i].y};
a[i].r=floor(u);
}
a[i].d=q[i].x;
}
reverse(a+1,a+t1+1);
//for(int i=1;i<=t1;i++) a[i].print();
}
void workR(){
for(int i=1;i<=n;i++){
scanf("%lld",&r[i]);
vec u=(vec){i,r[i]};
while(t2>1 && cross(q[t2]-q[t2-1],u-q[t2-1])<=0) t2--;
q[++t2]=u;
}
b[0].r=-inf-1;
for(int i=1;i<=t2;i++){
b[i].l=b[i-1].r+1;
if(i==t2) b[i].r=inf;
else{
vec u=(vec){q[i+1].x-q[i].x,q[i+1].y-q[i].y};
b[i].r=floor(u);
}
b[i].d=q[i].x;
}
//for(int i=1;i<=t2;i++) b[i].print();
}
ll cnt(ll L,ll R){
return (L+R)%P*((R-L+1)%P)%P*V%P;
}
ll mod(ll x){
return (x%P+P)%P;
}
ll cal(vec u,ll L,ll R){
u.x=mod(u.x); u.y=mod(u.y);
if(L>R) return 0;
return ((R-L+1)%P*((u.y+1)%P)%P+P-u.x*cnt(L,R)%P)%P;
}
int main() {
cin>>n;
workL(); workR();
ll ans=0;
for(int i=1,j=1;i<=t1;i++){
if(b[j].r<a[i].l && j<=t2) j++;
while(b[j].l<=a[i].r && j<=t2){
//cout<<"i="<<i<<" j="<<j<<endl;
ll L=max(a[i].l,b[j].l),R=min(a[i].r,b[j].r);
//cout<<"L="<<L<<" R="<<R<<endl;
vec u=(vec){b[j].d-a[i].d,-l[a[i].d]+r[b[j].d]};
//u.print();
if(!u.x){
if(u.y>=0) (ans+=cal(u,L,R))%=P;
}
else{
if(u.x>0) R=min(R,floor(u));
else L=max(L,up(u));
(ans+=cal(u,L,R))%=P;
}
j++;
}
j--;
}
cout<<ans<<endl;
//cout<<inf%P*(inf%P)%P<<endl;
return 0;
}
M
缩完点之后是一个DAG最小链覆盖，但链是可以相交的，之前网上的做法都是暴力\(O(n^2)\)建图，但这题可能就是为了卡这个的。然后优化的做法其实也比较常规：拆点后每个点向对应的点连容量inf的边，再把原来\(u->v\)的容量改成inf，这样就相当于：原图中可达，就可以跑出一个流；并且有源点汇点边的流量限制，所以是正确的。
然后有点麻烦的事输出方案，就按着反向边dfs一个个流去找即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=1e9;
vector<int> a[N];
stack<int> stk;
bool vis[N],instk[N];
int dfn[N],low[N],col[N],w[N]; // co:染色结果，w:点权
vector<int> sz; // sz:第i个颜色的点数
int n,m,dcnt;//
void dfs(int x){ // Tarjan求强联通分量
vis[x]=instk[x]=1; stk.push(x);
dfn[x]=low[x]=++dcnt;
for(auto p:a[x]){
if(!vis[p])dfs(p);
if(instk[p])low[x]=min(low[x],low[p]);
}
if(low[x]==dfn[x]){
int t; sz.push_back(0); // 记录
do{
t=stk.top();
stk.pop();
instk[t]=0;
sz.back()+=w[t]; // 记录
col[t]=sz.size(); // 染色
}while(t!=x);
}
}
void getscc(){
fill(vis,vis+n,0);
sz.clear();
for(int i=1;i<=n;i++) if(!vis[i])dfs(i);
}
struct pii{
int u,v;
};
void shrink(){ // 缩点，在a里重构
vector<pii> tmp;
getscc();
for(int i=1;i<=n;i++) {
for (auto j: a[i]) if (col[i] != col[j]) {
pii u = {col[i], col[j]};
tmp.push_back(u);
}
}
n=sz.size();
for(int i=1;i<=n;i++){
a[i].clear();
w[i]=sz[i];
}
for(auto i:tmp){
a[i.u].push_back(i.v);
}
}
int fa[N];
int find(int u){
if(u==fa[u]) return u;
return fa[u]=find(fa[u]);
}
struct FLOW{
struct edge{int to,w,nxt;};
vector<edge> a; int head[N],cur[N];
int n,s,t;
queue<int> q; bool inque[N];
int dep[N];
void ae(int x,int y,int w){ // add edge
//cout<<"ae:"<<x<<" "<<y<<" "<<w<<endl;
a.push_back({y,w,head[x]});
head[x]=a.size()-1;
}
bool bfs(){ // get dep[]
fill(dep,dep+n,inf); dep[s]=0;
copy(head,head+n,cur);
q=queue<int>(); q.push(s);
while(!q.empty()){
int x=q.front(); q.pop(); inque[x]=0;
for(int i=head[x];i!=-1;i=a[i].nxt){
int p=a[i].to;
if(dep[p]>dep[x]+1 && a[i].w){
dep[p]=dep[x]+1;
if(inque[p]==0){
inque[p]=1;
q.push(p);
}
}
}
}
return dep[t]!=inf;
}
int dfs(int x,int flow){ // extend
int now,ans=0;
if(x==t)return flow;
for(int &i=cur[x];i!=-1;i=a[i].nxt){
int p=a[i].to;
if(a[i].w && dep[p]==dep[x]+1)
if((now=dfs(p,min(flow,a[i].w)))){
a[i].w-=now;
a[i^1].w+=now;
ans+=now,flow-=now;
if(flow==0)break;
}
}
return ans;
}
bool is[N];
void init(int _n){
n=_n+1; a.clear();
fill(head,head+n,-1);
fill(inque,inque+n,0);
fill(is,is+n,0);
}
int solve(int _s,int _t,int _n){ // return max flow
s=_s,t=_t;
int ans=0;
while(bfs()) ans+=dfs(s,inf);
for(int e=head[s];e>=0;e=a[e].nxt) if(a[e^1].w) is[a[e].to]=1;
for(int e=head[t];e>=0;e=a[e].nxt) if(a[e].w){
int v=a[e].to,u=v;
while(1){
if(u>=1 && u<=_n && is[u]){
is[u]=0;
break;
}
int w=0,tmp=0;
for(int i=head[u];i>=0;i=a[i].nxt) if(i&1 && a[i].w){
w=a[i].to;
tmp=i;
break;
}
if(!w) break;
a[tmp].w--;
u=w;
}
//cout<<u<<" "<<v-_n<<endl;
// fa[find(u)]=find(v-_n);
}
return ans;
}
}flow;
void add(int x,int y,int w){flow.ae(x,y,w),flow.ae(y,x,0);}
// 先flow.init(n)，再add添边，最后flow.solve(s,t)
int ans[N];
int main(){
cin>>n>>m;
for(int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v),a[u].push_back(v);
int tot=n;
shrink();
//for(int i=1;i<=tot;i++) cout<<col[i]<<" "; puts("");
int S=0,T=n+n+1;
flow.init(T+1);
for(int i=1;i<=n;i++){
//cout<<"i="<<i<<endl;
add(S,i,1);
add(i+n,T,1);
add(i+n,i,inf);
for(auto j:a[i]) add(i,j+n,inf);
}
for(int i=1;i<=n;i++) fa[i]=i;
flow.solve(S,T,n);
int cnt=0;
for(int i=1;i<=tot;i++){
int u=find(col[i]);
if(!ans[u]) ans[u]=++cnt;
// cout<<col[i]<<" u="<<u<<endl;
printf("%d ",ans[u]);
}
puts("");
return 0;
}