#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ALL(x) (x).begin(),(x).end()
#define ll long long
#define ull unsigned long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 2005;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll sum[maxn];
int n,m,q,num;
int head[maxn],dis[maxn],h[maxn],PrePoint[maxn],PreEdge[maxn];
vector<int> mcost;
struct node
{
int u,v,f,w,nxt;
}edge[maxn];
inline void addedge(int x,int y,int f,int z)
{
edge[num].u=x;
edge[num].v=y;
edge[num].f=f;
edge[num].w=z;
edge[num].nxt=head[x];
head[x]=num++;
}
void add(int u,int v,int w,int c)
{
addedge(u,v,w,c);
addedge(v,u,0,-c);
}
int MCMF(int s,int t)
{
int ansflow=0;
rep(i,1,n) h[i] = 0;
while(1)
{
priority_queue<pii_>q;
rep(i,1,n) dis[i] = inf;
dis[s]=0;
q.push(make_pair(0,s));
while(q.size()!=0)
{
pii_ p=q.top();q.pop();
if(-p.fi!=dis[p.se]) continue;
if(p.se==t) break;
for(int i=head[p.se];i!=-1;i=edge[i].nxt)
{
int nowcost=edge[i].w+h[p.se]-h[edge[i].v];
if(edge[i].f>0&&dis[edge[i].v]>dis[p.se]+nowcost)
{
dis[edge[i].v]=dis[p.se]+nowcost;
q.push(make_pair(-dis[edge[i].v],edge[i].v));
PrePoint[edge[i].v]=p.se;
PreEdge[edge[i].v]=i;
}
}
}
if(dis[t]==inf) break;
for(int i=1;i<=n;i++) h[i]+=dis[i];
int nowflow=inf;
for(int now=t;now!=s;now=PrePoint[now])
nowflow=min(nowflow,edge[PreEdge[now]].f);
for(int now=t;now!=s;now=PrePoint[now])
edge[PreEdge[now]].f-=nowflow,
edge[PreEdge[now]^1].f+=nowflow;
ansflow+=nowflow;
mcost.pb(h[t]);
}
return ansflow;;
}
int main()
{
//fastio();
ll u,v,c;
while(~scanf("%d%d",&n,&m)){
rep(i,1,n) head[i] = -1;
num = 2;
mcost.clear();
int s = 1,t = n;
rep(i,1,m){
u = read();
v = read();
c = read();
add(u,v,1,c);
}
int maxflow = MCMF(s,t);
sort(ALL(mcost));
//for(int x:mcost) show1(x);
int sz = mcost.size();
rep(i,1,sz) sum[i] = sum[i-1] + mcost[i-1];
int q = read();
while(q--){
u = read();v = read();
if(u*maxflow<v) printf("NaN\n");
else{
int L = 1,R = sz,pos;
while(L<=R){
int mid = (L+R)>>1;
if(u*mid >= v) pos = mid,R=mid-1;
else L = mid+1;
} //show1(pos);
ll a = u*sum[pos-1];
ll o = (v-u*(pos-1)) * (sum[pos] - sum[pos-1]); //show2(a,o);
a = a+o;
ll g = gcd(a,v);
a /= g, v /= g;
printf("%lld/%lld\n",a,v);
}
}
}
return 0;
}
J - Easy Integration
$\int_0^1(x-x^2)^ndx=\frac{(n!)^2}{(2n+1)!}$ 。可以oeis/wolframalpha/分部积分。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
const ll N=2e6+10;
int n;
ll fac[N],inv[N];
void init()
{
fac[0]=1,inv[1]=1;
for(int i=1;i<N;i++)
fac[i]=fac[i-1]*i%mod;
for(int i=2;i<N;i++)
inv[i]=inv[mod%i]*(mod-mod/i)%mod;
inv[0]=1;
for(int i=1;i<N;i++)
inv[i]=inv[i-1]*inv[i]%mod;
}
int main()
{
init();
while(~scanf("%d",&n))
printf("%lld\n",fac[n]*fac[n]%mod*inv[2*n+1]%mod);
return 0;
}
比赛总结与反思
2020-2021/teams/wangzai_milk/20200712比赛记录.txt · 最后更改: 2020/07/16 15:15 由 wzx27
