T1：組合數問題
source：LOJ6353
很簡單，我的做法稍微有點不一樣：
考慮組合數的遞推式： C n m = C n − 1 m + C n − 1 m − 1 C_{n}^m=C_{n-1}^m+C_{n-1}^{m-1} Cnm=Cn−1m+Cn−1m−1
是以如果選出了一個數，那麼一定會先選它在組合數表格上的右邊和右上的
是以就先把最右邊一列加入一個set，然後每次選了一個數就把其左和左下的加入set（如果對應的可以選），并及時彈出set尾巴上的數
比大小用對數
Code：
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define pb push_back
#define mp make_pair
#define db double
#define ri register
#define fi first
#define se second
#define ite multiset<info>::iterator
#define mod 1000000007
#define eps 1e-8
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
return res*f;
}
inline int add(int x,int y){x+=y;if(x>=mod) x-=mod;return x;}
inline int dec(int x,int y){x-=y;if(x<0) x+=mod;return x;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline void inc(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline void Dec(int &x,int y){x-=y;if(x<0) x+=mod;}
inline void Mul(int &x,int y){x=1ll*x*y%mod;}
inline int ksm(int a,int b){int res=1;for(;b;b>>=1,a=mul(a,a)) if(b&1) res=mul(res,a);return res;}
const int N=1e6+5;
int fac[N],ifac[N];
inline void init(int n){
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
ifac[n]=ksm(fac[n],mod-2);
for(int i=n-1;i;i--) ifac[i]=mul(ifac[i+1],i+1);
}
inline int C(int n,int m){if(n<0 || m<0 || n<m) return 0;return mul(fac[n],mul(ifac[m],ifac[n-m]));}
db Lg[N];
struct info{
int x,y;
info(){}
info(int _x,int _y):x(_x),y(_y){}
friend inline bool operator < (const info &a,const info &b){
return (Lg[a.x]+Lg[b.y]+Lg[b.x-b.y]-Lg[a.y]-Lg[b.x]-Lg[a.x-a.y])>eps;
}
};
multiset<info>s;
map<pair<int,int>,int>m;
inline void file(){freopen("comb.in","r",stdin);freopen("comb.out","w",stdout);}
int main(){
Lg[0]=0.0;int ans=0;
for(int i=1;i<=1000000;i++) Lg[i]=Lg[i-1]+log2(i);
int n=read(),k=read(),K=k,cnt=0;
init(n);
for(int i=0;i<=n;i++) ++cnt,s.insert(info(n,i));
while(k--){
ite it=s.begin();info a=*it;
inc(ans,C(a.x,a.y));
if(it!=s.end()) {s.erase(it);m[make_pair(a.x,a.y)]=1;--cnt;}
if(a.x-1>=a.y){
if(m[make_pair(a.x,a.y+1)]==1){
++cnt;s.insert(info(a.x-1,a.y));
ite i=s.end();--i;
if(cnt>=K && i!=s.end()) s.erase(i),--cnt;
}
}
if(m[make_pair(a.x,a.y-1)]==1){
++cnt;s.insert(info(a.x-1,a.y-1));
ite i=s.end();--i;
if(cnt>=K && i!=s.end()) s.erase(i),--cnt;
}
}
cout<<ans;
return 0;
}
T2：字元串
source：LOJ6517
就是在trie樹上插入和删除一個串，詢問一些奇怪的資訊
直接暴力插入可以拿部分分，加個莫隊可以做到 O ( n n l o g n ) O(n\sqrt nlogn) O(nn
logn)，log來自set，要查詢前驅後繼
考慮用一個連結清單，但是連結清單不支援插入和删除，那就改成復原莫隊即可
Code：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
return res*f;
}
const int N=3e5+5;
int A,B,C;
int bel[N];
struct Q{
int l,r,id;
inline bool operator < (const Q &a)const{return bel[l]==bel[a.l]?r>a.r:l<a.l;}
}q[N];
struct info{
int l,r,p;
info(){}
info(int _l,int _r,int _p):l(_l),r(_r),p(_p){}
}sta[N];
int top=0;
int n,m,v[N],g[N],L,bg[N],ed[N],len[N],pt[N];
int sqr,cnt,head[N],pre[N],suf[N];
ll ans=0,fans[N],all;
inline ll S(int x){return 1ll*x*(x+1)/2;}
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline void back(){
while(top){
int l=sta[top].l,r=sta[top].r,p=sta[top].p;
ans-=S(r-l-1),ans+=S(p-l-1),ans+=S(r-p-1);
pre[r]=p,suf[l]=p;--top;
}
}
inline void del(int p){
int l=pre[p],r=suf[p];
ans-=S(p-l-1)+S(r-p-1),ans+=S(r-l-1);
sta[++top]=info(l,r,p);
pre[r]=l;suf[l]=r;
}
int a[N];
inline void build(){for(int i=1,j=0;i<=L+1;i++) if(pt[i]) suf[j]=i,pre[i]=j,ans+=S(i-j-1),j=i;}
namespace trie{
struct node{int son[26],sum,dep;}tr[N];
int tot=0;
inline void ins(int id,int kd){
int now=0;kd*=v[id];
for(int i=bg[id];i<=ed[id];i++){
if(!tr[now].son[a[i]]) tr[now].son[a[i]]=++tot,tr[tot].dep=tr[now].dep+1;
now=tr[now].son[a[i]];
int pre=(tr[now].sum>0 && 1ll*B*tr[now].sum+1ll*A*tr[now].dep>=C);
tr[now].sum+=kd;
int nxt=(tr[now].sum>0 && 1ll*B*tr[now].sum+1ll*A*tr[now].dep>=C);
if(!pre && nxt){++pt[g[tr[now].dep]];}
if(pre && !nxt){--pt[g[tr[now].dep]];if(!pt[g[tr[now].dep]]) del(g[tr[now].dep]);}
}
}
}
using namespace trie;
char s[N];
int num=0;
int main(){
n=read();A=read();B=read();C=read();
for(int i=1;i<=n;i++) v[i]=read();
for(int i=1;i<=n;i++){
scanf("%s",s+1);
len[i]=strlen(s+1);
bg[i]=num+1;
for(int j=1;j<=len[i];j++) a[++num]=s[j]-'a';
ed[i]=num;
L=max(L,len[i]);
}
for(int i=1;i<=L;i++) g[i]=read();
int m=read();pt[L+1]=1;
for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sqr=ceil(1.0*num/sqrt(m));
bel[1]=1;all=S(L);
for(int i=2,j=1;i<=n;i++){
bel[i]=bel[i-1];
if(ed[i]-bg[j]+1>sqr) ++bel[i],j=i;
}
cnt=bel[n];
sort(q+1,q+m+1);
for(int i=1;i<=n;i++) if(!head[bel[i]]) head[bel[i]]=i;
for(int i=1,j,pos=1;i<=cnt;i++){
ans=0;
for(j=head[i];j<=n;j++) ins(j,1);
build();
for(j=n;pos<=m && bel[q[pos].l]==i;pos++){
while(j>q[pos].r) ins(j,-1),--j;
top=0;
for(int k=head[i];k<q[pos].l;k++) ins(k,-1);
fans[q[pos].id]=all-ans;
for(int k=head[i];k<q[pos].l;k++) ins(k,1);
back();
}
while(j>=head[i]) ins(j,-1),--j;
}
for(int i=1;i<=m;i++){
ll Gcd=gcd(all,fans[i]);
cout<<fans[i]/Gcd<<"/"<<all/Gcd<<"\n";
}
return 0;
}
T3：cir
原題還要掃描線計算幾何（或者KD-tree），然而zxyoi怒噴資料卡精度（最小的圓的面積小于精度）并表示不值得一寫，我就去把簡化版的cot3找來做了（為了偷懶 ）
![Incredible Chess（尼姆博弈）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)