{purple10}

Colossal Fibonacci Numbers!

因为输入WA了好几次。。。

unsigned long long最大为18446744073709551615

 1 #include <iostream>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 #define uLL unsigned long long
 5 const int maxn=2005010;
 6 uLL a,b;
 7 int n;
 8 int gcd(uLL a,uLL b, int mod)
 9 {
10     uLL temp=a%mod,ans=1;
11     while(b)
12     {
13         if(b&1) ans=ans*temp%mod;
14         b>>=1;
15         temp=temp*temp%mod;
16     }
17     return (int)ans;
18 }
19 int f[maxn];
20 int main()
21 {
22     int t;
23     scanf("%d",&t);
24     f[1]=1;f[2]=1;
25     while(t--)
26     {
27       //  scanf("%lld%lld%d",&a,&b,&n);
28         cin>>a>>b>>n;
29         if(n==1)
30         {
31             puts("0");
32             continue;
33         }
34         int i;
35         for(i=3;;i++)
36         {
37             f[i]=(f[i-1]+f[i-2])%n;
38             if(f[i]==f[2]&&f[i-1]==f[1]) break;
39         }
40         int id=gcd(a,b,i-2);
41         printf("%d
",f[id]);
42     }
43 
44 }

View Code

Disgruntled Judge

UVA - 12169

扩展欧几里得

 1 #include <iostream>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 #define LL long long
 5 const LL maxn=10001;
 6 LL c[110];
 7 
 8 LL gcd(LL a,LL b,LL &g,LL &x,LL &y)
 9 {
10     if(b==0) {g=a;x=1;y=0;}
11     else {
12         gcd(b,a%b,g,y,x);
13         y-=x*(a/b);
14     }
15 }
16 
17 
18 int main()
19 {
20     int n;
21     while(scanf("%d",&n)!=EOF)
22     {
23         for(int i=1;i<=n;i++)
24             scanf("%lld",&c[i]);
25         //枚举a，求b
26         // c2 - a*a*c1 = (a+1) * b + 10001 * k; 
27         for(int a=0;a<maxn+10;a++)
28         {
29             int ok=1;
30             LL g,x,y;
31             LL temp=(c[2]-c[1]*a*a);
32             gcd(a+1,maxn,g,x,y);
33             if(temp%g) continue;
34             x=x*temp/g;
35             for(int j=3;j<=n;j++)
36             {
37                 if(c[j]!=(a*((c[j-1]*a+x)%maxn)+x)%maxn)
38                 {
39                     ok=0;
40                     break;
41                 }
42             }
43             if(ok)
44             {
45                 for(int j=1;j<=n;j++)
46                     cout<<(c[j]*a+x)%maxn<<endl;
47                 break;
48             }
49         }
50     }
51 }

View Code

Irrelevant Elements

UVA - 1635

二项式定理，，不过想不到这么做，一开始没太看懂书上的意思，看了别人代码才明白

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1E5 + 10;
 4 bool prim[maxn];
 5 vector<pair<int, int> > Fta;
 6 vector<int>ans;
 7 int n, m, kase, Irrelevant[maxn];
 8 
 9 void prime_factors(int n)
10 {
11     int m = floor(sqrt(n) + 0.5);
12     for (int i = 2; i  <= m; i++)
13     {
14         int cnt = 0, p = i;
15         if (n % p == 0)
16         {
17             while (n % p == 0) n /= p, cnt++;
18             Fta.push_back(make_pair(p, cnt));
19         }
20     }
21     if (n > 1) Fta.push_back(make_pair(n, 1));
22 }
23 int main(int argc, char const *argv[])
24 {
25     while (cin >> n >> m)
26     {
27         n--;//计算的是C(0~n-1,n-1)!;
28         ans.clear();
29         Fta.clear();
30         prime_factors(m);
31         memset(Irrelevant, 0, sizeof(Irrelevant));
32         for (int i = 0; i < Fta.size(); i++)
33         {
34             int p = Fta[i].first, cnt = 0, x;
35             for (int k = 1; k < n; k++)
36             {
37                 x = n - k + 1;
38                 while (x % p == 0) {x /= p; cnt++;}
39                 x = k;
40                 while (x % p == 0) {x /= p; cnt--;}
41                 if (cnt < Fta[i].second) Irrelevant[k] = 1;
42             }
43         }
44         for (int i = 1; i < n; i++) if (!Irrelevant[i]) ans.push_back(i + 1);
45         cout  << ans.size() << endl;
46         for (int i = 0; i < ans.size(); i++)
47             cout << ans[i] << (i == ans.size() - 1 ? "
" : " ");
48         if (!ans.size()) cout << endl;//千万别忘了没有答案，也要换行！
49     }
50     return 0;
51 }

COPY

Send a Table

UVA - 10820

欧拉函数的应用。

 1 #include <cstdio>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 const int maxn=50010;
 5 int sum[maxn];
 6 int phi[maxn];
 7 void get_phi(int m,int *phi)
 8 {
 9     memset(phi,0,sizeof(phi));
10     phi[1]=1;
11     for(int i=2;i<=m;i++) if(!phi[i])
12         for(int j=i;j<=m;j+=i)
13     {
14         if(!phi[j]) phi[j]=j;
15             phi[j]=phi[j]/i*(i-1);
16     }
17 }
18 
19 int main()
20 {
21     int n;
22     get_phi(maxn,phi);
23     sum[1]=0;
24     for(int i=2;i<=maxn;i++) sum[i]=sum[i-1]+phi[i];
25     while(scanf("%d",&n)&&n)
26     {
27         printf("%d
",2*sum[n]+1);
28     }
29 }

View Code

Password

UVA - 1262

http://blog.csdn.net/loveyou11111111/article/details/50812384

不想做。。。

Headshot

UVA - 1636

概率题

SHOOT的情况是条件概率，在已知第一次没有子弹的情况下求解

ROTATE的情况和前一次射击无关

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<string>
 4 #include<iostream>
 5 using namespace std;
 6 string s;
 7 
 8 int main()
 9 {
10     while(cin>>s)
11     {
12         int a=0,b=0;
13         int len=s.length();
14         for(int i=0;i<len;i++)
15         {
16             if(s[i]=='0') a++;
17             if(s[i]=='0'&&s[(i+1)%len]=='0') b++;
18         }
19         double pf=b*1.0/a;
20         double pb=a*1.0/len;
21         if(pf>pb) puts("SHOOT");
22         else if(pf<pb) puts("ROTATE");
23         else puts("EQUAL");
24     }
25 
26 
27 }

View Code

Critical Mass

UVA - 580

递推。

根据最左边的三个U的位置进行分类。

假定是i，i+1，i+2这三个是U，则前i-1个不能有三个连续的U。

设n个盒子没有三个连续的U放在一起的方案数为g[n]=2^n-f[n]，则前i-1个盒子的方案有g[i-1]种，后面n-i-2个盒子可以任意放，有2^(n-i-2)种

所以f[n]= ∑g[i-1]*2^(n-i-2); i从1到n-2

上面的推理有瑕疵

因为可能i-2和i-1是U，i-3不是U，但是i是U

这里强制让第i-1个盒子是L，则前i-2个盒子不能出现连续的三个U

因此，当i=1时，即此时前三个是连续的U，方案数为2^(n-3)

当i>1时，根据上面的推导可知，方案数为 ∑g[i-2]*2^(n-i-2); i从2到n-2

故f[n]=2^(n-3)+∑g[i-2]*2^(n-i-2); i从2到n-2

 1 #include <cstdio>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 int f[35],g[35];
 5 int n;
 6 int main()
 7 {
 8     f[0]=f[1]=f[2]=0;
 9     g[0]=1;g[1]=2;g[2]=4;
10     for(int i=3;i<=30;i++)
11     {
12         f[i]+=(1<<i-3);
13         for(int j=2;j<=i-2;j++)
14             f[i]+=g[j-2]*(1<<i-j-2);
15         g[i]=(1<<i)-f[i];
16     }
17     while(scanf("%d",&n)&&n)
18     {
19         printf("%d
",f[n]);
20     }
21 }

View Code

Race

UVA - 12034

还是递推。。

 1 #include <cstdio>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 const int mod=10056;
 5 int f[1010],g[1010];
 6 int c[1010][1010];
 7 
 8 int main()
 9 {
10     for(int i=0;i<1010;i++)
11     {
12         c[i][0]=1;
13         for(int j=1;j<=i;j++)
14             c[i][j]=c[i-1][j-1]%mod+c[i-1][j]%mod;
15     }
16 
17     f[0]=1;
18     f[1]=1;f[2]=3;
19     for(int i=3;i<1010;i++)
20         for(int j=1;j<=i;j++)
21         f[i]=(f[i]+c[i][j]*f[i-j])%mod;
22     int t,n;
23     int kase=0;
24     scanf("%d",&t);
25     while(t--)
26     {
27         scanf("%d",&n);
28         printf("Case %d: %d
",++kase,f[n]);
29     }
30 }

View Code

 1 #include <cstdio>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 const int mod=10056;
 5 int f[1010],g[1010];
 6 int c[1010];
 7 
 8 int main()
 9 {
10     f[0]=1;
11     f[1]=1;f[2]=3;
12     c[0]=1;
13     for(int i=3;i<1010;i++)
14         for(int j=1;j<=i;j++)
15             {
16                 c[j]=c[j-1]*(i-j+1)/j%mod;  //C[i][j]  注意因为有除法所以不能直接取模
17                 f[i]=(f[i]+c[j]*f[i-j])%mod;
18             }
19     int t,n;
20     int kase=0;
21     scanf("%d",&t);
22     while(t--)
23     {
24         scanf("%d",&n);
25         printf("Case %d: %d
",++kase,f[n]);
26     }
27 }

错误版

Pole Arrangement

UVA - 1638

递推从高到低安排位置 f[i][j][k]=f[i-1][j-1][k]+f[i-1][j][k-1]+f[i-1][j][k]*(i-2);

 1 #include <cstdio>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 int n,l,r;
 5 long long f[22][22][22];
 6 
 7 void init()
 8 {
 9     f[1][1][1]=1;
10     f[2][2][1]=f[2][1][2]=1;
11 
12     for(int i=3;i<=20;i++)
13         for(int j=1;j<=i;j++)
14         for(int k=1;k<=i;k++)
15         f[i][j][k]=f[i-1][j-1][k]+f[i-1][j][k-1]+f[i-1][j][k]*(i-2);
16 }
17 int main()
18 {
19     init();
20     int t;
21     scanf("%d",&t);
22     while(t--)
23     {
24         scanf("%d%d%d",&n,&l,&r);
25         printf("%lld
",f[n][l][r]);
26     }
27 }

View Code