acm代码模版

875619330 贡献于2013-11-12

作者 xiong  创建于2012-06-06 01:30:27   修改者我的电脑  修改于2013-10-11 07:16:04字数22262

文档摘要:数论数三角形(递推)/*设最大边长为x的三角形有c(x)个,跟三角形的定义两边之和大于第三边有x<y+z变形下的x-y<z<x;当y=1时无解,当y=2时只有一个解z=x-1,知道y=x-1时又x-2个解,所以共有(x-1)(x-2)/2个解,由于题意中不能存在y=z的解所以y=z这部分解,当x/2+1至x-1才存在y=z的可能.
关键词:

 数论 数三角形(递推) /* 设最大边长为x的三角形有c(x)个,跟三角形的定义两边之和大于第三边有x #include using namespace std; __int64 f[1000010]; void Init() { __int64 i;//用int定义结果Wrong answer,不定义__int64计算过程中会溢出 f[1]=0; f[2]=0; f[3]=0; for(i=4;i<=1000000;i++) f[i]=f[i-1]+((i-1)*(i-2)/2-(i-1)/2)/2; } int main() { Init(); int n; while(cin>>n,n>=3) printf("%I64d\n",f[n]); return 0; } 数论 容斥原理+bfs 题目大意:在一个n*m的网格放k个想同的石子,每个格子最多放一块,都要放玩,求第一行、最后一行、第一列、最后一列、都得有石子的种数 直接求太麻烦了,运用容斥原理设集合S、A(第一行没有石子)、B(第一列没有石子)、C(最后一行没有石子)、D(最后一列没有石子) 设题目要求的结合为E(第一行、最后一行、第一列、最后一列、都得有石子) 设A'为A的补集,设A&B为A跟B的交集(数学符号懒得找,就用这种表示了) 那么根据容斥原理 E=A'&B'&C'&D'=S-(A+B+C+D)+(A&B+A&C+A&D+B&C+B&D+C&D)-(A&B&C+A&B&D+A&C&D+B&C&D)+A&B&C&D 用dfs做容斥原理 AC代码: #include #include #include using namespace std; #define Max 550 #define MOD 1000007 int c[Max][Max]; int map[5]={0,1,2,3,4}; int vis[5]; int n,m,k,num,temp; void Init() { memset(c,0,sizeof(c)); int i,j; for(i=0;i>t; Case=0; while(t--) { Case++; cin>>n>>m>>k; sum=c[n*m][k]; memset(vis,false,sizeof(vis)); for(i=1;i<=4;i++) { num=0; temp=(i%2?-1:1); dfs(0,i,1,0); sum=(sum+MOD+num)%MOD; } printf("Case %d: %d\n",Case,sum); } return 0; } 欧几里得/扩展欧几里得/模线性方程组(中国剩余定理 以及mod不互质的情况) /***********欧几里得算法**************/ 辗转相除法求最大公约数。GCD(a,b)=GCD(b,a mod b)稍微证明一下: (参考:算法导论)证明的思路是大致是这样的: 证明 GCD(a,b) | GCD(b,a mod b) 并且 GCD(b,a mod b) | GCD(a,b) 先证GCD(a,b) | GCD(b,a mod b):设 d=GCD(a,b),则d|a 并且 d|b那么 a=r+kb (k为整数)也就是说 (a mod b) 是a和b的线性组合, 所以有d|(a mod b)因为 d|b 并且 d|(a mod b) 所以 d|GCD(b,a mod b)也就是 GCD(a,b) | GCD(b,a mod b)类似的,GCD(b,a mod b) | GCD(a,b) //递归 int gcd(int a,int b) { return b?gcd(b,a%b):a; } //非递归 int gcd(int a,int b) { int t;    while(b)    {     t=a;a=b;b=t%b;    }    return a; } /**********扩展欧几里得算法*************/ 用这个算法可以求 X mod b=m 这种模线性方程(求的是X的通解,整数解)。 变形一下,得 X+by=m,其中y为整数。通常写成 ax+by=m 的形式,然后解得x的通解,进而得到X=ax的通解。 其实就是在求GCD(a,b)的同时把解出满足 ax+by=m 的(x,y)通解。首先,a和b的线性组合能表示的最 小的正整数为GCD(a,b),也就是说ax+by=m,m的最小值为GCD(a,b)ax+by=m有整数解的前提是 GCD(a,b)|m 设d=GCD(a,b)用EXGCD(待会儿再来讲这个函数) 可以解出ax+by=d的一个整数解(x‘,y’),则(x‘*m/d,y’*m/d)就是ax+by=m的一个整数解。 令(x0,y0)=(x‘*m/d,y’*m/d)那么,有(x0+b/d*t,y0-a/d*t)是ax+by=m的通解。 证一下: 由已知得ax0+by0=m将(x,y)=(x0+b/d*t,y0-a/d*t)代入ax+by, 化简一下就有ax0+ab/d*t+by0-ab/d*t=ax0+by0=m证毕。 所以只要得到ax+by=m的一组解,就可以用(x,y)=(x0+b/d*t,y0-a/d*t)得到满足要求的解。 一般要求的是满足条件的最小正整数x。 可以用x=(x0 mod (b/d) + (b/d) ) mod (b/d) 如果求的是X mod b=m的最小正整数解,则X=(ax mod b + b) mod b。这么写是为了避免a为负数的情况下造成的错误。 然后,大家肯定很纳闷这个(x',y')到底怎么求,接下来就讲的是用EXGCD 解 ax+by=d的一个特解的求法。 原来说过的,GCD(a,b)=GCD(b,a mod b)。 那么有ax+by=d………………………………………………(1) a'x'+b'y'=d……………………………………(2) 其中(a',b')=(b,a mod b)可设 a=bk+t……………………………………(3) 将(3)代入(1),有(bk+t)x+by=d整理, 得b(kx+y)+tx=d………………………………(4) 对比(2)和(4),且用(a',b')替换(b,t), 有a'x' + b'y' =da'(kx+y) + b'x =d对比两式的系数, 有(x',y')=(kx+y,x)整理下,有(x,y)=(y',x'-ky') 也就是说,当深层的(x',y')解出后,就能推出外层的(x,y)边界条件是 b=0时 d=a 那么 ax+by=d 的解(x,y)=(1,0)用EXGCD就能递归地解得 ax+by=d 的一个特解 (x',y') int Extended_Euclid(int a,int b,int &x,int &y) { if(!b) {x=1;y=0;return a;} int d = Extended_Euclid(b,a%b,x,y); int t = x; x=y; y=t-(a/b)*y; return d; } 二元一次不定方程求解:ax+by=c gcd(a,b)|c是有整数解的充分必要条件 通过欧几里德扩展定理Extende_Euclid(a,b,x,y)求出一组特殊解:x0=x*c/gcd(a,b)、y0=y*c/gcd(a,b) 通解X=x0+t*b/gcd(a,b)、Y=y0-t*a/gcd(a,b);(t为正整数) MODULAR-LINEAR_EQUATION_SOLVER(a, b, n) (d,x’,y’) ← EXTENDED-EUCLID(a, n) if (d | b) then x0 ← x’(b/d)mod n for i ← 0 to d-1 do print(x0 + i(n / d)) mod n else print “no solution” 求解模线性方程:ax=b (mod n) 通过欧几里德扩展定理Extended_Euclid(a,n,x,y)求出一个特解:x0=x*b/gcd(a,n)%n; 通解X=x0+i*n/gcd(a,n); /**************线性同余方程**************/ 问题是,求满足以下模线性方程组的 X(通常求的是X的最小正整数解) X mod m1=r1 X mod m2=r2 ... ... ... X mod mn=rn其中,mi之间两两互质线性同余方程中特殊的(用中国剩余定理) m=m1*m2*.......*mn; Mi=m/mi; X=M1’M1*b1+M2’M2*b2+.......+Mn’*Mn*bn; 其中Mi’为乘率: Mi’*Mi=1(mod mi); 可以通过Extended_Euclid(mi,M,x,y)得出Mi’=y; int Extended_Euclid(int a, int b, int & x, int & y) { if (b==0) { x=1; y=0; return a; } int d = Extended_Euclid(b, a%b, x, y); int t = x; x = y; y = t - a / b * y; return d; } int china( int n) { int i, d, x, y, M, sum, n = 1; Sum=0; for (i = 0; i < n; i++) n *= m[i]; for (i = 0; i < n; i++) { M= n / m[i]; d = Extended_Euclid(m[i], M, x, y); sum = (sum+ y * m * b[i]) % n; } if (sum > 0) return sum; else return (sum + n); } 用中国剩余定理有一个前提条件,就是mi之间是两两互质的!如果mi并不满足两两互质的话。。怎么解呢? /**************一般模线性方程*******************/ 同样是求这个东西。。 X mod m1=r1 X mod m2=r2 ... ... ... X mod mn=rn 首先,我们看两个式子的情况 X mod m1=r1……………………………………………………………(1) X mod m2=r2……………………………………………………………(2) 则有 X=m1*k1+r1………………………………………………………………(*) X=m2*k2+r2那么 m1*k1+r1=m2*k2+r2整理, 得m1*k1-m2*k2=r2-r1令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1),原式变成ax+by=m熟悉吧? 解线性同余方程组(中国剩余定理中的两两不互质的情况) int Extended_Euclid(int a,int b,int &x,int &y) { if(!b) {x=1;y=0;return a;} int d = Extended_Euclid(b,a%b,x,y); int t = x; x=y; y=t-(a/b)*y; return d; } int CRT(int n,int &LCM) { int i,x,y; int d,c,t,mm=m[0],bb=b[0]; for(i=1;i #include using namespace std; #define Max 4000000 __int64 s[Max+5],f[Max+5],phi[Max+5]; int prime[Max/10]; bool flag[Max+5]; void Init() { int i,j,num=0; memset(flag,1,sizeof(flag)); phi[1]=1; for(i=2;i<=Max;i++)//欧拉筛选 { if(flag[i]) { prime[num++]=i; phi[i]=i-1; } for(j=0;j>n,n) printf("%I64d\n",s[n]); return 0; } 数论 高次幂取模 题目大意:求一个数((((a^b)^c)^d)^e)..... Mod m的值 幂太huge了,上界是1000^1000^1000^1000^1000^1000^1000^1000^1000,暴力快速幂模肯定行不通,因为幂是多少都难的计算。有公式a^x=a^(x%phi(c)+phi(c)) (mod c),所以可以用递归方法求解。 AC代码: #include #include #include using namespace std; int phi[10010]; int f[20],n; string m; void init() { int i; for(i=2;i<=10000;i++) phi[i]=0; phi[1]=1; for(i=2;i<=10000;i++) if(!phi[i]) for(int j=i;j<=10000;j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } int montgomery(int a,int b,int c) { int t=1; while(b) { if(b%2) t=t*a%c; b/=2; a=a*a%c; } return t; } int dfs(int now,int mod) { if(now==n-1) { return f[now]%mod; } int t=dfs(now+1,phi[mod]); int ans=montgomery(f[now],t+phi[mod],mod); return ans; } int main() { init(); int i,ret,kase=1; while(cin>>m,m!="#") { ret=0; for(i=0;i>n; for(int i=0;i #include #include #include using namespace std; bool flag[50010]; int prime[8000]; bool r[1000010]; int num; void Init() { int i,j; num=0; memset(flag,true,sizeof(flag)); flag[1]=flag[0]=0; for(i=2;i<50000;i++) { if(flag[i]) prime[num++]=i; for(j=0;j>a>>b) { if(a==1) a++;//a=1的情况 min=20000000; max=0; memset(r,true,sizeof(r)); for(i=0;ii-up) { min=i-up; mina=up; minb=i; } if(max #include #include #include #include using namespace std; typedef long long LL; set s; LL X,R,N; LL Extended_Euclid(LL a,LL b,LL &x,LL &y)//欧几里德扩展定理 { LL d,t; if(b==0) { x=1;y=0;return a; } d=Extended_Euclid(b,a%b,x,y); t=x; x=y; y=t-a/b*y; return d; } void Mod_Line_Equation_Solve(LL a,LL b,LL n)//模线性方程求解 { LL x,y,d,t,lcm; d=Extended_Euclid(a,n,x,y); if(b%d==0) { x=x*b/d; x=(x%(n/d)+n/d)%(n/d); t=a*x-b/2; lcm=a/d*n; for(;t=0 && t*t%N==X) s.insert(t);//符合条件的解插入set容器 } } } int main() { LL i,top,Case=0; while(cin>>X>>N>>R && !(X==0 && N==0 && R==0)) { Case++; printf("Case %d:",Case); s.clear(); top=sqrt(N+0.5); for(i=1;i<=top;i++)//枚举所有的A*B=n的情况 { if(N%i==0) { Mod_Line_Equation_Solve(i,2*R,N/i); Mod_Line_Equation_Solve(N/i,2*R,i); } } set::iterator it; for(it=s.begin();it!=s.end();it++) printf(" %lld",*it); printf("\n"); } return 0; } 数论 解模方程a^x=b (mod n) 题目大意:已知N,K,R和B个格子的位置求最小可能的M。 #include #include #include #include #include #include using namespace std; typedef long long LL; const int MOD=100000007; const int Max=1000; int N,M,B,K,R,x[Max],y[Max]; set > bset; LL mult_mod(LL a,LL b) { LL t=0; a%=MOD; while(b) { if(b&1) t=(t+a)%MOD; b>>=1; a=(a<<1)%MOD; } return t; } LL pow_mod(LL a,LL b) { LL t=1; a%=MOD; while(b) { if(b&1) t=mult_mod(t,a); b>>=1; a=mult_mod(a,a); } return t; } int Extended_Euclid(int a,int b,int &x,int &y) { int d,t; if(b==0) { x=1;y=0;return a; } d=Extended_Euclid(b,a%b,x,y); t=x; x=y; y=t-a/b*y; return d; } int inv(int a) { int x,y,d; d=Extended_Euclid(a,MOD,x,y); x=(x%MOD+MOD)%MOD; return x; } int log_mod(int a,int b) { int c,v,e=1,i; c=(int)sqrt(MOD+0.5); v=inv(pow_mod(a,c)); map xx; xx[1]=0; for(i=1;if(x1) (0=p2>=......>=pn 证明:若pi #include using namespace std; typedef long long LL; int prime[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}; LL n,ans,Max; void dfs(LL sum,LL num,LL k,LL t) { if(sum>Max) {Max=sum;ans=num;} if(sum==Max && num14) return ; LL temp=num; for(int i=1;i<=t;i++) { if(temp*prime[k]>n) break; temp*=prime[k]; dfs(sum*(i+1),temp,k+1,i); } } int main() { while(~scanf("%lld",&n)) { ans=n;Max=0; dfs(1,1,0,50); printf("%lld\n",ans); } return 0; } 数论 miller_rabin + pollard_rho模版 #include #include #include #include #include #define MAXN 100000 using namespace std; typedef unsigned long long LL; LL fac[MAXN],cnt,G,L,m,p; LL min(LL a,LL b) { return a>=1; } return ans; } LL pow_mod(LL a,LL b,LL mod) { LL d=1; a%=mod; while(b) { if(b&1) d=mult_mod(d,a,mod); a=mult_mod(a,a,mod); b>>=1; } return d%mod; } bool witness(LL a,LL n) { LL u=n-1,t=0; while((u&1)==0) { u>>=1; t++; } LL x,x0=pow_mod(a,u,n); for(LL i=1; i<=t; i++) { x=mult_mod(x0,x0,n); if(x==1&&x0!=1&&x0!=(n-1)) return true; x0=x; } if(x!=1) return true; return false; } bool miller_rabin(LL n) { if(n==2) return true; if(n<2||!(n&1)) return false; for(int j=1; j<=8; j++) { LL a=rand()%(n-1)+1; if(witness(a,n)) return false; } return true; } LL pollard_rho(LL n,LL c) { LL i=1,k=2,d,x=2,y=2; while(true) { i++; x=(mult_mod(x,x,n)+c)%n; d=gcd(y-x,n); if(d!=1&&d!=n) return d; if(x==y) return n; if(i==k) { y=x; k<<=1; } } } void find_fac(LL n,LL c) { if(miller_rabin(n)||n<=1) { fac[cnt++]=n; return; } LL p=pollard_rho(n,c); while(p>=n) p=pollard_rho(p,c--); find_fac(p,c); find_fac(n/p,c); } void dfs( LL step,LL num) { if(step==cnt||num>p) { if(num<=p&&num>m) m=num; return; } dfs(step+1,num*fac[step]); dfs(step+1,num); } int main() { srand(time(NULL)); while(scanf("%I64u%I64u",&G,&L)!=EOF) { cnt=0; find_fac(L/G,181); sort(fac,fac+cnt); LL i=0,t=0; while(i #include #include using namespace std; vector v[100005]; int sg[100005]; bool vis[100005]; int mex(int n) { int i; if(sg[n]!=-1) return sg[n]; sg[n]=0; vis[n]=true; for(i=0;i>t; memset(vis,false,sizeof(vis)); while(t-- && scanf("%d",&n)) { memset(sg,-1,sizeof(sg)); for(i=1;i<=n;i++) v[i].clear(); for(i=1;i#include#include#include#include using namespace std; vector v; int sg[300]; int Max(int a,int b) { return a>b?a:b; } int mex(int n) { bool flag[300]; int i,t; if(sg[n]!=-1) return sg[n]; if(n==0) return sg[n]=0; memset(flag,false,sizeof(flag)); //i位置放X,它左边两个跟右边两个都为禁区,谁再放X谁输 for(i=1;i<=n;i++) { //一个游戏分成两个子游戏 t=(mex(Max(0,i-3))^mex(Max(0,n-i-2))); flag[t]=true; } for(i=0;i<300;i++) if(!flag[i]) break; return sg[n]=i; } bool is_oi(string s) //判断先手是否已经胜利 { for(int i=0;i=1&&s[i-1]=='X')||(i>=2&&s[i-2]=='X')||(i+1>t; while(t--) { v.clear(); cin>>s; solve(s); if(v.size()==0) //先手没有必胜的情况,肯定必败。 cout<<"LOSING"< using namespace std; typedef long long LL; LL power[55]; int gcd(int a,int b) { return b?gcd(b,a%b):a; } int main() { int n,i,t; LL a,b; power[0]=1; while(cin>>n>>t) { for(i=1;i<=n;i++) power[i]=power[i-1]*t; a=0; for(i=0;i#include#include using namespace std; int main() { int t,i,j,f[30],n,flag; char s[30]; bool vis[30]; scanf("%d",&t); while(t--) { scanf("%s",s); memset(vis,false,sizeof(vis)); memset(f,0,sizeof(f)); for(i=0;i<26;i++) { if(!vis[i]) { j=i;n=0; do{ vis[j]=true; j=s[j]-'A'; n++; }while(i!=j); f[n]++;//长度为n的循环个数+1 } } flag=1; for(i=2;i<=26;i+=2)//长度n为偶数的循环能否配对 { if(f[i]%2) { flag=0;break; } } if(flag) printf("Yes\n"); else printf("No\n"); } return 0; } uva 11077 Find the Permutations 题目大意:给出1-n的一个排列,可以通过一系列的交换变成{1,2,3,....,n}。比如{2,1,4,3}需要两次交换(1和2,3和4),{4,2,3,1}只需交换一次(1和4),{2,3,4,1}需要三次,而{1,2,3,4}本身一次都不需要。给定n和k,统计有多少个排列至少需要交换k次才能变成{1,2,3....n}。 分析:不难发现单个元素不需要交换,2个元素要交换一次,3个元素要交换两次,.....,c个元素的循环要交换c-1次。这样,如果排列p的循环节为x个,则总的交换次数为n-x次。有了上述结论,就不难进行递推了。设f(i,j)表示满足“至少需要交换j次才能变成{1,2,3,...,i}”的排列个数,则f(i,j)=f(i-1,j)+f(i-1,j-1)*(i-1),因为元素i要么自己形成一个循环,要么加入前面任意一个循环的任意一个位置(i-1个)。边界f(1,0)=1,其他f(1,j)=0。 #include#include#include using namespace std; typedef unsigned long long LL; LL f[30][30]; int main() { int i,j; memset(f,0,sizeof(f)); f[1][0]=1; for(i=2;i<22;i++) { for(j=0;j>i>>j,i+j) printf("%llu\n",f[i][j]); return 0; } 组合数学 递推矩阵幂模 题目大意:f(n)=a1*f(n-1)+a2*f(n-2)+.....+ad*f(n-d) #include#include#include using namespace std; #define Max 20 typedef long long LL; struct Matrix { LL a[Max][Max]; int n; }; Matrix Matrix_mult_mod(Matrix A,Matrix B,int m) { int i,j,k; Matrix C; C.n=A.n; memset(C.a,0,sizeof(C.a)); for(i=1;i<=A.n;i++) { for(j=1;j<=A.n;j++) { for(k=1;k<=A.n;k++) { C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%m; } } } return C; } Matrix Matrix_pow_mod(Matrix A,int n,int m) { Matrix t; int i,j; t.n=A.n; memset(t.a,0,sizeof(t.a)); for(i=1;i<=A.n;i++) t.a[i][i]=1; for(i=1;i<=A.n;i++) for(j=1;j<=A.n;j++) A.a[i][j]%=m; while(n) { if(n&1) t=Matrix_mult_mod(t,A,m); n>>=1; A=Matrix_mult_mod(A,A,m); } return t; } void deal(int d,int n,int m) { int i,j; LL dd[Max],dd1[Max]; Matrix A; A.n=d; memset(A.a,0,sizeof(A.a)); for(i=1,j=2;j<=d;i++,j++) A.a[i][j]=1; for(j=d,i=1;i<=d;i++,j--) scanf("%ll",&A.a[d][j]); for(i=1;i<=d;i++) scanf("%ll",dd+i); A=Matrix_pow_mod(A,n-d,m); for(i=1;i<=d;i++) { dd1[i]=0; for(j=1;j<=d;j++) dd1[i]=(dd1[i]+A.a[i][j]*dd[j])%m; } printf("%ll\n",dd1[d]); } int main() { int d,n,m; while(scanf("%d %d %d",&d,&n,&m),d+n+m) deal(d,n,m); return 0; } 概率与数学期望 题目大意:给一个正整数N,每次可以在不超过N的素数中随机选择一个P,如果P是N的约数,则把N变成N/p,否则N不变,问平均情况下需要多少次随机选择,才能把N变成1? 分析:根据数学期望的线性和全期望公式可以为每个状态列出一个方程,例如: f(x)=1+f(6)*1/3+f(3)*1/3+f(2)*1/3 等式右边的最前面的“1”是指第一次转移,而后面的几项是后续的转移,用全期望公式展开,一般地,设不超过x的素数有p个,其中有g个是x的因子,则 f(x)=1+f(x)*(1-g/p)+Σf(x/y)/p 边界f(1)=0。移项后整理得 f(x)=(Σf(x/y)+p)/g 因为x/y#include#include using namespace std; const int Max=1000005; int prime[100000],Num; bool flag[Max],vis[Max]; double f[Max]; void Init() { int i,j; Num=0; for(i=2;i #include #include using namespace std; int n; char str[10005][12]; struct node { bool flag; node *child[11]; }; void Build(int k,node *p) { int i,j,len; len=strlen(str[k]); for(i=0;ichild[str[k][i]-'0']==NULL) { node *t=new node; t->flag=0; for(j=0;j<10;j++) t->child[j]=NULL; p->child[str[k][i]-'0']=t; p->flag=1; } p=p->child[str[k][i]-'0']; } return ; } bool Find(int k,node *p) { int i,len; len=strlen(str[k]); for(i=0;ichild[str[k][i]-'0']!=NULL) { p=p->child[str[k][i]-'0']; if(i==len-1&&p->flag) return 1; if(p->flag==0) break; } } return 0; } 数位dp 题目大意:区间各个位数之和能被10整除的个数 #include #include #include #include #include #include using namespace std; const int MAX=22; __int64 dp[MAX][10];//分别代表长度为i位数和mod 10为j的个数 int digit[MAX]; void digit_dp() {//计算每长度为i为的数mod 10 == 0的个数 dp[0][0]=1; for(int i=1;i=1;--i) { for(int j=0;j

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档