洛希极限
发现对于 $ (x,y) $ 的转移只可能从 $ (x-1,k) $ 或者 $ (k,y-1) $ 来
每行每列维护单调队列即可
至于求出每个点最左最右转移边界 用并查集维护即可
code
#include<iostream>
#include<algorithm>
#define Sakura int
#define Re register ll
#define ll long long
#define _ putchar(' ')
#define el putchar('\n')
#define fre(x,y) freopen(#x".in","r",stdin),freopen(#y".out","w",stdout);
using namespace std;
const ll mod=1e9+7;
const ll maxn=2e3+10;
const ll maxq=5e5+10;
inline ll read() {
ll x=0,f=0;char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
inline void ot(ll x) {
if(x<0) putchar('-'),x=-x;
if(x>9) ot(x/10);putchar(x%10|48);
}
ll T;
ll n,m,q;
ll le[maxn][maxn],ri[maxn][maxn],dw[maxn][maxn],up[maxn][maxn];
struct Mat {
ll r1,c1,r2,c2;
}mat[maxq];
inline bool cmp1(const Mat &A,const Mat &B) {
return A.r1<B.r1;
}
inline bool cmp2(const Mat &A,const Mat &B) {
return A.c1<B.c1;
}
struct node {
ll ans,sum;
inline void out() {
ot(ans),_,ot((sum+mod)%mod),el;
}
}f[maxn][maxn],ans;
inline node operator + (const node &A,const node &B) {
if(A.ans==B.ans) return { A.ans,(A.sum+B.sum)%mod };
return A.ans>B.ans?A:B;
}
inline bool operator < (const node &A,const node &B) {
return A.ans<B.ans;
}
struct Que {
node q[maxn];
ll head=1,tail,w[maxn],cnt[maxn];
inline void init() {
head=1,tail=0;
for(Re i=0;i<=max(n,m);++i) w[i]=cnt[i]=0;
}
inline void push(ll x,node y) {
while(head<=tail&&q[tail]<y) (cnt[q[tail].ans]-=q[tail].sum)%=mod,tail--;
q[++tail]=y;
(cnt[y.ans]+=y.sum)%=mod;
w[tail]=x;
}
node query(ll x) {
while(head<=tail&&w[head]<x) (cnt[q[head].ans]-=q[head].sum)%=mod,head++;
return { q[head].ans+1,cnt[q[head].ans] };
}
}r[maxn],c[maxn];
inline void clear() {
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j) {
le[i][j]=ri[i][j]=dw[i][j]=up[i][j]=0;
f[i][j]={1,1};
}
ans={0,0};
}
inline ll get1(ll x,ll y) {
if(!ri[x][y]) return x;
return ri[x][y]=get1(ri[x][y],y);
}
inline ll get2(ll x,ll y) {
if(!up[x][y]) return y;
return up[x][y]=get2(x,up[x][y]);
}
inline void solve() {
n=read(),m=read(),q=read();
clear();
for(Re i=1;i<=q;++i) mat[i].r1=read(),mat[i].c1=read(),mat[i].r2=read(),mat[i].c2=read();
sort(mat+1,mat+q+1,cmp1);
for(Re i=1;i<=q;++i)
for(Re y=mat[i].c1+1;y<=mat[i].c2;++y)
for(Re x=mat[i].r1+1;x<=mat[i].r2;)
if(!ri[x][y]) {
le[x][y]=mat[i].r1;
ri[x][y]=mat[i].r2+1;
++x;
}
else x=get1(x,y);
sort(mat+1,mat+q+1,cmp2);
for(Re i=1;i<=q;++i)
for(Re x=mat[i].r1+1;x<=mat[i].r2;++x)
for(Re y=mat[i].c1+1;y<=mat[i].c2;)
if(!up[x][y]) {
dw[x][y]=mat[i].c1;
up[x][y]=mat[i].c2+1;
++y;
}
else y=get2(x,y);
// for(Re i=1;i<=n;++i) {
// for(Re j=1;j<=m;++j)
// ot(le[i][j]),_;
// el;
// }
// for(Re i=1;i<=n;++i) {
// for(Re j=1;j<=m;++j)
// ot(ri[i][j]),_;
// el;
// }
// for(Re i=1;i<=n;++i) {
// for(Re j=1;j<=m;++j)
// ot(dw[i][j]),_;
// el;
// }
// for(Re i=1;i<=n;++i) {
// for(Re j=1;j<=m;++j)
// ot(up[i][j]),_;
// el;
// }
for(Re i=1;i<=max(n,m);++i) r[i].init(),c[i].init();
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j) {
r[i].push(j,f[i][j]);
c[j].push(i,f[i][j]);
if(i<n&&j<m&&le[i+1][j+1]&&dw[i+1][j+1]) {
// ot(i),_,ot(j),el,r[i].query(dw[i+1][j+1]).out(),c[j].query(le[i+1][j+1]).out(),el;
f[i+1][j+1]=f[i+1][j+1]+r[i].query(dw[i+1][j+1]);
f[i+1][j+1]=f[i+1][j+1]+c[j].query(le[i+1][j+1]);
if(f[i][j].ans+1==f[i+1][j+1].ans) (f[i+1][j+1].sum-=f[i][j].sum)%=mod;
}
ans=ans+f[i][j];
}
// for(Re i=1;i<=n;++i) {
// for(Re j=1;j<=m;++j)
// f[i][j].out();
// el;
// }
ans.out();
}
Sakura main() {
fre(roche,roche);
T=read();
while(T--) solve();
}
特立独行的图
发现最多有一个三元环 即 $ -\frac{L}{2} ,0,\frac{L}{2} $ 的情况 把 $ 0 $ 去掉之后 就形成了一个二分图
我们先强行把没有与其他点连边的点扔到左部点里去
根据连边方式可知左部每个点所连的右部点构成的集合 它们之间的包含关系构成一条链 右部同样
我们将左部内点按度数排序 显然度数越大的点对应的 $ a_i $ 绝对值越大
在左部按度数从小到大的顺序遍历每个点并对其赋值 同样从小到大 对其相连的右部点依次赋值为其减去 $-\frac{L}{2} $ 每个右部点只赋一次值
这部分主要看代码
正确性：发现之前如果一个右部点此时被第一次遍历到了 那么它与往后所有的左部点都有边 因为左部点往后被赋的值逐渐递增 所以它与后面每一个左部点的 $ a_i $ 之差都大于 $ -\frac{L}{2} $
左部点按照度数从大到小也好构造
code
#include <algorithm>
#include <bitset>
#include <vector>
#define Sakura int
#define Re register ll
#define ll long long
#define _ putchar(' ')
#define el putchar('\n')
#define fre(x,y) freopen(#x".in","r",stdin),freopen(#y".out","w",stdout);
using namespace std;
const ll mod=1e9+7;
const ll maxn=1e3+10;
inline ll read() {
ll x=0,f=0;char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
inline void ot(ll x) {
if(x<0) putchar('-'),x=-x;
if(x>9) ot(x/10);putchar(x%10|48);
}
vector<int> G[maxn];
bitset<maxn> bit[maxn];
int T,n,m;
int p1,p2,p3;
int col[maxn],dg[maxn];
int a[maxn],cnt;
int ans[maxn],tim;
bool ju;
inline void clear() {
for(Re i=1;i<=n;++i) G[i].clear(),dg[i]=0,col[i]=0,bit[i].reset(),ans[i]=0;
p1=p2=p3=0;
ju=false;
cnt=0;
tim=0;
}
inline void add(int x,int y) {
G[x].emplace_back(y);
bit[x][y]=true;
}
inline void add_edge(int x,int y) {
add(x,y);
add(y,x);
dg[x]++,dg[y]++;
}
void dfs(int u) {
if(ju) return;
for(auto v:G[u])
if(col[v]) {
if(col[v]==col[u]) {
ju=true;
return;
}
}
else {
col[v]=col[u]^1;
dfs(v);
}
}
inline bool cmp(int A,int B) {
return dg[A]<dg[B]||B==p2;
}
inline void solve() {
n=read(),m=read();
clear();
while(m--) add_edge(read(),read());
for(Re i=1;i<=n;++i)
for(auto j:G[i])
if(j>i)
for(auto k:G[j])
if(k>j)
if(bit[i][k])
col[i]=col[j]=col[k]=1;
for(Re i=1;i<=n;++i)
if(col[i])
if(!p1) p1=i;
else if(!p2) p2=i;
else if(!p3) p3=i;
else {
puts("No");
return;
}
if(p1) {
if(dg[p2]==2) swap(p1,p2);
if(dg[p3]==2) swap(p1,p3);
col[p2]=col[p3]=0;
}
for(Re i=1;i<=n;++i)
if(!col[i]) {
col[i]=2;
dfs(i);
}
if(ju) {
puts("No");
return;
}
for(Re i=1;i<=n;++i) if(col[i]==2) a[++cnt]=i;
if(p1) {
for(auto v:G[p3])
if(col[v]==3) {
swap(p2,p3);
break;
}
if(dg[p2]!=n-cnt||dg[p3]!=cnt+1) {
puts("No");
return;
}
ans[p3]=-1e9;
}
sort(a+1,a+cnt+1,cmp);
for(Re i=1;i<cnt;++i)
if((bit[a[i]]|bit[a[i+1]])!=bit[a[i+1]]) {
puts("No");
return;
}
for(Re i=1;i<=cnt;++i) {
for(auto v:G[a[i]])
if(ans[v]==0)
ans[v]=++tim-1e9;
ans[a[i]]=++tim;
}
ans[p2]=1e9;
ans[p1]=0;
puts("Yes");
ot(2e9),_;
for(Re i=1;i<=n;++i) ot(ans[i]),_;el;
}
Sakura main() {
fre(graph,graph);
T=read();
while(T--) solve();
}
玩游戏
首先放结论
因为所有人都是老六都会采取最优策略 所以如果你翻出来的比之前最大的还大 一定会被别人换走 所以不如直接选前面的最大的
如果之前最大的也比没出现的小 那肯定不交换 因为不管后面怎么跟你交换你肯定仍然大于此时前面的最大值
那么什么情况下第 $ i $ 个位置的人会留下呢？第 $ i $ 张牌是后面 $ n-i+1 $ 张牌中最小的那一张的时候 概率为 $ \frac{1}{n-i+1} $
请注意 这与第 $ i $ 个人选取的什么操作无关 因为第 $ i $ 张牌必然会亮出来
那么总期望就是 $ \sum_{i=1}^{n} \frac{1}{n} $ 即 $ H(n) $
考虑我们要对其做 $ k $ 次前缀和
等价于对多项式 $ \sum_{i=1}^{\infty} \frac{1}{i} x^i $ 做 $ k+1 $ 次前缀和
先求导 得 $ \sum_{i=0}^{\infty} x^i = \frac{1}{1-x} $ 再积分 得 $ -\ln(1-x) $
最终答案就是 $ \frac{-\ln(1-x)}{(1-x)^{k+1}} $ 的第 $ n $ 项系数
接下来的推导直接放joke博客
注：$ \lim_{n \to \infty} H(n) - \ln n = \gamma $ ，其中 $ \gamma $ 为欧拉常数
code
#include <cmath>
#include <sstream>
#define Sakura int
#define Re register ll
#define ll long long
#define ldb long double
#define _ putchar(' ')
#define el putchar('\n')
#define fre(x,y) freopen(#x".in","r",stdin),freopen(#y".out","w",stdout);
using namespace std;
const ll maxn=1e6+10;
const ldb gm=0.57721566490153286060651209;
inline ll read() {
ll x=0,f=0;char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
inline void ot(ll x) {
if(x<0) putchar('-'),x=-x;
if(x>9) ot(x/10);putchar(x%10|48);
}
ll n,k;
ldb h[maxn];
char out[100];
inline ldb H(ll n) {
return log(n)+gm;
}
ldb s(ll k,ll n) {
if(k==0) return n<=1e6?h[n]:H(n);
ldb res=1;
for(Re i=1;i<=k;++i) res=res/i*(i+n);
return s(k-1,n+1)/k*(n+1)-res/k;
}
Sakura main() {
fre(game,game);
stringstream ss;
ss.unsetf(ios::fixed);
ss.setf(ios::scientific);
ss.precision(9);
k=read(),n=read();
for(Re i=1;i<=1e6;++i) h[i]=h[i-1]+(ldb)1.0/i;
ss << s(k,n);
ss >> out;
for (ll i = 0; ; ++i)
if (out[i] == '+')
{
if (out[i + 3] < '0')
{
out[i + 3] = out[i + 2];
out[i + 2] = out[i + 1];
out[i + 1] = '0';
}
break;
}
cout << out;
}