第一周 8.28-9.3

我好烦呀。

8.30

让我们看看题解是怎么说的。

我好无脑呀。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 
 6 const LL mod = 1e6 + 3;
 7 
 8 
 9 LL qpow(LL a, LL b)
10 {
11     LL ret = 1LL;
12     while(b)
13     {
14         if(b & 1) ret = ret * a % mod;
15         a = a * a % mod;
16         b >>= 1;
17     }
18     return ret;
19 }
20 
21 
22 LL inv(LL x)
23 {
24     return qpow(x, mod - 2);
25 }
26 
27 
28 int main(void)
29 {
30     LL n, k;
31     scanf("%I64d %I64d", &n, &k);
32 
33     if(n <= 60 && (1LL << n) < k) return puts("1 1");
34 
35 
36     LL u = 0, d = (k - 1) % (mod - 1) * (n % (mod - 1)) % (mod - 1);
37 
38     LL base = 1;
39     while((1LL << base) <= k - 1)
40     {
41         LL tmp = (k - 1) / (1LL << base);
42         u += tmp;
43         d = (d + mod - 1 - tmp) % (mod - 1);
44         base++;
45     }
46     LL ans = qpow(2, d);
47 
48 
49     if(k - 1 >= mod) printf("%I64d ", ans);
50     else
51     {
52         LL tmp = 1;
53         for(int i = 1; i <= k - 1; i++)
54             tmp = tmp * (qpow(2, n) + mod - i) % mod;
55 
56         tmp = tmp * inv(qpow(2, u)) % mod;
57         printf("%I64d ", (ans + mod - tmp) % mod);
58     }
59 
60     printf("%I64d
", ans);
61 
62     return 0;
63 }

Aguin

51NOD 1661 黑板上的游戏

找完规律写错了一个很重要的地方但是竟然过了24组数组导致我以为是什么坑结果只是纯粹的写错。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 const int maxn = 1e5 + 10;
 6 LL a[maxn], sg[maxn];
 7 
 8 int main(void)
 9 {
10     int n;
11     LL k, ans = 0;
12     cin >> n >> k;
13     for(int i = 1; i <= n; i++)
14     {
15         cin >> a[i];
16         LL x = a[i];
17         while(x > 1 && x % k == 1) x /= k;
18         sg[i] = x - 1 - (x - 2) / k;
19         ans ^= sg[i];
20     }
21     if(!ans) puts("Bob");
22     else
23     {
24         for(int i = 1; i <= n; i++)
25         {
26             LL tmp = sg[i] ^ ans;
27             if(tmp >= sg[i]) continue;
28             LL cur = tmp + 1 + (tmp - 1) / (k - 1);
29             LL m = a[i] / k + (a[i] % k ? 1 : 0);
30             LL base = cur * (k - 1) + 1;
31             while(cur < m)
32             {
33                 cur += base;
34                 base = base * k;
35             }
36             printf("Alice ");
37             cout << i << ' ' << cur << endl;
38             break;
39         }
40     }
41     return 0;
42 }

Aguin