• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

NOIP模拟75

开发技术 开发技术 3小时前 3次浏览

T1:

  考场卡点在于如何采用根号算法求解,试图推性质,利用根号左侧数据更新根号右侧数据

开方即可,然而当数据存在指数为奇数的质因子时无法进行计算

  正解为整除分块,事实上大多数数论根号算法都是数论分块

  考虑如何对问题所求进行转化,对于2^n,能够想到可以类比为子集枚举,那么发现,问题等价于

对于1~n内质因数进行子集枚举,于是考虑转化为求解子集贡献,设子集为k,那么问题等价于求

sigma u^2(k) * n / k,u^2考虑莫比乌斯函数的定义,在质因数集含偶指数时为0,不含则为(-1)^k,

k为集合大小,那么我们需要的是对于任意不含偶指数质因子集贡献为1,于是需要魔改u函数,平方即可

  上述式子需要杜教筛进行优化,数论分块的话发现难以进行,考虑转换思路,问题等价于求解

sigma u^2(d)(d | n) = sigma sigma u(d)(d | n && k^2 | d)(证明采用二项式定理,考虑u函数意义即可),

和式变换枚举d得到sigma u(d) * sigma(k^2 | d)n / d

设d = k^2 * i,得到 sigma u(d) sigam n / (k * k * i),于是对后者数论分块即可

代码如下:

NOIP模拟75NOIP模拟75

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I long long
 4 #define C char
 5 #define B bool
 6 #define V void
 7 #define D double
 8 #define LL long long
 9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 const I mod = 1e9 + 7;
20 LL n,ans;
21 I cnt,prime[78500];
22 B not_prime[1000005];
23 I u[1000005],pre[1000005];
24 inline LL read () {
25     LL x(0),y(1); C z(getchar());
26     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
27     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
28     return x * y;
29 }
30 inline V Max (I &a,I b) { a = a > b ? a : b; }
31 inline V Min (I &a,I b) { a = a < b ? a : b; }
32 inline I max (I a,I b) { return a > b ? a : b; }
33 inline I min (I a,I b) { return a < b ? a : b; }
34 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
35 inline I abs (I a) { return a >= 0 ? a : -a; }
36 inline P operator + (const P &a,const P &b) {
37     return MP (a.a + b.a,a.b + b.b);
38 }
39 inline P operator - (const P &a,const P &b) {
40     return MP (a.a - b.a,a.b - b.b);
41 }
42 signed main () {
43     FP (elegant.in), FC (elegant.out);
44     n = read ();
45     I t (ceil (sqrt (n)));
46     u[1] = pre[1] = 1;
47     for (I i(2);i <= t; ++ i) {
48         if (!not_prime[i]) prime[cnt++] = i, u[i] = -1;
49         for (I j(0);j < cnt && i * prime[j] <= t; ++ j) {
50             not_prime[i * prime[j]] = 1;
51             if (i % prime[j] == 0) break;
52             u[i * prime[j]] = -u[i];
53         }
54         pre[i] = pre[i - 1] + u[i];
55     }
56     I w,s;
57     for (I l(1),r;l <= t;l = r + 1) {
58         if (n / (l * l) == 0) break; 
59         r = sqrt (n / (n / (l * l))), w = n / (l * l), s = 0;
60         for (I a(1),b;a <= w;a = b + 1) {
61             b = w / (w / a);
62             (s += (b - a + 1) * (w / a) % mod) %= mod;
63         }
64         (ans += (pre[r] - pre[l - 1]) * s % mod) %= mod;
65     }
66     printf ("%lldn",(ans + mod) % mod);
67 }

View Code

T2:

  set暴力维护即可

代码如下:

NOIP模拟75NOIP模拟75

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define C char
 5 #define B bool
 6 #define V void
 7 #define D double
 8 #define LL long long
 9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 const I N = 1e5 + 3, inf = 1e9;
20 I typ,n,m,c,p,ans;
21 I tot,head[N],to[N << 1],nxt[N << 1];
22 I cnt,dfn[N],f[N],t[N],s[N],size[N],d[N];
23 multiset <I> g[N];
24 inline I read () {
25     I x(0),y(1); C z(getchar());
26     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
27     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
28     return x * y;
29 }
30 inline V Max (I &a,I b) { a = a > b ? a : b; }
31 inline V Min (I &a,I b) { a = a < b ? a : b; }
32 inline I max (I a,I b) { return a > b ? a : b; }
33 inline I min (I a,I b) { return a < b ? a : b; }
34 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
35 inline I abs (I a) { return a >= 0 ? a : -a; }
36 inline P operator + (const P &a,const P &b) {
37     return MP (a.a + b.a,a.b + b.b);
38 }
39 inline P operator - (const P &a,const P &b) {
40     return MP (a.a - b.a,a.b - b.b);
41 }
42 inline V found (I x,I y) {
43     to[++tot] = y, nxt[tot] = head[x], head[x] = tot;
44     to[++tot] = x, nxt[tot] = head[y], head[y] = tot;
45 }
46 V Dfs1 (I x,I father) {
47     f[x] = father, size[x] = 1;
48     for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (y != father) {
49         d[y] = d[x] + 1, Dfs1 (y,x), size[x] += size[y];
50         if (size[y] > size[s[x]]) s[x] = y;
51     }
52 }
53 V Dfs2 (I x,I top) {
54     dfn[x] = ++cnt, t[x] = top;
55     if (!s[x]) return ; Dfs2 (s[x],top);
56     for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (y != f[x] && y != s[x])
57         Dfs2 (y,y);
58 }
59 inline I LCA (I x,I y) {
60     while (t[x] != t[y]) dfn[x] < dfn[y] ? y = f[t[y]] : x = f[t[x]];
61     return dfn[x] < dfn[y] ? x : y;
62 }
63 signed main () {
64     FP (yygq.in), FC (yygq.out);
65     typ = read (), n = read ();
66     for (I i(1);i <  n; ++ i)
67         found (read (), read ());
68     Dfs1 (1,0), Dfs2 (1,1);
69     m = read ();
70     while (m -- ) {
71         I tp (read ()), x (read () ^ (ans * typ));
72         if (tp == 1) {
73             g[p + 1] = g[c]; c = ++ p;
74             if (g[p].find (x) == g[p].end ()) g[p].insert (x); else g[p].erase (g[p].find (x));
75         }
76         if (tp == 2) {
77             ans = inf;
78             if (x > n) { puts ("1000000000"); continue; }
79             for (auto y : g[c]) 
80                 Min (ans,d[x] + d[y] - d[LCA (x,y)] * 2);
81             printf ("%dn",ans);
82         }
83         if (tp == 3 && x <= p) c = x;
84     }
85 }

View Code

T3:

  考虑根据题意,设f[i][j]表示i个数,j次交换方案数,考虑dp转移,首先第i个数不进行交换

直接继承上一次状态为f[i][j] += f[i – 1][j],第二种情况为第i个数进行交换,考虑交换对象有

i – 1种选择,于是有转移f[i][j] += f[i – 1][j – 1] * (i – 1)

  考虑优化dp,发现本题dp的本质与输入的n与k并不相关,考虑其数学原理,利用表格法

将dp的转移路径在草纸上画出,可以发现,dp转移最多进行k次,每次转移项数加1并且次数加1

于是根据自然数平方和定理每次转移由项数与次数分别进次,那么最终f[n][k]即为不超过2 * k – 1

次多项式,最终要求前缀和,那么即为2 * k次多项式,拉格朗日插值求出前2 * k项前缀和即可

代码如下:

NOIP模拟75NOIP模拟75

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I long long
 4 #define C char
 5 #define B bool
 6 #define V void
 7 #define D double
 8 #define LL long long
 9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 const I mod = 1e9 + 7;
20 I n,k,ans,f[2][6005],y[6005];  
21 inline I read () {
22     I x(0),y(1); C z(getchar());
23     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
24     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
25     return x * y;
26 }
27 inline V Max (I &a,I b) { a = a > b ? a : b; }
28 inline V Min (I &a,I b) { a = a < b ? a : b; }
29 inline I max (I a,I b) { return a > b ? a : b; }
30 inline I min (I a,I b) { return a < b ? a : b; }
31 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
32 inline I abs (I a) { return a >= 0 ? a : -a; }
33 inline P operator + (const P &a,const P &b) {
34     return MP (a.a + b.a,a.b + b.b);
35 }
36 inline P operator - (const P &a,const P &b) {
37     return MP (a.a - b.a,a.b - b.b);
38 }
39 inline I fp (I a,I b) {
40     I ans (1);
41     for (; b ;b >>= 1, a = a * a % mod)
42         if (b & 1) ans = ans * a % mod;
43     return ans;
44 }
45 signed main () {
46     FP (guess.in), FC (guess.out);
47     n = read (), k = read (); 
48     for (I i(1);i < 6005; ++ i) {
49         y[i] = f[i & 1][0] = 1;
50         for (I j(1);j < 6005 && j <= k; ++ j)
51             f[i & 1][j] = (f[i - 1 & 1][j] + (i - 1) * f[i - 1 & 1][j - 1]) % mod, y[i] = (y[i] + f[i & 1][j]) % mod;
52         if (i == n) printf ("%lldn",y[i]), exit (0);
53     }
54     for (I i(1);i < 6005; ++ i) {
55         I pro1 (y[i]), pro2 (1);
56         for (I j(1);j < 6005; ++ j) if(j != i)
57             pro1 = pro1 * (n - j) % mod, pro2 = pro2 * (i - j) % mod;
58         ans = (ans + pro1 * fp (pro2,mod - 2) % mod) % mod;
59     }
60     printf ("%lldn",(ans + mod) % mod);
61 }

View Code

 


程序员灯塔
转载请注明原文链接:NOIP模拟75
喜欢 (0)