Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 136 words)

【模板】各种欧几里得

原文地址 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int gcd(int n,int m)//n>m
{
    //最大公约数
    int r;
    while(m)
    {
        r = n%m;
        n = m;
        m = r;
    }
    return n;
}

int kgcd(int a,int b)
{
    if(!a) return b;
    if(!b) return a;
    if(!(a&1) && !(b&1))
        return kgcd(a>>1,b>>1)<<1;
    else if(!(b&1)) return kgcd(a,b>>1);
    else if(!(a&1)) return kgcd(a>>1,b);
    else return kgcd(abs(a-b),min(a,b));
}

//扩展欧几里得
//求方程ax+by+c = 0有多少整数解
int extgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    int d = extgcd(b,a%b,x,y);
    int t = x;
    x=y;
    y=t-a/b*y;
    return d;
}
Posted Updated  Semprathlon / Simfae Dean 2 minutes read (About 316 words)

PHP Markdown & LaTex test

1

<https: //daringfireball.net/projects/markdown/syntax>
The full documentation of Markdown’s syntax

|Hash函数|数据1|数据2|数据3|数据4|数据1得分|数据2得分|数据3得分|数据4得分|平均分| |—-|—-|—-|—-|—-|—-|—-|—-|—-|—-| |BKDRHash|2|0|4774|481|96.55|100|90.95|82.05|92.64| |APHash|2|3|4754|493|96.55|88.46|100|51.28|86.28| |DJBHash|2|2|4975|474|96.55|92.31|0|100|83.43| |JSHash|1|4|4761|506|100|84.62|96.83|17.95|81.94| |RSHash|1|0|4861|505|100|100|51.58|20.51|75.96| |SDBMHash|3|2|4849|504|93.1|92.31|57.01|23.08|72.41| |PJWHash|30|26|4878|513|0|0|43.89|0|21.95| |ELFHash|30|26|4878|513|0|0|43.89|0|21.95|

Problem Description

Tom was on the way home from school. He saw a matrix in the sky. He found that if we numbered rows and columns of the matrix from 0, then, $ {a} _ {i,j}={C} _ {i}^{j}$
if i < j, $ {a}_{i,j}=0$
Tom suddenly had an idea. He wanted to know the sum of the numbers in some rectangles. Tom needed to go home quickly, so he wouldn’t solve this problem by himself. Now he wants you to help him.
Because the number may be very large, output the answer to the problem modulo a prime p.

Input

Multi test cases(about 8). Each case occupies only one line, contains five integers, $ x_{1}、y_{1}、x_{2}、y_{2}、p.
x_{1}\leq x_{2}\leq {10}^{5},y_{1}\leq y_{2}\leq {10}^{5},2\leq p\leq {10}^{9}$ .

###Latex公式测试
行内公式 $ \delta = \beta / (\alpha + 1) $
行间公式
$$
\frac{O}{I} \approx \frac{A}{1+AF}
$$

$$ 上下标 U_o = A^2 * ( U_+ - U_- ) $$
$$ 上下标 (U_o = A^2 * ( U_+ - U_- )) $$
$$ 上下标 [U_o = A^2 * ( U_+ - U_- )] $$

积分
$ \int_1 ^2 sin x dx $

方程组
$$
\begin{aligned}
\dot{x} & = \sigma(y-x) \newline
\dot{y} & = \rho x - y - xz \newline
\dot{z} & = -\beta z + xy
\end{aligned}
$$

$$
\begin{eqnarray}
&& \frac{\partial x}{\partial C_{ikj}} \
&& \frac{\partial C_{ikj}}{\partial R_{ik}} \
&& \frac{\partial C_{ikj}}{\partial R_{jk}}\
&& a = R_{ik}^2-R_{jk}^2 , b = (R_{ij}^4-a^2)^2
\end{eqnarray}
$$

$$
\left{ \Sigma= { (\theta,\varphi)|0\le \theta \le 2\pi,0\le \varphi \le\frac{\pi}{2} \right}
$$

Dashboard

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing7 minutes read (About 1120 words)

2013ACM-ICPC杭州赛区全国邀请赛

Transformation（HDU 4578）

Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 65535/65536 K (Java/Others)

Problem Description

Yuanfang is puzzled with the question below:
There are n integers, a1, a2, …, an. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between ax and ay inclusive. In other words, do transformation ak<—ak+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between ax and ay inclusive. In other words, do transformation ak<—ak×c, k = x,x+1,…,y.
Operation 3: Change the numbers between ax and ay to c, inclusive. In other words, do transformation ak<—c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between ax and ay inclusive. In other words, get the result of axp+ax+1p+…+ay p.
Yuanfang has no idea of how to do it. So he wants to ask you to help him.

Input

There are no more than 10 test cases.
For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.
Each the following m lines contains an operation. Operation 1 to 3 is in this format: “1 x y c” or “2 x y c” or “3 x y c”. Operation 4 is in this format: “4 x y p”. (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)
The input ends with 0 0.

Output

For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.

Sample Input

5 5
3 3 5 7
1 2 4 4
4 1 5 2
2 2 5 8
4 3 5 3
0 0

Sample Output

307
7489

  • TLE，不必在每次query时都更新到叶结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
struct Node
{
    int l,r,mid;
    LL v,add,mul;
} SegTree[maxn*4];

void build(int rt,int l,int r)
{
    SegTree[rt].l=l;SegTree[rt].r=r;
    SegTree[rt].mid=(l+r)>>1;
    SegTree[rt].add=SegTree[rt].v=0;
    SegTree[rt].mul=1;
    if (l<r)
    {
        build(rt<<1,l,SegTree[rt].mid);
        build(rt<<1|1,SegTree[rt].mid+1,r);
    }
}

void add(int rt,int x,int y,int num)
{
    int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
    if (x>y) return;
    //cout<<"+ "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<x<<' '<<y<<' '<<num<<endl;
    if (x<=SegTree[rt].l&&SegTree[rt].r<=y)
    {
        SegTree[rt].add+=num;
        SegTree[rt].add%=mod;
        return;
    }
    int tmp=SegTree[rt].add;
    if (SegTree[rt].add)
    {

        SegTree[rt].add=0;
        add(rt,SegTree[rt].l,x-1,tmp);
        add(rt,y+1,SegTree[rt].r,tmp);
    }
    if (x<=mid) add(rt<<1,x,min(mid,y),tmp+num);
    if (y>mid) add(rt<<1|1,max(mid+1,x),y,tmp+num);
}

void mul(int rt,int x,int y,int num)
{
    int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
    if (x>y) return;
    if (x<=SegTree[rt].l&&SegTree[rt].r<=y)
    {
        SegTree[rt].mul*=num;SegTree[rt].mul%=mod;
        SegTree[rt].add*=num;SegTree[rt].add%=mod;
        return;
    }
    int tmp=SegTree[rt].mul;
    if (SegTree[rt].mul!=1)
    {
        SegTree[rt].mul=1;
        add(rt,SegTree[rt].l,x-1,SegTree[rt].add*tmp);
        mul(rt,SegTree[rt].l,x-1,tmp);
        add(rt,x,y,SegTree[rt].add*tmp*num);
        add(rt,y+1,SegTree[rt].r,SegTree[rt].add*tmp);
        mul(rt,y+1,SegTree[rt].r,tmp);
    }
    if (x<=mid) mul(rt<<1,x,min(mid,y),tmp*num);
    if (y>mid) mul(rt<<1|1,max(mid+1,x),y,tmp*num);
}

void cover(int rt,int x,int y,int num)
{
    int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
    if (x>y) return;
    //cout<<"c "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<x<<' '<<y<<' '<<num<<endl;
    if (x<=SegTree[rt].l&&SegTree[rt].r<=y)
    {
        SegTree[rt].v=num;
        SegTree[rt].add=0;
        SegTree[rt].mul=1;
        return;
    }
    if (SegTree[rt].add)
    {
        int tmp=SegTree[rt].add;
        SegTree[rt].add=0;
        add(rt,SegTree[rt].l,x-1,tmp);
        add(rt,y+1,SegTree[rt].r,tmp);
    }
    if (SegTree[rt].mul!=1)
    {
        int tmp=SegTree[rt].mul;
        SegTree[rt].mul=1;
        mul(rt,SegTree[rt].l,x-1,tmp);
        mul(rt,y+1,SegTree[rt].r,tmp);
    }
    if (x<=mid) cover(rt<<1,x,min(mid,y),num);
    if (y>mid) cover(rt<<1|1,max(mid+1,x),y,num);
}

LL query(int rt,int x,int y,int p)
{
    int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
    //cout<<"q "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<SegTree[rt].v<<' '<<SegTree[rt].add<<' '<<SegTree[rt].mul<<endl; //<<"  "<<x<<' '<<y<<' '<<endl;
    if (SegTree[rt].l==SegTree[rt].r)
    //if (SegTree[rt].v)
    {
        SegTree[rt].v*=SegTree[rt].mul;SegTree[rt].v%=mod;
        SegTree[rt].v+=SegTree[rt].add;SegTree[rt].v%=mod;
        SegTree[rt].add=0;
        SegTree[rt].mul=1;
        switch(p)
        {
            case 1:return SegTree[rt].v;
            case 2:return SegTree[rt].v*SegTree[rt].v%mod;
            case 3:return SegTree[rt].v*SegTree[rt].v*SegTree[rt].v%mod;
        }

    }
    if (SegTree[rt].v)
    {
        add(rt<<1,l,mid,SegTree[rt].v*SegTree[rt].mul+SegTree[rt].add);
        add(rt<<1|1,mid+1,r,SegTree[rt].v*SegTree[rt].mul+SegTree[rt].add);
        SegTree[rt].v=0;
    }
    if (SegTree[rt].add)
    {
        //puts("update");
        add(rt<<1,l,mid,SegTree[rt].add);
        add(rt<<1|1,mid+1,r,SegTree[rt].add);
        SegTree[rt].add=0;
    }
    if (SegTree[rt].mul!=1)
    {
        mul(rt<<1,l,mid,SegTree[rt].mul);
        mul(rt<<1|1,mid+1,r,SegTree[rt].mul);
        SegTree[rt].mul=1;
    }
    return (((x<=mid)?query(rt<<1,x,min(mid,y),p):0)+((y>mid)?query(rt<<1|1,max(mid+1,x),y,p):0))%mod;

}

LL fnd(int rt,int x)
{
    if(SegTree[rt].l==SegTree[rt].r) return SegTree[rt].v;
    else if (x<=SegTree[rt].mid) return fnd(rt<<1,x);
    else return fnd(rt<<1|1,x);
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        if (!n&&!m) break;
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            int op,x,y,c;
            scanf("%d%d%d%d",&op,&x,&y,&c);
            switch(op)
            {
                case 1:
                    add(1,x,y,c);//query(1,x,y,1);
                    break;
                case 2:
                    mul(1,x,y,c);//query(1,x,y,1);
                    break;
                case 3:
                    cover(1,x,y,c);//query(1,x,y,1);
                    break;
                case 4:
                    printf("%I64d\n",query(1,x,y,c));
                    break;
            }
            //for(int i=1;i<=n;i++) printf("%lld ",fnd(1,i));printf("\n");
        }
    }
    return 0;
}
  • AC 4882MS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))

using namespace std;

typedef long long LL;
const double pi = acos(-1.0);
const int maxn = 1e5 + 10;
const int inf = 99999999;
const double eps = 1e-3;
const int mod = 10007;

struct Node
{
    int l, r, mid;
    LL v, add, mul;
    bool up;
} SegTree[maxn * 4];

void build(int rt, int l, int r)
{
    SegTree[rt].l = l;
    SegTree[rt].r = r;
    SegTree[rt].mid = (l + r) >> 1;
    SegTree[rt].add = SegTree[rt].v = 0;
    SegTree[rt].mul = 1;
    if (l < r)
    {
        SegTree[rt].up = 0;
        build(rt << 1, l, SegTree[rt].mid);
        build(rt << 1 | 1, SegTree[rt].mid + 1, r);
    }
    else
    {
        SegTree[rt].up = 1;
    }
}

void pushdown(int rt)
{
    int mid = SegTree[rt].mid;
    if (SegTree[rt].up)
    {
        SegTree[rt << 1].add = SegTree[rt << 1 | 1].add = 0;
        SegTree[rt << 1].mul = SegTree[rt << 1 | 1].mul = 1;
        SegTree[rt << 1].v = SegTree[rt << 1 | 1].v = SegTree[rt].v;
        SegTree[rt << 1].up = SegTree[rt << 1 | 1].up = 1;
        SegTree[rt].up = 0;
    }
    else
    {
        if (SegTree[rt].add)
        {
            if (SegTree[rt << 1].up)
            {
                SegTree[rt << 1].v += SegTree[rt].add;
                SegTree[rt << 1].v %= mod;
            }
            else
            {
                pushdown(rt << 1);
                SegTree[rt << 1].add += SegTree[rt].add;
                SegTree[rt << 1].add %= mod;
            }
            if (SegTree[rt << 1 | 1].up)
            {
                SegTree[rt << 1 | 1].v += SegTree[rt].add;
                SegTree[rt << 1 | 1].v %= mod;
            }
            else
            {
                pushdown(rt << 1 | 1);
                SegTree[rt << 1 | 1].add += SegTree[rt].add;
                SegTree[rt << 1 | 1].add %= mod;
            }
            SegTree[rt].add = 0;
        }
        if (SegTree[rt].mul != 1)
        {
            if (SegTree[rt << 1].up)
            {
                SegTree[rt << 1].v *= SegTree[rt].mul;
                SegTree[rt << 1].v %= mod;
            }
            else
            {
                pushdown(rt << 1);
                SegTree[rt << 1].mul *= SegTree[rt].mul;
                SegTree[rt << 1].mul %= mod;
            }
            if (SegTree[rt << 1 | 1].up)
            {
                SegTree[rt << 1 | 1].v *= SegTree[rt].mul;
                SegTree[rt << 1 | 1].v %= mod;
            }
            else
            {
                pushdown(rt << 1 | 1);
                SegTree[rt << 1 | 1].mul *= SegTree[rt].mul;
                SegTree[rt << 1 | 1].mul %= mod;
            }
            SegTree[rt].mul = 1;
        }
    }
}

void update(int rt, int x, int y, LL num,int op)
{
    int& l = SegTree[rt].l, &r = SegTree[rt].r, &mid = SegTree[rt].mid;
    //cout<<"+ "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<x<<' '<<y<<' '<<num<<endl;
    if (x <= SegTree[rt].l && SegTree[rt].r <= y)
    {
        if (op==3)
        {
            SegTree[rt].add=0;
            SegTree[rt].mul=1;
            SegTree[rt].v=num;
            SegTree[rt].up=1;
        }
        else
        {
            if (SegTree[rt].up)
            {
                if (op==1)
                {
                    SegTree[rt].v+=num;SegTree[rt].v%=mod;
                }
                else
                {
                    SegTree[rt].v*=num;SegTree[rt].v%=mod;
                }
            }
            else
            {
                pushdown(rt);
                if (op==1)
                {
                    SegTree[rt].add+=num;SegTree[rt].add%=mod;
                }
                else
                {
                    SegTree[rt].mul*=num;SegTree[rt].mul%=mod;
                }
            }
        }
        return;
    }
    pushdown(rt);
    if (x <= mid)
        update(rt << 1, x, min(mid, y), num,op);
    if (y > mid)
        update(rt << 1 | 1, max(mid + 1, x), y, num,op);
}

LL query(int rt, int x, int y, int p)
{
    int& l = SegTree[rt].l, &r = SegTree[rt].r, &mid = SegTree[rt].mid;
    //cout<<"q "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<SegTree[rt].v<<' '<<SegTree[rt].add<<' '<<SegTree[rt].mul<<endl; //<<"  "<<x<<' '<<y<<' '<<endl;
    if (x <= SegTree[rt].l && SegTree[rt].r <= y&&SegTree[rt].up)
    {
        LL tmp=LL(r-l+1)%mod;
        for(int i=1;i<=p;i++)
        {
            tmp*=SegTree[rt].v;tmp%=mod;
        }
        return tmp;
    }
    pushdown(rt);
    return (((x <= mid) ? query(rt << 1, x, min(mid, y), p) : 0LL) + ((y > mid) ? query(rt << 1 | 1, max(mid + 1, x), y, p) : 0LL)) % mod;
}

LL fnd(int rt, int x)
{
    if (SegTree[rt].l == SegTree[rt].r)
    {
        return SegTree[rt].v;
    }
    else if (x <= SegTree[rt].mid)
    {
        return fnd(rt << 1, x);
    }
    else
    {
        return fnd(rt << 1 | 1, x);
    }
}

int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        if (!n && !m)
        {
            break;
        }
        build(1, 1, n);
        for (int i = 1; i <= m; i++)
        {
            int op, x, y;
            LL c;
            scanf("%d%d%d%I64d", &op, &x, &y, &c);
            switch (op)
            {
                case 1:
                case 2:
                case 3:
                    update(1, x, y, c,op); //query(1,x,y,1);
                    break;
                case 4:
                    printf("%I64d\n", query(1, x, y, c));
                    break;
            }
            //for(int i=1;i<=n;i++) printf("%lld ",fnd(1,i));printf("\n");
        }
    }
    return 0;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing9 minutes read (About 1303 words)

ACM - ICPC Regionals 2014 Bangkok 亚洲区域赛 国外某数学题

ACM-ICPC Live Archive Regionals 2014 >> Asia - Bangkok
6844 - Combination

原题页面
PDF题面
Vjudge提交地址

艰辛坎坷的探索历程

设 $ {f(n)=C_{n}^{r}(n∈N^{ * },r∈[0,n])} $中奇数的个数。
题意是说，求出 $ \sum f(k),k∈[low,high] $
庞大的数据， $ n≤16\times{10^{11}}. $

step1

判断给定 $ n∈N^{ * } $时 $ C_n^r(r∈[0,n]) $的奇偶性。 不难往n,r的二进制表示方向考虑。
查阅他人博客获得结论： $ n{ & }r==r $时 $ C_n^r $为奇数。 然而本题中无需直接应用这一“定理”，所要做的是统计。
拿出纸笔推算发现，若n的二进制表示中有d个1，则 $ C_n^r(r∈[0,n]) $中存在 $ 2^d $个奇数。

step2

研究 $ f(n) $ 的递推关系及通项。 编写暴力程序 $ O(n^2) $ ，打表观察 $ n∈[0,64) $ 时 $ f(n) $ 的取值：
1
2
2 4
2 4 4 8
2 4 4 8 4 8 8 16
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32 4 8 8 16 8 16 16 32 8 16 16 32 16 32 32 64
第一行 $ f(0)=1 $ 作为边界条件， 第二行 $ f(1)=2 $ ，随后各行的第k行的 $ 2^{k-2} $ 个数分别表示 $ f(2^{k-2}),f(2^{k-2}+1),…,f(2^{k-1}-1) $ 。
通过不懈的努力，观察发现从第3行开始，每行的前半部分与前一行完全一致，每行的后半部分的各个f值恰为前半部分对应位置的f值的2倍。

step3

出于数列直觉，我们尝试求解各行的和构成的数列的递推以及通项。
$ a_1=1 $
$ a_2=2 $
$ a_3=a_2+2\times{a_2}=3\times{a_2}=6 $
…
$ a_n=a_{n-1}+2\times{a_{n-1}}=3\times{a_{n-1}}(n\geq 3) $（递推公式）
通项公式:
$$
\begin{equation} a_n= \begin{cases} 1 &\mbox{$n=1$}\newline 2 &\mbox{$n=2$}\newline 2\times3^{n-2} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$

$$
\begin{equation} S_n=\sum\limits_{i=1}^{n} {a_i}= \begin{cases} 1 &\mbox{$n=1$}\newline 3 &\mbox{$n=2$}\newline 3+6\times\frac{1-3^{n-2}}{1-3}=3+3\times{(3^{n-2}-1)}=3^{n-1} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$

$$
S_n=3^{n-1}（a_n的前n项和的公式）
$$
化简后上面这个公式样子够好看了吧？

step4

再看一下第2步发现的规律，应用“二分”手段高效地求解，而且真的可以二分求解。
具体地说，就是先置求解区间 $ [l,r) $ (左闭右开)的端点于每行的头尾( $ l=2^{i-2},r=2^{i-1} $ )，利用上一步所得公式计算该区间的 $ 左端点前缀和U=\sum\limits_{k=1}^{2^{i-2}} {f(k)} $ 与 $ 右端点前缀和V=\sum\limits_{k=1}^{2^{i-1}-1} {f(k)} $ 后，不断地对区间折半，总可以确定新区间的左端点前缀和与右端点前缀和。
当区间缩至一点时， $ U==V==f(k) $，即能得到我们所求，而无需计算出[1..n]的每个函数值。

step5

以上所解决的并不是最终答案，而是前缀和 $ \sum\limits_{k=1}^{n} {f(k)} $ ；
不过走到这一步已经很好办了， $ ans=\sum\limits_{k=low}^{high} {f(k)}=\sum\limits_{k=1}^{high} {f(k)}-\sum\limits_{k=1}^{low-1} {f(k)} $

PS:写完代码后，用极大的n值测试一下，事实上 $ \sum\limits_{k=1}^{n} {f(k)} $已经超出了int64的范围。其他的细节不必多说了。

1.319s AC java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * @date 2015-05-31
 * @author Semprathlon
 */
import java.math.*;
import java.io.*;

public class Main {
    static int maxn=42;
    static BigInteger[] sum=new BigInteger[maxn];
    static long[] Pow2=new long[maxn];
    final static BigInteger TWO=BigInteger.valueOf(2);
    final static BigInteger THREE=BigInteger.valueOf(3);
    
    static int found_pow2(long n){
        return (int)(Math.log((double)n)/Math.log(2.0));
    }

    static void init(){
        for(int i=0;i<maxn;i++)
        {
            sum[i]=THREE.pow(i);
            Pow2[i]=1L<<i;
        }
            
    }
    static BigInteger Bisearch(long l,long r,BigInteger ls,BigInteger rs,long key){
        while(l+1L<r){
            long mid=(l+r)>>1;
            if(key<mid){
                r=mid;
                rs=ls.add(rs.subtract(ls).divide(THREE));
            }
            else{
                l=mid;
                ls=ls.add(rs.subtract(ls).divide(THREE));
            }
        }
        return ls;
    }
    static BigInteger solve(long n){
        if (n<0L) return BigInteger.ZERO;
        if (n==0L) return BigInteger.ONE;
        int k=found_pow2(n+1);
        BigInteger ls=sum[k];
        BigInteger rs=sum[k+1];
        return Bisearch(Pow2[k],Pow2[k+1],ls,rs,n+1);
    }
    public static void main(String[] args) throws IOException{
        init();
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        long n=0,m=0;
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n=(long)in.nval;
            in.nextToken();
            m=(long)in.nval;
            if (n==0L&&m==0L) break;
            out.println(solve(m).subtract(solve(n-1)));
        }
        out.flush();
        out.close();
    }
}

0.279s AC cpp代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 42;
const LL mod = 1e8;
const int digit = 8;
struct LongInt
{
    LL data[3];
    LongInt()
    {
        data[0] = data[1] = data[2] = 0;
    }
    LongInt(LL n)
    {
        data[0] = n % mod;
        n /= mod;
        data[1] = n % mod;
        n /= mod;
        data[2] = n;
    }
    LongInt operator= (const LL num)
    {
        LL n = num;
        data[0] = n % mod;
        n /= mod;
        data[1] = n % mod;
        n /= mod;
        data[2] = n;
        return *this;
    }
    LongInt operator+ (const LL& num)
    {
        LL n = num;
        LongInt tmp = *this;
        tmp.data[0] += n;
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator+ (const LongInt& b)
    {
        LongInt tmp = *this;
        tmp.data[0] += b.data[0];
        tmp.data[1] += b.data[1];
        tmp.data[2] += b.data[2];
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator- (const LongInt& b)
    {
        LongInt tmp = *this;
        tmp.data[0] -= b.data[0];
        if (tmp.data[0] < 0)
        {
            tmp.data[1]--;
            tmp.data[0] += mod;
        }
        tmp.data[1] -= b.data[1];
        if (tmp.data[1] < 0)
        {
            tmp.data[2]--;
            tmp.data[1] += mod;
        }
        tmp.data[2] -= b.data[2];
        return tmp;
    }
    LongInt operator* (const LL num)
    {
        LL n = num;
        LongInt tmp = *this;
        tmp.data[0] *= num;
        tmp.data[1] *= num;
        tmp.data[2] *= num;
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator*= (const LL num)
    {
        *this = *this * num;
        return *this;
    }
    LongInt operator/ (const LL num)
    {
        LongInt tmp = *this;
        tmp.data[1] += tmp.data[2] % num * mod;
        tmp.data[2] /= num;
        tmp.data[0] += tmp.data[1] % num * mod;
        tmp.data[1] /= num;
        tmp.data[0] /= num;
        return tmp;
    }
    void fillzero(int n)
    {
        char str[digit * 2];
        sprintf(str, "%d", n);
        for (int i = 1; i <= digit - strlen(str); i++)
        {
            printf("%d", 0);
        }
        printf("%s", str);
    }
    void print()
    {
        if (data[2] > 0)
        {
            printf("%d", data[2]);
            fillzero(data[1]);
            fillzero(data[0]);
        }
        else if (data[1] > 0)
        {
            printf("%d", data[1]);
            fillzero(data[0]);
        }
        else
        {
            printf("%d", data[0]);
        }
    }
};

const LL pow2[maxn] = {1, 2, 4, 8, 16, 32, 64, 128,
                       256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
                       65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
                       16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648,
                       4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888,
                       1099511627776, 2199023255552
                      };
/*const ULL sum[maxn] = {3, 5, 11, 29, 83, 245, 731, 2189,
                       6563, 19685, 59051, 177149, 531443, 1594325, 4782971, 14348909,
                       43046723, 129140165, 387420491, 1162261469, 3486784403, 10460353205, 31381059611, 94143178829,
                       282429536483, 847288609445, 2541865828331, 7625597484989, 22876792454963, 68630377364885, 205891132094651, 617673396283949,
                       1853020188851843, 5559060566555525, 16677181699666571, 50031545098999709, 150094635296999123, 450283905890997365, 1350851717672992091, 4052555153018976269,
                       12157665459056928803
                      };*/
LongInt sum[maxn];

int found_pow2(ULL n)
{
    return int(log(n) / log(2));
}

LongInt Bisearch(LL l, LL r, LongInt ls, LongInt rs, LL key) // [ l , r ) 
{
    while (l + 1 < r)
    {
        ULL mid = (l + r) >> 1;
        if (key < mid)
        {
            r = mid;
            rs = (rs - ls) / 3 + ls;
        }
        else
        {
            l = mid;
            ls = (rs - ls) / 3 + ls;
        }
    }
    return ls;
}

LongInt solve(LL n)
{
    if (n < 0)
    {
        return 0;
    }
    if (!n)
    {
        return 1;
    }
    int k = found_pow2(n + 1);
    LongInt ls = sum[k];
    LongInt rs = sum[k + 1];
    return Bisearch(pow2[k], pow2[k + 1], ls, rs, n + 1);
}

void init()
{
    LongInt tmp = 1;
    for (int i = 0; i < maxn; i++)
    {
        sum[i] = tmp;
        tmp *= 3;
    }
}

int main()
{
    init();
    LL n, m;
    while (cin >> n >> m)
    {
        if (!n && !m)
        {
            break;
        }
        LongInt ans = solve(m) - solve(n - 1);
        ans.print();
        puts("");
    }
    return 0;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 239 words)

看起来比较舒服的矩阵乘法模板

转载源页面
poj 3070

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

#define SIZE 4 
#define mod 10000

using namespace std;

struct MATRIX
{
    int mt[SIZE][SIZE];
    int x,y;
}ans,def;

int n;

inline MATRIX operator *(MATRIX a,MATRIX b)
{
    MATRIX c;
    memset(c.mt,0,sizeof c.mt);
    c.x=a.x; c.y=b.y;
    for(int i=1;i<=a.x;i++)
        for(int j=1;j<=b.y;j++)
            for(int k=1;k<=a.y;k++)
                c.mt[i][j]=(c.mt[i][j]+(a.mt[i][k]%mod)*(b.mt[k][j]%mod))%mod;
    return c;
}

inline MATRIX operator +(MATRIX a,MATRIX b)
{
    MATRIX c;
    memset(c.mt,0,sizeof c.mt);
    c.x=a.x; c.y=a.y;
    for(int i=1;i<=c.x;i++)
        for(int j=1;j<=c.y;j++)
            c.mt[i][j]=(a.mt[i][j]+b.mt[i][j])%mod;
    return c;
}

inline bool prt(MATRIX &c)
{
    for(int i=1;i<=c.x;i++)
    {
        for(int j=1;j<=c.y;j++) printf("%d ",c.mt[i][j]);
        puts("");
    }
}

void go()
{
    n-=2;
    def.mt[1][1]=def.mt[1][2]=def.mt[2][1]=1;
    def.mt[2][2]=0; def.x=def.y=2;
    ans.mt[1][1]=ans.mt[1][2]=ans.mt[2][1]=1; ans.mt[2][2]=0;
    ans.x=ans.y=2;
    
    while(n)
    {
        if(n&1) ans=ans*def;
        def=def*def;
        n>>=1;
    }
    printf("%d\n",ans.mt[1][1]);
}

int main()
{
    while(scanf("%d",&n))
    {
        if(n==-1) break;
        else if(n==0) puts("0");
        else if(n==1) puts("1");
        else go();
    }
    system("pause");
    return 0;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 167 words)

ACM-ICPC Live Archive Regionals 2014 >> Asia - Kuala Lumpur 6811 - Irrigation Lines

参见：转载前页面

怎么读题时就没发现“每行每列各有一个水阀”？这是把问题转化成二分图模型的关键啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
 
const int MAXN = 110;
char graph[MAXN][MAXN];
bool visited[MAXN];
int nCase, cCase, use[MAXN], m, n;
 
void init() {
    memset(use, -1, sizeof(use));
}
 
void input() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) {
        scanf("%s", graph[i]);
    }
}
 
bool find(int x) {
    for (int j = 0; j < n; j++) {
        if (graph[x][j] == '1' && !visited[j]) {
            visited[j] = true;
 
            if (use[j] == -1 || find(use[j])) {
                use[j] = x;
                return true;
            }
        }
    }
    return false;
}
 
int match() {
    int count = 0;
    for (int i = 0; i < m; i++) {
        memset(visited, false, sizeof(visited));
        if (find(i)) count++;
    }
    return count;
}
 
void solve() {
    printf("Case #%d: %d\n", ++cCase, match());
}
 
int main() {
    scanf("%d", &nCase);
    while (nCase--) {
        init();
        input();
        solve();
 
    }
    return 0;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 173 words)

2015年浙江省大学生程序设计竞赛

像这样搞错映射关系，不是个很好的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))


using namespace std;


typedef long long LL;
const double pi = acos(-1.0);
const int maxn=1e4;
const int inf=99999999;
const double eps=1e-3;


int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};


int ans(int x)
{


  //  cout<<x<<endl ;
    if (x==-1) return 6;
    if (x==0) return 5;
    if (x==1) return 6;
    if (x==2) return 9;
    if (x==3) return 6;
    if (x==4) return 5;
    if (x==5) return 5;
    if (x==6) return 5;
    if (x==7) return 5;
    if (x==8) return 6;
}


int isleap(int y)
{
    if ((y%4==0&&y%100!=0) || y%400==0) return 366;
    else return 365;
}


int fun(int y,int m)
{
    if (m==2)
    {
        if ((y%4==0&&y%100!=0) || y%400==0) return 29;
        else return 28;
    }
    else return month[m];
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int y;
        scanf("%d",&y);
        int day=0;
        for(int i=1928;i<y;i++)
            day+=isleap(i);
        for(int i=1;i<=4;i++)
            day+=fun(y,i);
        day+=1;
        //cout<<day<<' ';
        cout<<ans(day%7)<<endl;
        /*switch (day%7)
        {
        case 0:


        }*/
    }
    return 0;
}
Posted Updated  Semprathlon / Simfae Dean Programinga minute read (About 131 words)

C/C++宏定义的不安全性

早就听说#define有不靠谱之处，平时写代码也对它多有抵触情绪；今日偶然一用，大跌眼镜

1
#define MAX(a,b) (a>b)?a:b

通常预处理器只对宏定义做相应的字符替换，编译器不做语法检查；visual studio 则能在替换后检查语法。
无编译错误，调用的时候无论如何都算不对

1
return MAX(Depth(T->lchild), Depth(T->rchild)) + 1;

加号的运算优先级如何处理？

Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview4
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python11
RMQ1
React2
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
TypeScript2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network2
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×