题目来源：2014-2015 ACM-ICPC, Asia Xian Regional Contest
F. Color
第一道二项式反演。。膜题解: https://www.cnblogs.com/wmrv587/p/6681953.html
#include<bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9 + 7;
using namespace std;
ll q_pow(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
ll n,m,k,inv[1000007];
ll C(ll n,ll m){ll t=1;
for(ll i=n-m+1;i<=n;++i)t=(t*i)%mod;
for(ll i=1;i<=m;++i)t=(t*inv[i])%mod;
return t;
}
ll a(ll x){return ((x%mod)*q_pow(x-1,n-1)%mod)%mod;}
int T,K;
int main() {
scanf("%d",&T);
for(int i=1;i<=1e6;++i)inv[i]=q_pow(i,mod-2);
while(T--){
scanf("%lld%lld%lld",&n,&m,&k);
ll ans=0,w=1,Cki=1;if(k%2)w=-1;
for(int i=0;i<=k;++i,w=-w){
ans = (ans%mod + (w*(Cki%mod*a(i)%mod)%mod+mod)%mod)%mod;
Cki=(((Cki%mod)*(k-i)%mod)*inv[i+1]%mod)%mod;
}
ans = (ans*C(m,k))%mod;
printf("Case #%d: %lld
",++K,ans);
}
}
C. The Problem Needs 3D Arrays
将有逆序关系的点相连，题目转化为，求最大密度子图。回去复习论文。。
update:今天看了一下，马上就想起来了。。。于是写了一下。。。有点伤感。。。按论文第一种方式建二分图。。。T了？，，于是学了第二种建图。。。精度炸了？倒查了3个小时。。。inf开大了，导致大数，吞小数。。。计方老师。。。终于过了第一个样例。。。T在第二个？查了半小时。。。数组开太大了，还用的memset。。。，改掉成WA了？于是把eps调小了点。。。当我准备改long double时。过了。。。真的是好感伤。。。就读过几篇论文。。。被考到了。。。还不会。。。知道了还写炸。。。没救了。没救了。
#include <bits/stdc++.h>
#define pb(x) push_back(x)
#define LD long double
typedef long long ll;
const int maxn = 510000;
const int maxm = 2100000;
const double eps = 1e-7;
using namespace std;
double inf;
int T,n,a[111];
struct node{
int x,y;
node(){}
node(int a,int b){x=a;y=b;}
};
vector<node> ee;
struct edge{int e,nxt;LD w;}E[maxm];
int h[maxn],cc;
void add(int u,int v,LD w){
E[cc].e=v;E[cc].w=w;E[cc].nxt=h[u];h[u]=cc;++cc;
E[cc].e=u;E[cc].w=0;E[cc].nxt=h[v];h[v]=cc;++cc;
}
int dd[maxn],q[maxn],st,ed;
int bfs(){
int l=0,r=0;for(int i=0;i<=n+1;++i)dd[i]=0;
q[r]=st;++r;dd[st]=1;
while(l<r){
int u=q[l];++l;
for(int i=h[u];~i;i=E[i].nxt){
int v=E[i].e;
if(!dd[v]&&E[i].w>=eps){
dd[v]=dd[u]+1;
q[r]=v;++r;
if(v==ed)return 1;
}
}
}
return 0;
}
LD dfs(int u,LD fl) {
if(u==ed)return fl;
LD s=fl,t;
for(int i=h[u];~i;i=E[i].nxt){
int v=E[i].e;
if(dd[v]==dd[u]+1&&E[i].w>=eps&&s>=eps){
t=dfs(v,min(E[i].w,s));
s-=t;
E[i].w-=t;E[i^1].w+=t;
if(s<eps)return fl;
}
}
if(abs(s-fl)<eps) dd[u]=0;
return fl-s;
}
LD dinic(){
LD ans=0;
while(bfs())ans+=dfs(st,inf);
return ans;
}
int m,d[111];
void build(LD g){
for(int i=0;i<=n+1;++i)h[i]=-1;cc=0;
st=0;ed=n+1;inf=m*3+m*n+m+2*g+10000.0;
for(int i=0;i<m;++i){
add(ee[i].x,ee[i].y,1.0);
add(ee[i].y,ee[i].x,1.0);
}
for(int i=1;i<=n;++i){
add(st,i,m*1.0);
add(i,ed,m*1.0+2.0*g-d[i]);
}
}
LD solve(LD g) {
build(g);
return (n*m*1.0-dinic());
}
int K=0;
int main() {
scanf("%d",&T);
while(T--) {ee.clear();
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]),d[i]=0;
for(int i=2;i<=n;++i)
for(int j=1;j<i;++j)if(a[j]>a[i]){
ee.pb(node(i,j));
++d[i];++d[j];
}
m=ee.size();
LD l=0, r = m, mid;
int tt=0;
while(r-l>=eps){
mid = (l+r)/2.0; LD t = solve(mid);
//printf("%f %f
",(double)mid,(double)t);
if(t>eps)l=mid;
else r=mid;
}
printf("Case #%d: %f
",++K,(double)l);
}
return 0;
}
//5
//5
//3 4 2 5 1