Lightoj 1245 - Harmonic Number (II)

http://lightoj.com/volume_showproblem.php?problem=1245

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define llu long long unsigned
4. int main(){
5.     int ts;
6.     scanf("%d", &ts);
7.     for(int p = 1; p <= ts; p++){
8.     int n;
9.     scanf("%d", &n);
10.     llu sum = 0;
11.     int m = sqrt(n);
12.     for(int i = 1; i<= m; i++) sum += (n/i);
13.     for(int i = 1; i<= m; i++){
14.         sum+= ((n/i)-(n/(i+1)))*i;
15.     }
16.     if(m==n/m) sum -= m;
17.     printf("Case %d: %llu\n",p,  sum);
18.     }
19.     return 0;
20. }

Lightoj 1213 - Fantasy of a Summation

http://lightoj.com/volume_showproblem.php?problem=1213

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define llu long long unsigned
4. long long mod_pow(long long b, long long e, long long m) {
5.   long long ans = 1;
6.   while (e > 0) {
7.     if (e & 1)
8.       ans = (ans * b) % m;
9.     b = (b * b) % m;
10.     e >>= 1;
11.   }
12.   return ans;
13. }
14.  
15. int main(){
16.     int ts;
17.     scanf("%d", &ts);
18.     for(int p = 1; p <= ts; p++){
19.     llu sum = 0, n, k, m;
20.     scanf("%llu%llu%llu",&n, &k, &m);
21.     for(llu i =0; i <n; i++){
22.         llu a;
23.         scanf("%llu", &a);
24.         sum+= a;
25.     }
26.     llu ans = k;
27.     ans = (ans*(mod_pow(n, k-1, m)))%m;
28.     //cout<<"ans = "<<sum<<endl;
29.     ans = (ans*sum)%m;
30.     printf("Case %d: %llu\n",p, ans);
31.     }
32.     return 0;
33. }

Lightoj 1170 - Counting Perfect BST

http://lightoj.com/volume_showproblem.php?problem=1170

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define ll long long unsigned
4. #define N 10000000000
5. #define M 100000007
6. ll numbers[1000006];
7. int cnt = 0;
8. void generate_num(){
9.     ll mul;
10.     for(ll i = 2; i <= 1000005; i++){
11.         mul = i*i;
12.         //printf("mul = %llu\n", mul);
13.         while(mul<= N){
14.             numbers[cnt++] = mul;
15.             mul = mul*i;
16.         }
17.     }
18.     sort(numbers, numbers+cnt);
19.     cnt = unique(numbers, numbers+cnt) - numbers;
20.     numbers[cnt++] = 1000000000000000;
21.     //cout<<"count = "<<cnt<<endl;
22.     //for(int i = 0; i <100; i++) cout<<numbers[i]<<" ";
23. }
24.  
25. ll fact[1000005];
26. ll bigmod(ll p, ll q){
27.     if(q == 1) return p%M;
28.     if(q%2 == 0){
29.         ll a = bigmod(p, q/2);
30.         return ((a%M)*(a%M))%M;
31.     }
32.     else{
33.         ll a = bigmod(p, q-1);return (a*p)%M;
34.     }
35. }
36. void pre(){
37.     fact[0] = 1;
38.     for(int i = 1; i <1000005; i++) fact[i] = (i*(fact[i-1]%M))%M;
39. }
40. int main(){
41.     generate_num();
42.     pre();
43.     int ts;
44.     scanf("%d", &ts);
45.     for(int k = 1; k <= ts; k++){
46.     ll a, b;
47.     scanf("%llu%llu", &a, &b);
48.     int l = lower_bound(numbers, numbers+cnt, a)-numbers;
49.     int r = upper_bound(numbers, numbers+cnt, b)-numbers;
50.     int elements = r-l;
51.         if(elements == 0){
52.             printf("Case %d: 0\n", k);
53.             continue;
54.         }
55.         ll s = bigmod((fact[elements+1]*fact[elements])%M,M-2)%M;
56.         ll p = (fact[2*elements]*s)%M;
57.         printf("Case %d: %llu\n", k,p);
58.     }
59.     return 0;
60. }

1189 - Sum of Factorials

http://lightoj.com/volume_showproblem.php?problem=1189

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define ll long long unsigned
4. #define N 66
5. ll fac[N];
6. void pre(){
7.     fac[0] = 1;
8.     for(int i = 1; i <N; i++) fac[i] = fac[i-1]*i;
9. }
10. int main(){
11.     pre();
12.     int ts;
13.     scanf("%d", &ts);
14.     for(int p = 1;p<= ts; p++){
15.     ll ans;
16.     scanf("%llu", &ans);
17.     vector<int> a;
18.     for(int i = N-1; i>= 0; i--) {
19.         if(ans>= fac[i]){
20.             ans = ans-fac[i];
21.             a.push_back(i);
22.         }
23.     }
24.     if(ans == 0){
25.     printf("Case %d: ", p);
26.     sort(a.begin(), a.end());
27.     for(int i = 0; i <a.size()-1; i++) printf("%d!+", a[i]);
28.     printf("%d!\n", a[a.size()-1]);
29.     }
30.     else printf("Case %d: impossible\n", p);
31.     }
32.     //for(int i = 0; i <N; i++) cout<<fac[i]<<" ";
33.    
34.     return 0;
35. }

Lightoj 1095 - Arrange the Numbers

http://lightoj.com/volume_showproblem.php?problem=1095

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define MOD 1000000007
4. #define N 1005
5. #define ll long long unsigned
6. ll fac[N];
7. ll dp[N][N];
8. int pre(){
9.     fac[0] = 1;
10.     for(int i = 1; i <N; i++) fac[i]= (fac[i-1]*i)%MOD;
11.     memset(dp, -1, sizeof(dp));
12. }
13. ll ncr(int n, int k){
14.     if(k==1) return n;
15.     if(n==k) return 1;
16.     if(dp[n][k]!=-1) return dp[n][k];
17.     return dp[n][k]= (ncr(n-1,k-1)+ncr(n-1,k))%MOD;
18. }
19. int main(){
20.     pre();
21.     int ts;
22.     scanf("%d", &ts);
23.     for(int p =1;p <= ts; p++){
24.     int n, m, k;
25.     scanf("%d%d%d", &n, &m, &k);
26.     ll ans1 = ncr(m, k);
27.     ll ans2 = fac[n-k];
28.     for(int i = 1; i <= m-k; i++){
29.         if(i%2) ans2-= (ncr(m-k, i)*fac[n-k-i])%MOD;
30.         else ans2+= (ncr(m-k, i)*fac[n-k-i])%MOD;
31.         ans2 = (ans2+MOD)%MOD;
32.     }
33.     printf("Case %d: %llu\n",p, (ans1*ans2)%MOD);
34.     }
35.     return 0;  
36. }

Lightoj 1102 - Problem Makes Problem

http://lightoj.com/volume_showproblem.php?problem=1102

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define ll long long int
4. #define M 1000000007
5. #define N 2000006
6. ll fact[N];
7. ll bigmod(ll p, ll q){
8.     if(q == 1) return p%M;
9.     if(q%2 == 0){
10.         ll a = bigmod(p, q/2);
11.         return ((a%M)*(a%M))%M;
12.     }
13.     else {ll a = bigmod(p, q-1);return (a*p)%M;}
14. }
15. void pre(){
16.     fact[0] = 1;
17.     for(int i = 1; i <N; i++) fact[i] = (i*(fact[i-1]%M))%M;
18. }
19. int main(){
20.     pre();
21.     int ts;
22.     scanf("%d", &ts);
23.     for(int k = 1; k <= ts; k++){
24.         int n, r;
25.         scanf("%d%d", &n, &r);
26.         ll s = bigmod((fact[n]*fact[r-1])%M,M-2)%M;
27.         ll p = (fact[n+r-1]*s)%M;
28.         printf("Case %d: %lld\n", k,p);
29.     }
30.     return 0;
31. }
32.  
33. /*
34.  
35. using namespace std;
36. #include <bits/stdc++.h>
37.  
38. const long long mod = 1000000007ll;
39. const int mn = 2000002;
40. long long fact[mn];
41.  
42. long long mod_pow(long long b, long long e, long long m) {
43.   long long ans = 1;
44.   while (e > 0) {
45.     if (e & 1)
46.       ans = (ans * b) % m;
47.     b = (b * b) % m;
48.     e >>= 1;
49.   }
50.   return ans;
51. }
52.  
53. void solve() {
54.   long long n, k;
55.   cin >> n >> k;
56.   long long num = fact[n + k - 1];
57.   long long den = (fact[n] * fact[k - 1]) % mod;
58.   printf("%lld\n", (num * mod_pow(den, mod - 2, mod)) % mod);
59. }
60.  
61.  
62. int main() {
63.   ios_base::sync_with_stdio(false);
64.   cin.tie(NULL);
65.   fact[0] = 1;
66.   for (int i = 1; i < mn; ++i) {
67.     fact[i] = (i * fact[i - 1]) % mod;
68.   }
69.   int tc;
70.   cin >> tc;
71.   for (int i = 0; i < tc; ++i) {
72.     printf("Case %d: ", i + 1);
73.     solve();
74.   }
75.   return 0;
76. }
77.  
78. */