hdu1465 不容易系列之一 （错排公式）
虽说大家知道 还是把这个小小说一下
来自百度百科
1 #include <iostream> 2 #include<cstdio> 3 #include<stdlib.h> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 #include<stack> 10 #include<set> 11 using namespace std; 12 #define LL long long 13 LL f[22]; 14 int main() 15 { 16 int i,n; 17 f[1] = 0; 18 f[2] = 1; 19 while(cin>>n) 20 { 21 for(i = 3; i <= n ; i++) 22 f[i] = (i-1)*(f[i-1]+f[i-2]); 23 cout<<f[n]<<endl; 24 } 25 return 0; 26 }
poj1850 Code
以前做过 没印象了。。
仔细想一下 也是很简单的 一个字母的所有排列就是C（n,1),二个字母C（n,2),三个字母C(n,3)........依次
具体的就类似于逐位了 注意下细节就OK了
1 #include <iostream> 2 #include<cstdio> 3 #include<stdlib.h> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 #include<stack> 10 #include<set> 11 using namespace std; 12 #define LL long long 13 char s[12]; 14 LL c[30][15]; 15 void init() 16 { 17 int i,j; 18 for(i = 0 ;i <= 26 ;i++) 19 c[i][0] = 1; 20 for(i = 1 ; i <= 26 ;i++) 21 for(j = 1 ; j <= 10 ; j++) 22 c[i][j] = c[i-1][j-1]+c[i-1][j]; 23 } 24 int main() 25 { 26 int i,j,k; 27 init(); 28 while(cin>>s) 29 { 30 k = strlen(s); 31 if(k>1) 32 { 33 for(i = 0 ; i < k-1 ; i++) 34 if(s[i+1]<s[i]) break; 35 if(i!=k-1) {puts("0");continue;} 36 } 37 LL ans=0; 38 for(i = 1 ; i < k ;i++) 39 ans+=c[26][i]; 40 int t; 41 for(i = 0; i < k ;i++) 42 { 43 if(i!=0) 44 t = ‘z‘-s[i-1]-1; 45 else 46 t = 25; 47 //cout<<‘z‘-s[i]+1<<endl; 48 for(j = max((‘z‘-s[i]+1),k-i-1) ; j <= t ; j++) 49 { 50 //cout<<j<<endl; 51 ans+=c[j][k-i-1]; 52 } 53 } 54 ans++; 55 cout<<ans<<endl; 56 } 57 return 0; 58 }
poj2773 Happy 2006 二分+容斥原理
容斥原理可以明显的看的出 也算是模板题了
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 using namespace std; 11 #define N 10000000000 12 #define LL long long 13 int p[32],g; 14 LL sum=0; 15 int gcd(int a,int b) 16 { 17 return b==0?a:gcd(b,a%b); 18 } 19 void dfs(int num,LL y,int i,LL n) 20 { 21 y = p[i]*y; 22 if(num%2==0) sum-=n/y; 23 else sum+=n/y; 24 for(int j = i+1 ; j <= g ; j++) 25 dfs(num+1,y,j,n); 26 } 27 int main() 28 { 29 int m,k,i; 30 while(cin>>m>>k) 31 { 32 g = 0; 33 for(i = 2; i <= m ;i++) 34 { 35 if(m%i==0) p[++g] = i; 36 while(m%i==0) 37 { 38 m/=i; 39 } 40 } 41 if(m!=1) p[++g] = m; 42 LL low = 1,high = N,mid; 43 LL ans; 44 while(low<=high) 45 { 46 mid = (low+high)/2; 47 sum=0; 48 for(i = 1; i <= g; i++) 49 { 50 dfs(1,1,i,mid); 51 } 52 /*if(mid-sum==k) 53 { 54 while(gcd(mid,k)!=1)mid--; 55 break; 56 }*/ 57 if(mid-sum<k) low = mid+1; 58 else {high = mid-1;} 59 } 60 cout<<low<<endl; 61 } 62 return 0; 63 }
这跳骚很牛X 。。特别能跳
这个可以想到 可以跳出相差为一的 就是gcd(x1,x2,,....xn) = 1，具体我也不知道怎么证 我是以欧几里得猜的 ax+by = gcd(x,y) 有解
这个题求补集 把每一次的减去
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set> 10 using namespace std; 11 #define N 100000 12 #define LL __int64 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 int p[32]; 18 double ppow(int x,int n) 19 { 20 int i; 21 double s = 1; 22 for(i = 1; i <= n ;i++) 23 s*=x; 24 return s; 25 } 26 int main() 27 { 28 int i,j,n,m; 29 scanf("%d%d",&n,&m); 30 int g = 0; 31 int q = m; 32 for(i = 2 ; i*i <= m ;i++) 33 { 34 if(m%i==0) p[++g] = i; 35 while(m%i==0) 36 m/=i; 37 if(i>m) break; 38 } 39 if(m!=1) p[++g] = m; 40 double s = ppow(q*1.0,n); 41 for(i = 1 ; i < (1<<g) ; i++) 42 { 43 int o = 0,y=1; 44 for(j = 0 ; j < g ; j++) 45 { 46 if(i&(1<<j)) 47 { 48 o++; 49 y*=p[j+1]; 50 } 51 } 52 LL x = q/y; 53 if(o%2) s-=ppow(x,n); 54 else s+=ppow(x,n); 55 } 56 printf("%I64d\n",(LL)s); 57 return 0; 58 }
这个其实把最大公约数除去之后 求一下互质的个数 可能数据有点水吧 直接枚举每一个的与其互质的个数 然后加起来
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 #define LL __int64 10 #define N 100010 11 LL o[N]; 12 int p[22]; 13 LL init(int s1,int s2) 14 { 15 int i,j,e; 16 LL cnt = 0; 17 for(i = s1 ; i >= 2 ; i--) 18 { 19 int g = 0,x=i; 20 for(j = 2 ; j*j <= x ; j++) 21 { 22 if(x%j==0){p[++g] = j;} 23 while(x%j==0) x/=j; 24 } 25 if(x!=1) p[++g] = x; 26 int ans = i+s2-s1; 27 for(j = 1 ; j < (1<<g) ; j++) 28 { 29 int s = 0,y=1; 30 for(e = 0 ; e < g ; e++) 31 { 32 if(j&(1<<e)) 33 { 34 s++; 35 y*=p[e+1]; 36 } 37 } 38 if(s%2) 39 { 40 ans-=i/y; ans-=(s2/y-s1/y); 41 } 42 else {ans+=i/y;ans+=(s2/y-s1/y); 43 } 44 } 45 cnt += ans; 46 } 47 return cnt+s2-s1+1; 48 } 49 int main() 50 { 51 int k,a,b,c,d; 52 int t,kk=0; 53 cin>>t; 54 while(t--) 55 { 56 scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); 57 if(b>d) swap(b,d); 58 printf("Case %d: ",++kk); 59 if(k==0||b<k) 60 { 61 cout<<"0\n"; 62 continue; 63 } 64 cout<<init(b/k,d/k)<<endl; 65 } 66 return 0; 67 }
直接套模板
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdio> 5 #include<stdlib.h> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 int k[10],o[10],num[10]; 10 int c1[55],c2[55]; 11 bool f[10]; 12 int main() 13 { 14 int i,j,a,b,n,k,t,e; 15 cin>>t; 16 while(t--) 17 { 18 memset(o,0,sizeof(o)); 19 memset(f,0,sizeof(f)); 20 memset(c1,0,sizeof(c1)); 21 memset(c2,0,sizeof(c2)); 22 cin>>n>>k; 23 int g = 0; 24 for(i = 1; i <= k ;i++) 25 { 26 cin>>a>>b; 27 o[a]+=b; 28 if(!f[b]) 29 { 30 num[++g] = a; 31 } 32 } 33 for(i = 0 ; i <= num[1]*o[num[1]] &&i<=n; i += num[1]) 34 c1[i] = 1; 35 for(i = 2 ; i <= g ;i++) 36 { 37 for(j = 0 ; j <= n ; j++) 38 for(e = 0 ; e+j<=n&&e <= num[i]*o[num[i]] ; e+=num[i]) 39 { 40 c2[j+e]+=c1[j]; 41 } 42 for(j = 0 ; j <= n ;j++) 43 { 44 c1[j] = c2[j]; 45 c2[j] = 0; 46 } 47 } 48 cout<<c1[n]<<endl; 49 } 50 return 0; 51 }
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set> 10 using namespace std; 11 #define LL long long 12 #define INF 0xfffffff 13 const double eps = 1e-8; 14 const double pi = acos(-1.0); 15 const double inf = ~0u>>2; 16 double c1[22],c2[22]; 17 int b[12]; 18 int cn(int x) 19 { 20 int i,s=1; 21 for(i = 1; i <= x ; i++) 22 s*=i; 23 return s; 24 } 25 int main() 26 { 27 int i,j,n,m; 28 while(cin>>n>>m) 29 { 30 memset(c1,0,sizeof(c1)); 31 memset(c2,0,sizeof(c2)); 32 for(i = 1; i <= n; i++) 33 { 34 cin>>b[i]; 35 } 36 for(i = 0 ;i<=b[1] ;i++) 37 c1[i] = 1.0/cn(i); 38 for(i = 2; i <= n ;i++) 39 { 40 for(j = 0 ;j <= m ;j++) 41 { 42 for(int g = 0 ; g <= b[i] ; g++) 43 c2[j+g] += 1.0*c1[j]/cn(g); 44 } 45 for(j = 0 ; j <= m ;j++) 46 { 47 c1[j] = c2[j]; 48 c2[j] = 0; 49 } 50 } 51 printf("%0.lf\n",c1[m]*cn(m)); 52 } 53 return 0; 54 }
原文：http://www.cnblogs.com/shangyu/p/3577427.html
