生成树计数-基尔霍夫定理

http://vfleaking.blog.163.com/blog/static/1748076342013112523651955/

https://www.cnblogs.com/GerynOhenz/p/4450417.html

http://blog.csdn.net/werkeytom_ftd/article/details/60766200

 

找规律

BZOJ1228

这个SG规律真难找,找了半天也找不出最后看了题解。

这个规律不是O(1)的,是O(log)的。

SG[i/2][j/2]->SG[i][j]

int GetSG(int n,int m){
    if((n&1)&&(m&1)) return 0;
    if(!(n&1)&&!(m&1)) return GetSG(n/2,m/2)+1;
    return (n&1)?GetSG((n+1)/2,m/2)+1:GetSG(n/2,(m+1)/2)+1;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int tmp[500010],ts,mex,sg[555][555];
int main(){
	FOR(t,2,60)
		FOR(j,1,t-1){
			int i=t-j;
			ts=0;
			FOR(k,1,i-1) tmp[++ts]=sg[k][i-k];
			FOR(k,1,j-1) tmp[++ts]=sg[k][j-k];
			sort(tmp+1,tmp+ts+1);
			ts=unique(tmp+1,tmp+ts+1)-tmp-1;
			mex=-1;
			FOR(k,1,ts)
				if (tmp[k]==mex+1) ++mex;
			sg[i][j]=mex+1;
		}
	FOR(i,1,30){
		FOR(j,1,30) printf("%d ",sg[i][j]);
		puts("");
	}
	return 0;
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3288

欧拉函数前缀积。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=1e9+7;
int n,phi[1000010],p[1000010],pr;
LL ans;
bool u[1000010];
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
void getp(){
	phi[1]=1;
	FOR(i,2,n){
		if (!u[i]){p[++pr]=i;phi[i]=i-1;}
		FOR(j,1,pr){
			if (i*p[j]>n) break;
			u[i*p[j]]=1;
			if (i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
			else phi[i*p[j]]=phi[i]*phi[p[j]];
		}
	}
}
int main(){
	cin>>n;
	getp();
	ans=1;
	FOR(i,1,n) ans=ans*phi[i]%MO;
	cout<<ans<<endl;
	return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=1e9+7;
int a[1010][1010],n,k;
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
LL det(){
	LL ans=1;
	FOR(i,1,n){
		k=0;
		FOR(j,i,n)
			if (a[j][i]!=0){k=j;break;}
		if (!k) return 0ll;
		if (i!=k){
			FOR(j,1,n) swap(a[i][j],a[k][j]);
			ans=-ans;
		}
		LL t=pw(a[i][i],MO-2);
		FOR(j,i+1,n)
			if (a[j][i]!=0){
				LL w=-t*a[k][i]%MO;
				FOR(k,i,n) (a[j][k]+=a[i][k]*w)%=MO;
			}
	}
	FOR(i,1,n) ans=ans*a[i][i]%MO;
	return ans;
}
int main(){
	cin>>n;
	FOR(i,1,n)
		FOR(j,1,n)
			a[i][j]=__gcd(i,j);
	cout<<det()<<endl;
	return 0;
}

生成树计数-prufer

https://www.cnblogs.com/dirge/p/5503289.html

BZOJ1005

确定每个点度数后容易求出有多少种不同的无根树。

https://loj.ac/problem/6044

硬点一些点作为奇层点,一些点作为偶层层,方案数为C(n-1,k-1)。

令S(x,y)表示左边x个点右边y个点的二分图的生成树计数。

ans=C(n-1,k-1)*S(k,n-k)

考虑用prufer推S(x,y):

最后剩下的两个点肯定一个是左边的,一个是右边的。

因为我们已经确定了左边x个点的标号和右边y个点的标号,所以我们进行求prufer序列这个操作的时候,每次删掉的点是哪一个是确定的,只要考虑写入prufer的数是哪个,如果是删除左边,那么prufer中新增的数有y-1种可能,如果是删除右边,那么prufer中新增的数有x-1种可能,所以S(x,y)=x^(y-1)*y^(x-1)。

https://loj.ac/submission/52865

KMP

http://codeforces.com/contest/631/submission/33833481

最小圆覆盖

http://blog.csdn.net/commonc/article/details/52291822

BZOJ2823

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const double eps=1e-6;
struct Point{
	double x,y;
	Point(){}
	Point(double X,double Y){x=X;y=Y;}
	Point operator - (const Point & A) const{
		return Point(x-A.x,y-A.y);
	}
}P[1000010];
int n;
struct Circle{
	Point o;
	double r;
}C;
int sgn(double x){
	if (fabs(x)<eps) return 0;
	else if (x>0) return 1;
	else return -1;
}
double dis(Point A,Point B){
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
bool IN(Point P,Circle C){
	return (sgn(dis(P,C.o)-C.r)<=0);
}
Circle get1(Point A,Point B){
	Circle t;
	t.o.x=(A.x+B.x)/2,t.o.y=(A.y+B.y)/2;
	t.r=dis(A,B)/2;
	return t;
}
Point rev(Point P){
	return Point(P.y,-P.x);
}
Circle get2(Point A,Point B,Point C){
	Circle O;
	Point P1=Point((A.x+B.x)/2,(A.y+B.y)/2);
	Point Q1=rev(B-A);
	Point P2=Point((A.x+C.x)/2,(A.y+C.y)/2);
	Point Q2=rev(C-A);
	double b=(Q1.x*P1.y-Q1.x*P2.y+P2.x*Q1.y-P1.x*Q1.y)/(Q2.y*Q1.x-Q2.x*Q1.y);
	double a;
	if (sgn(Q1.x)!=0) a=(P2.x+Q2.x*b-P1.x)/Q1.x;
	else a=(P2.y+Q2.y*b-P1.y)/Q1.y;
	O.o.x=P1.x+Q1.x*a;
	O.o.y=P1.y+Q1.y*a;
	O.r=dis(O.o,A);
	return O;
}
int main(){
	scanf("%d",&n);
	FOR(i,1,n) scanf("%lf%lf",&P[i].x,&P[i].y);
	random_shuffle(P+1,P+n+1);
	C.o.x=P[1].x,C.o.y=P[1].y,C.r=0.0;
	FOR(i,2,n)
		if (!IN(P[i],C)){
			C.o=P[i],C.r=0.0;
			FOR(j,1,i-1)
				if (!IN(P[j],C)){
					C=get1(P[i],P[j]);
					FOR(k,1,j-1)
						if (!IN(P[k],C))
							C=get2(P[i],P[j],P[k]);
				}
		}
	printf("%.2f %.2f %.2f\n",C.o.x,C.o.y,C.r);
	return 0;
}

最小树形图

Surreal Number

利用Surreal Number解决一类不平等的组合游戏(Partisan Combinatorial Games)

https://wenku.baidu.com/view/65b1a600a6c30c2259019ea8.html

http://www.matrix67.com/blog/archives/6333

待填坑

欧拉降幂

 

CF17D

直接套用公式

http://codeforces.com/contest/17/submission/33807003

 

BZOJ3884

一个数经过O(log)次求phi后变成1,然后套用公式递归求解。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
bool u[10000010];
int T,n,f[10000010],phi[10000010],pr,p[1000010];
LL pw(LL x,LL y,LL MO){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
void getp(){
	phi[1]=1;
	n=1e7;
	FOR(i,2,n){
		if (!u[i]){p[++pr]=i;phi[i]=i-1;}
		FOR(j,1,pr){
			if (i*p[j]>n) break;
			u[i*p[j]]=1;
			if (i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
			else phi[i*p[j]]=phi[i]*phi[p[j]];
		}
	}
}
LL cal(int n){
	if (f[n]!=-1) return f[n];
	return f[n]=pw(2,cal(phi[n])+phi[n],n);
}
int main(){
	scanf("%d",&T);
	getp();
	memset(f,-1,sizeof(f));
	f[1]=0;
	while (T--){
		scanf("%d",&n);
		printf("%lld\n",cal(n));
	}
	return 0;
}

CF906D

因为经过O(log)次phi变成1,所以同样递归求解即可。

http://codeforces.com/contest/906/submission/33807499

三分答案

对于一个在某处x最优,其它地方离x越近越优的函数,可以三分求出x。

考虑当前三分区间[l,r]

令p=l+(r-l)/3,q=r-(r-l)/3

如果p比q优,那么[l,r]->[l,q],否则[l,r]->[p,r]

(易证)

 

CF101246J

三分距离差,求值(一定有个不动点)。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<complex>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int n,w,a[555];
double p,q,l,r;
double cal(double o){
	double cst=1e9;
	FOR(W,1,n){
		double t=0.0;
		FOR(i,1,n) t+=fabs(a[W]+(i-W)*o-a[i]);
		if (t<cst) cst=t,w=W;
	}
	return cst;
}
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
	scanf("%d",&n);
	FOR(i,1,n) scanf("%d",&a[i]);
	l=0.0,r=30000.0;
	FOR(rp,1,100){
		p=l+(r-l)/3;
		q=r-(r-l)/3;
		if (cal(p)<cal(q)) r=q;
		else l=p;
	}
	printf("%.10f\n",cal(r));
	FOR(i,1,n) printf("%.10f ",a[w]+(i-w)*r);
	return 0;
}

还有一种姿势叫做三分套三分。

BZOJ1857

CF891E

令人境界飙升的数数题?

首先答案=初始乘积-最终乘积的期望。(易证)

这样写出指数型生成函数的形式后可以ntt做到O(nklogk)。

然后我想到了最终答案的式子应该是这样一些东西xabc+y(ab+ac+bc)+z(a+b+c)+w,就是说不同的系数只有O(n)个,只要通过某些方式获得系数就做完了?

系数可能有规律?不会会啊。。

喵了题解,里面写到了子集DP的做法,然后把接下来的做法自行YY出来了。

大概就是说把DP式子写出来后发现直接可以算每项到第k步的系数,做完了。

总结:因为期望很好加减,所以把状态用子集表示就很好转移。之后就比较显然了?

其实DP只是某种脑子里想的时候用来推出系数的途径罢了,如果会找规律就更棒了?

其实当n一定是时候,系数是关于k的多项式?可能把多项式插出来也可以?

http://codeforces.com/contest/891/submission/33239888