lightoj1174

maksyuki 发表于 oj 分类，标签: 图论-最短路

27 8月 2015

1174 - Commandos

InputA group of commandos were assigned a critical task. They are to destroy an enemy head quarter. The enemy head quarter consists of several buildings and the buildings are connected by roads. The commandos must visit each building and place a bomb at the base of each building. They start their mission at the base of a particular building and from there they disseminate to reach each building. The commandos must use the available roads to travel between buildings. Any of them can visit one building after another, but they must all gather at a common place when their task in done. In this problem, you will be given the description of different enemy headquarters. Your job is to determine the minimum time needed to complete the mission. Each commando takes exactly one unit of time to move between buildings. You may assume that the time required to place a bomb is negligible. Each commando can carry unlimited number of bombs and there is an unlimited supply of commando troops for the mission.

Input starts with an integer T (≤50), denoting the number of test cases.

The first line of each case starts with a positive integer N (1 ≤ N ≤ 100), where N denotes the number of buildings in the head quarter. The next line contains a positive integer R, where Ris the number of roads connecting two buildings. Each of the next R lines contain two distinct numbers u v (0 ≤ u, v < N), this means there is a road connecting building u to building v. The buildings are numbered from 0 to N-1. The last line of each case contains two integers s d (0 ≤ s, d < N). Where s denotes the building from where the mission starts and d denotes the building where they must meet. You may assume that two buildings will be directly connected by at most one road. The input will be given such that, it will be possible to go from any building to another by using one or more roads.

Output

For each case, print the case number and the minimum time required to complete the mission.

Sample Input

Output for Sample Input

2430 1

2 1

1 3

0 3

0 1

1 0

Case 1: 4Case 2: 1

题目类型：最短路

算法分析：使用SPFA和一个邻接表、一个逆邻接表分别求得最短路径，然后将每个点的两个最短路相加再取最大值，否则会WA！！！！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define i64 long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 300 + 66;


//分别表示顶点v。w和下一个邻接的位置
struct Node
{
    int v, w, next;
};

Node edge[maxn*maxn];
int head[maxn], edgelen;//分别表示顶点的表头节点和边的数量

Node redge[maxn*maxn];
int rhead[maxn], redgelen;

//将所有的数组均初始化为-1
void Init ()
{
    memset (head, -1, sizeof (head));
    memset (edge, -1, sizeof (edge));
    edgelen = 0;

    memset (rhead, -1, sizeof (rhead));
    memset (redge, -1, sizeof (redge));
    redgelen = 0;
}

//使用头插法构建
void AddEdge (int u, int v, int w)
{
    edge[edgelen].v = v;
    edge[edgelen].w = w;
    edge[edgelen].next = head[u];
    head[u] = edgelen++;

    redge[redgelen].v = u;
    redge[redgelen].w = w;
    redge[redgelen].next = rhead[v];
    rhead[v] = redgelen++;
}

//分别表示源点到其他顶点的最短距离、顶点是否在队列中的判断数组、顶点入队列的次数和顶点个数
long long dis[maxn], inq[maxn];
int n, m;

long long rdis[maxn], rinq[maxn];


//数组下标从1开始
void spfa (int s)
{
    for (int i = 1; i <= n; i++)//初始化dis数组和inq数组
    {
        dis[i] = INF;
        inq[i] = 0;
    }

    dis[s] = 0;//将源点的dis数组值初始化为0，重要！！
    queue <int> qu;
    qu.push (s);
    inq[s]++;//将源点标志为在队列中
    while (!qu.empty ())
    {
        int tt = qu.front(); qu.pop (); inq[tt]--;
        int pa = head[tt];
        while (pa != -1)
        {
            int pb = edge[pa].v;
            if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w)//松弛操作
            {
                dis[pb] = dis[tt] + edge[pa].w;
                if (!inq[pb])//如果被松弛的节点不在队列中，则将该节入队
                {
                    qu.push (pb);
                    inq[pb]++;
                }
            }
            pa = edge[pa].next;
        }
    }
}

//数组下标从1开始
void rspfa (int s)
{
    for (int i = 1; i <= n; i++)//初始化dis数组和inq数组
    {
        rdis[i] = INF;
        rinq[i] = 0;
    }

    rdis[s] = 0;//将源点的dis数组值初始化为0，重要！！
    queue <int> qu;
    qu.push (s);
    rinq[s]++;//将源点标志为在队列中
    while (!qu.empty ())
    {
        int tt = qu.front(); qu.pop (); rinq[tt]--;
        int pa = rhead[tt];
        while (pa != -1)
        {
            int pb = redge[pa].v;
            if (rdis[tt] < INF && rdis[pb] > rdis[tt] + redge[pa].w)//松弛操作
            {
                rdis[pb] = rdis[tt] + redge[pa].w;
                if (!rinq[pb])//如果被松弛的节点不在队列中，则将该节入队
                {
                    qu.push (pb);
                    rinq[pb]++;
                }
            }
            pa = redge[pa].next;
        }
    }
}

int main()
{
//    CPPFF;

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        Init ();
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            cin >> u >> v;
            u++, v++;
            AddEdge(u, v, 1);
            AddEdge(v, u, 1);
        }

        int s, e;
        cin >> s >> e;
        spfa (s + 1);
        rspfa (e + 1);

       long long maxval = -INF;
       for (int i = 1; i <= n; i++)
            maxval = max (maxval, dis[i] + rdis[i]);

        cout << "Case " << flag++ <<": " << maxval << endl;
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define i64 long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 300 + 66;

//分别表示顶点v。w和下一个邻接的位置

struct Node

{

int v, w, next;

};

Node edge[maxn*maxn];

int head[maxn], edgelen;//分别表示顶点的表头节点和边的数量

Node redge[maxn*maxn];

int rhead[maxn], redgelen;

//将所有的数组均初始化为-1

void Init ()

{

memset (head, -1, sizeof (head));

memset (edge, -1, sizeof (edge));

edgelen = 0;

memset (rhead, -1, sizeof (rhead));

memset (redge, -1, sizeof (redge));

redgelen = 0;

}

//使用头插法构建

void AddEdge (int u, int v, int w)

{

edge[edgelen].v = v;

edge[edgelen].w = w;

edge[edgelen].next = head[u];

head[u] = edgelen++;

redge[redgelen].v = u;

redge[redgelen].w = w;

redge[redgelen].next = rhead[v];

rhead[v] = redgelen++;

}

//分别表示源点到其他顶点的最短距离、顶点是否在队列中的判断数组、顶点入队列的次数和顶点个数

long long dis[maxn], inq[maxn];

int n, m;

long long rdis[maxn], rinq[maxn];

//数组下标从1开始

void spfa (int s)

{

for (int i = 1; i <= n; i++)//初始化dis数组和inq数组

{

dis[i] = INF;

inq[i] = 0;

}

dis[s] = 0;//将源点的dis数组值初始化为0，重要！！

queue <int> qu;

qu.push (s);

inq[s]++;//将源点标志为在队列中

while (!qu.empty ())

{

int tt = qu.front(); qu.pop (); inq[tt]--;

int pa = head[tt];

while (pa != -1)

{

int pb = edge[pa].v;

if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w)//松弛操作

{

dis[pb] = dis[tt] + edge[pa].w;

if (!inq[pb])//如果被松弛的节点不在队列中，则将该节入队

{

qu.push (pb);

inq[pb]++;

}

pa = edge[pa].next;

}

//数组下标从1开始

void rspfa (int s)

{

for (int i = 1; i <= n; i++)//初始化dis数组和inq数组

{

rdis[i] = INF;

rinq[i] = 0;

}

rdis[s] = 0;//将源点的dis数组值初始化为0，重要！！

queue <int> qu;

qu.push (s);

rinq[s]++;//将源点标志为在队列中

while (!qu.empty ())

{

int tt = qu.front(); qu.pop (); rinq[tt]--;

int pa = rhead[tt];

while (pa != -1)

{

int pb = redge[pa].v;

if (rdis[tt] < INF && rdis[pb] > rdis[tt] + redge[pa].w)//松弛操作

{

rdis[pb] = rdis[tt] + redge[pa].w;

if (!rinq[pb])//如果被松弛的节点不在队列中，则将该节入队

{

qu.push (pb);

rinq[pb]++;

}

pa = redge[pa].next;

}

int main()

{

// CPPFF;

int t, flag = 1;

cin >> t;

while (t--)

{

Init ();

cin >> n >> m;

for (int i = 1; i <= m; i++)

{

int u, v;

cin >> u >> v;

u++, v++;

AddEdge(u, v, 1);

AddEdge(v, u, 1);

}

int s, e;

cin >> s >> e;

spfa (s + 1);

rspfa (e + 1);

long long maxval = -INF;

for (int i = 1; i <= n; i++)

maxval = max (maxval, dis[i] + rdis[i]);

cout << "Case " << flag++ <<": " << maxval << endl;

}

return 0;

}

lightoj1164

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

27 8月 2015

1164 - Horrible Queries

0 x y v - you have to add v to all numbers in the range of x to y (inclusive), where x and y are two indexes of the array.World is getting more evil and it's getting tougher to get into the Evil League of Evil. Since the legendary Bad Horse has retired, now you have to correctly answer the evil questions of Dr. Horrible, who has a PhD in horribleness (but not in Computer Science). You are given an array of n elements, which are initially all 0. After that you will be given q commands. They are -

1 x y - output a line containing a single integer which is the sum of all the array elements between x and y (inclusive).

The array is indexed from 0 to n - 1.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 10⁵) and q (1 ≤ q ≤ 50000). Each of the next q lines contains a task in one of the following form:

0 x y v (0 ≤ x ≤ y < n, 1 ≤ v ≤ 1000)

1 x y (0 ≤ x ≤ y < n)

Output

For each case, print the case number first. Then for each query '1 x y', print the sum of all the array elements between x and y.

Sample Input

Output for Sample Input

210 50 0 9 101 1 6

0 3 7 2

0 4 5 1

1 5 5

20 3

0 10 12 1

1 11 12

1 19 19

Case 1:6013Case 2:

Note

Dataset is huge. Use faster i/o methods.

题目类型：线段树

算法分析：线段树的成段更新和区间求和问题，直接按照题目的要求求解即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;


const int maxn = 100000 + 66;
long long lazy[maxn<<2];
long long sum[maxn<<2];

int n, q;

void PushUp (int rt)
{
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void PushDown (int rt, int l, int m, int r)
{
    if (lazy[rt])
    {
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        sum[rt<<1] += lazy[rt] * (m - l + 1);
        sum[rt<<1|1] += lazy[rt] * (r - m);
        lazy[rt] = 0;
    }
}

/*void Build (int rt, int l, int r)
{
    lazy[rt] = 0;

    if (l == r)
    {
        scanf ("%lld", &sum[rt]);
        return ;
    }

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);

	Build (lson);
	Build (rson);
	PushUp (rt);
}*/

void UpDate (int rt, int l, int r, int L, int R, int add)
{
	if (L <= l && r <= R)
    {
		lazy[rt] += add;
		sum[rt] += add * (r - l + 1);
		return ;
	}

	int m = (l + r) >> 1;
    PushDown (rt, l, m, r);

    if (L <= m)
        UpDate (lson, L, R, add);

    if (R > m)
        UpDate (rson, L, R, add);

	PushUp (rt);
}

long long Query (int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
    {
        return sum[rt];
    }

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);
    long long ans = 0;

    if (L <= m)
        ans += Query (lson, L, R);

    if (R > m)
        ans += Query (rson, L, R);

return ans;
}



int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:\n", flag++);


        scanf ("%d%d", &n, &q);

        memset (sum, 0, sizeof (sum));
        memset (lazy, 0, sizeof (lazy));

        int i;
        for (i = 0; i < q; i++)
        {
            int cmd;
            scanf ("%d", &cmd);

            if (cmd == 0)
            {
                int val_a, val_b, val;
                scanf ("%d%d%d", &val_a, &val_b, &val);
                val_a++, val_b++;
                UpDate (1, 1, n, val_a, val_b, val);
            }

            else
            {
                int val_a, val_b;
                scanf ("%d%d", &val_a, &val_b);
                val_a++, val_b++;
                printf ("%lld\n", Query (1, 1, n, val_a, val_b));
            }
        }
    }

return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 100000 + 66;

long long lazy[maxn<<2];

long long sum[maxn<<2];

int n, q;

void PushUp (int rt)

{

sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void PushDown (int rt, int l, int m, int r)

{

if (lazy[rt])

{

lazy[rt<<1] += lazy[rt];

lazy[rt<<1|1] += lazy[rt];

sum[rt<<1] += lazy[rt] * (m - l + 1);

sum[rt<<1|1] += lazy[rt] * (r - m);

lazy[rt] = 0;

}

/*void Build (int rt, int l, int r)

{

lazy[rt] = 0;

if (l == r)

{

scanf ("%lld", &sum[rt]);

return ;

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

Build (lson);

Build (rson);

PushUp (rt);

}*/

void UpDate (int rt, int l, int r, int L, int R, int add)

{

if (L <= l && r <= R)

{

lazy[rt] += add;

sum[rt] += add * (r - l + 1);

return ;

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

if (L <= m)

UpDate (lson, L, R, add);

if (R > m)

UpDate (rson, L, R, add);

PushUp (rt);

}

long long Query (int rt, int l, int r, int L, int R)

{

if (L <= l && r <= R)

{

return sum[rt];

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

long long ans = 0;

if (L <= m)

ans += Query (lson, L, R);

if (R > m)

ans += Query (rson, L, R);

return ans;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

scanf ("%d%d", &n, &q);

memset (sum, 0, sizeof (sum));

memset (lazy, 0, sizeof (lazy));

int i;

for (i = 0; i < q; i++)

{

int cmd;

scanf ("%d", &cmd);

if (cmd == 0)

{

int val_a, val_b, val;

scanf ("%d%d%d", &val_a, &val_b, &val);

val_a++, val_b++;

UpDate (1, 1, n, val_a, val_b, val);

}

else

{

int val_a, val_b;

scanf ("%d%d", &val_a, &val_b);

val_a++, val_b++;

printf ("%lld\n", Query (1, 1, n, val_a, val_b));

}

return 0;

}

lightoj1140

maksyuki 发表于 oj 分类，标签: 组合数学-计数

27 8月 2015

1140 - How Many Zeroes?

InputJimmy writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?

Input starts with an integer T (≤ 11000), denoting the number of test cases.

Each case contains two unsigned 32-bit integers m and n, (m ≤ n).

Output

For each case, print the case number and the number of zeroes written down by Jimmy.

Sample Input

Output for Sample Input

510 11100 2000 500

1234567890 2345678901

0 4294967295

Case 1: 1Case 2: 22Case 3: 92Case 4: 987654304

Case 5: 3825876150

题目类型：组合计数

算法分析：每次从小到大判断N的每一位上的数字，如果当前位上的数字不为0，则该位左边的所有的数字都可以和该位右边的每一位上的数字构成一个合理的结果(每一位上有0~9共10个数)。如果当前位上的数字为0，则该位左边只有小于当前数1的个数可以和右边的right+1个数构成一个合理的结果

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 6000 + 66;

long long Get (long long val)
{
    if (val < 0)
        return 0;

    long long cnt = 1, right = 0, res = 1;
    while (val >= 10)
    {
        long long tt = val % 10;
        val /= 10;
        if (tt)
            res += val * cnt;

        else
            res += (val - 1) * cnt + right + 1;

        right += tt * cnt;
        cnt *= 10;
    }

    return res;
}


int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    long long a, b;
    while (t--)
    {
        cin >> a >> b;

        cout << "Case " << flag++ << ": " << Get (b) - Get (a - 1) << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 6000 + 66;

long long Get (long long val)

{

if (val < 0)

return 0;

long long cnt = 1, right = 0, res = 1;

while (val >= 10)

{

long long tt = val % 10;

val /= 10;

if (tt)

res += val * cnt;

else

res += (val - 1) * cnt + right + 1;

right += tt * cnt;

cnt *= 10;

}

return res;

}

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

long long a, b;

while (t--)

{

cin >> a >> b;

cout << "Case " << flag++ << ": " << Get (b) - Get (a - 1) << endl;

}

return 0;

}

lightoj1131

maksyuki 发表于 oj 分类，标签: 数值-矩阵快速幂取模

27 8月 2015

1131 - Just Two Functions

Find f_n % M and g_n % M. (% stands for the modulo operation.)Let f_n = a₁ * f_n-1 + b₁ * f_n-2 + c₁ * g_n-3g_n = a₂ * g_n-1 + b₂ * g_n-2 + c₂ * f_n-3

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a blank line. Next line contains three integers a₁ b₁ c₁ (0 ≤ a₁, b₁, c₁ < 25000). Next line contains three integers a₂ b₂ c₂ (0 ≤ a₂, b₂, c₂ < 25000). Next line contains three integers f₀ f₁ f₂ (0 ≤ f₀, f₁, f₂ < 25000). Next line contains three integers g₀ g₁ g₂ (0 ≤ g₀, g₁, g₂ < 25000). The next line contains an integer M (1 ≤ M < 25000).

Next line contains an integer q (1 ≤ q ≤ 100) denoting the number of queries. Next line contains q space separated integers denoting n. Each of these integers is non-negative and less than 2³¹.

Output

For each case, print the case number in a line. Then for each query, you have to print one line containing f_n % M and g_n % M.

Sample Input

Output for Sample Input

21 1 00 0 00 1 1

0 0 0

20000

1 2 3 4 5 6 7 8 9 10

1 1 1

2 2 2

20000

2 4 6 8 10

Case 1:1 01 02 03 0

5 0

8 0

13 0

21 0

34 0

55 0

Case 2:

2 2

10 10

34 34

114 114

386 386

题目类型：矩阵快速幂取模

算法分析：由于两个递推式之间不是独立的，所以需要将两个递推式用一个矩阵乘幂表示！！！之后直接上模板即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
//const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 6;

long long n = 6;//表示方阵的尺寸，必须恰好为运算的大小

long long MOD;
//申请变量
struct Mat
{
    long long mat[maxn][maxn];
};


//重载Mat乘法运算
Mat operator * (Mat a, Mat b)
{
    Mat c;
    memset (c.mat, 0, sizeof (c.mat));
    for (long long k = 0; k < n; k++)
    {
        for (long long i = 0; i < n; i++)
        {
            if (a.mat[i][k] == 0) continue;

            for (long long j = 0; j < n; j++)
            {
                if (b.mat[k][j] == 0) continue;

                c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD;
            }
        }
    }
return c;
}

//重载Mat乘幂运算
Mat operator ^ (Mat a, long long k)
{
    Mat c;
    for (long long i = 0; i < n; i++)
        for(long long j = 0; j < n; j++)
        c.mat[i][j] = (i == j);

    while (k)
    {
        if(k & 1)
            c = c * a;

        a = a * a;
        k >>= 1;
    }

return c;
}

int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    cin >> t;

    while(t--)
	{
        cout << "Case " << flag++ << ":" << endl;
        long long a1, b1, c1, a2, b2, c2, f0, f1, f2, g0, g1, g2;

        cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2 >> f0 >> f1 >> f2 >> g0 >> g1 >> g2 >> MOD;

		Mat aa, a0;
        aa.mat[0][0] = a1, aa.mat[0][1] = b1, aa.mat[0][2] = 0, aa.mat[0][3] = 0, aa.mat[0][4] = 0, aa.mat[0][5] = c1;
        aa.mat[1][0] = 1, aa.mat[1][1] = 0, aa.mat[1][2] = 0, aa.mat[1][3] = 0, aa.mat[1][4] = 0, aa.mat[1][5] = 0;
        aa.mat[2][0] = 0, aa.mat[2][1] = 1, aa.mat[2][2] = 0, aa.mat[2][3] = 0, aa.mat[2][4] = 0, aa.mat[2][5] = 0;
		aa.mat[3][0] = 0, aa.mat[3][1] = 0, aa.mat[3][2] = c2, aa.mat[3][3] = a2, aa.mat[3][4] = b2,  aa.mat[3][5] = 0;
		aa.mat[4][0] = 0, aa.mat[4][1] = 0, aa.mat[4][2] = 0, aa.mat[4][3] = 1, aa.mat[4][4] = 0, aa.mat[4][5] = 0;
		aa.mat[5][0] = 0, aa.mat[5][1] = 0, aa.mat[5][2] = 0, aa.mat[5][3] = 0, aa.mat[5][4] = 1, aa.mat[5][5] = 0;

		a0.mat[0][0] = f2, a0.mat[1][0] = f1, a0.mat[2][0] = f0, a0.mat[3][0] = g2, a0.mat[4][0] = g1, a0.mat[5][0] = g0;

        int q;
        cin >> q;

		long long tt;
		Mat res;
        for (int i = 1; i <= q; i++)
		{
			cin >> tt;
//			cout << tt << endl;

            if (tt == 0)
				cout << f0 % MOD << " " << g0 % MOD << endl;

			else if (tt == 1)
				cout << f1 % MOD << " " << g1 % MOD << endl;

			else if (tt == 2)
				cout << f2 % MOD << " " << g2 % MOD << endl;

			else
			{
				res = aa ^ (tt - 2);
				res = res * a0;
				cout << res.mat[0][0] % MOD << " " << res.mat[3][0] % MOD << endl;
			}
		}
	}
return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

//const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 6;

long long n = 6;//表示方阵的尺寸，必须恰好为运算的大小

long long MOD;

//申请变量

struct Mat

{

long long mat[maxn][maxn];

};

//重载Mat乘法运算

Mat operator * (Mat a, Mat b)

{

Mat c;

memset (c.mat, 0, sizeof (c.mat));

for (long long k = 0; k < n; k++)

{

for (long long i = 0; i < n; i++)

{

if (a.mat[i][k] == 0) continue;

for (long long j = 0; j < n; j++)

{

if (b.mat[k][j] == 0) continue;

c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD;

}

return c;

}

//重载Mat乘幂运算

Mat operator ^ (Mat a, long long k)

{

Mat c;

for (long long i = 0; i < n; i++)

for(long long j = 0; j < n; j++)

c.mat[i][j] = (i == j);

while (k)

{

if(k & 1)

c = c * a;

a = a * a;

k >>= 1;

}

return c;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

cin >> t;

while(t--)

{

cout << "Case " << flag++ << ":" << endl;

long long a1, b1, c1, a2, b2, c2, f0, f1, f2, g0, g1, g2;

cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2 >> f0 >> f1 >> f2 >> g0 >> g1 >> g2 >> MOD;

Mat aa, a0;

aa.mat[0][0] = a1, aa.mat[0][1] = b1, aa.mat[0][2] = 0, aa.mat[0][3] = 0, aa.mat[0][4] = 0, aa.mat[0][5] = c1;

aa.mat[1][0] = 1, aa.mat[1][1] = 0, aa.mat[1][2] = 0, aa.mat[1][3] = 0, aa.mat[1][4] = 0, aa.mat[1][5] = 0;

aa.mat[2][0] = 0, aa.mat[2][1] = 1, aa.mat[2][2] = 0, aa.mat[2][3] = 0, aa.mat[2][4] = 0, aa.mat[2][5] = 0;

aa.mat[3][0] = 0, aa.mat[3][1] = 0, aa.mat[3][2] = c2, aa.mat[3][3] = a2, aa.mat[3][4] = b2, aa.mat[3][5] = 0;

aa.mat[4][0] = 0, aa.mat[4][1] = 0, aa.mat[4][2] = 0, aa.mat[4][3] = 1, aa.mat[4][4] = 0, aa.mat[4][5] = 0;

aa.mat[5][0] = 0, aa.mat[5][1] = 0, aa.mat[5][2] = 0, aa.mat[5][3] = 0, aa.mat[5][4] = 1, aa.mat[5][5] = 0;

a0.mat[0][0] = f2, a0.mat[1][0] = f1, a0.mat[2][0] = f0, a0.mat[3][0] = g2, a0.mat[4][0] = g1, a0.mat[5][0] = g0;

int q;

cin >> q;

long long tt;

Mat res;

for (int i = 1; i <= q; i++)

{

cin >> tt;

// cout << tt << endl;

if (tt == 0)

cout << f0 % MOD << " " << g0 % MOD << endl;

else if (tt == 1)

cout << f1 % MOD << " " << g1 % MOD << endl;

else if (tt == 2)

cout << f2 % MOD << " " << g2 % MOD << endl;

else

{

res = aa ^ (tt - 2);

res = res * a0;

cout << res.mat[0][0] % MOD << " " << res.mat[3][0] % MOD << endl;

}

return 0;

}

lightoj1129

maksyuki 发表于 oj 分类，标签: 字符串-Trie树

27 8月 2015

1129 - Consistency Checker

123SETI is receiving some weird signals for the past few days. After converting them to our number system they found out that some numbers are repeating. Due to travelling millions of miles signal gets distorted. Now they asked you check the consistency of their data sets. The consistency is that, no number is the prefix another number in that data set. Let's consider a data set:

5123456
123456

In this data set, numbers not consistent, because the first number is the prefix of the third one.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with an integer n (1 ≤ n ≤ 10000) denoting the total numbers in their list. Each of the next n lines contains one unique phone number. A number is a sequence of digits and has length from 1 to 10.

Output

For each case, print the case number and 'YES' if the list is consistent or 'NO' if it's not.

Sample Input

Output for Sample Input

2391197625999

91125426

113

12340

123440

12345

98346

Case 1: NOCase 2: YES

题目类型：Trie树

算法分析：将所有的单词插入到Trie树中，然后对于每个输入中的单词，查询其终止节点是否有后继节点即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 10000 + 66;

char ss[maxn][16];

struct Trie
{
    int next[maxn*10+66][10];
	int len, root;

	int newnode ()
	{
        for (int i = 0; i < 10; i++)
			next[len][i] = -1;

		len++;
		return len - 1;
	}

    void init ()
    {
        len = 0;
        root = newnode ();
    }

    void Insert (char *s)
    {
        int p = root;
        for (int i = 0; s[i]; i++)
		{
            if (next[p][s[i]-'0'] == -1)
                next[p][s[i]-'0'] = newnode ();

			p = next[p][s[i]-'0'];
		}
    }

    bool Query (char *s)
    {
        int p = root;
        for (int i = 0; s[i]; i++)
		{
            if (next[p][s[i]-'0'] == -1)
				return false;

			p = next[p][s[i]-'0'];
		}

		for (int i = 0; i < 10; i++)
            if (next[p][i] != -1)
				return true;

		return false;
    }
};

Trie aa;

int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;

    cin >> t;

    while (t--)
	{
		cout <<"Case " << flag++ << ": ";

        aa.init ();

        int n;
        cin >>n;
        for (int i = 1; i <= n; i++)
		{
			cin >> ss[i];
			aa.Insert(ss[i]);
		}

		bool is_valid = true;
        for (int i = 1; i <= n; i++)
		{
            if (aa.Query(ss[i]))
			{
				is_valid = false;
				break;
			}
		}

		if (is_valid)
			cout << "YES" << endl;

		else
			cout << "NO" << endl;

	}
return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 10000 + 66;

char ss[maxn][16];

struct Trie

{

int next[maxn*10+66][10];

int len, root;

int newnode ()

{

for (int i = 0; i < 10; i++)

next[len][i] = -1;

len++;

return len - 1;

}

void init ()

{

len = 0;

root = newnode ();

}

void Insert (char *s)

{

int p = root;

for (int i = 0; s[i]; i++)

{

if (next[p][s[i]-'0'] == -1)

next[p][s[i]-'0'] = newnode ();

p = next[p][s[i]-'0'];

}

bool Query (char *s)

{

int p = root;

for (int i = 0; s[i]; i++)

{

if (next[p][s[i]-'0'] == -1)

return false;

p = next[p][s[i]-'0'];

}

for (int i = 0; i < 10; i++)

if (next[p][i] != -1)

return true;

return false;

}

};

Trie aa;

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

cin >> t;

while (t--)

{

cout <<"Case " << flag++ << ": ";

aa.init ();

int n;

cin >>n;

for (int i = 1; i <= n; i++)

{

cin >> ss[i];

aa.Insert(ss[i]);

}

bool is_valid = true;

for (int i = 1; i <= n; i++)

{

if (aa.Query(ss[i]))

{

is_valid = false;

break;

}

if (is_valid)

cout << "YES" << endl;

else

cout << "NO" << endl;

}

return 0;

}

lightoj1127

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

27 8月 2015

1127 - Funny Knapsack

InputGiven n integers and a knapsack of weight W, you have to count the number of combinations for which you can add the items in the knapsack without overflowing the weight.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 30) and W (1 ≤ W ≤ 2 * 10⁹) and the next line will contain n integers separated by spaces. The integers will be non negative and less than 10⁹.

Output

For each set of input, print the case number and the number of possible combinations.

Sample Input

Output for Sample Input

31 111 12

3 10

1 2 4

Case 1: 2Case 2: 1Case 3: 8

题目类型：折半枚举

算法分析：由于物品的个数比较少，所以将物品大致分为两堆，然后分别枚举组合的情况，最后再查找小于w的组合个数

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;


const int maxn = 60000 + 66;

long long ans[36], sa[maxn], sb[maxn], len_a, len_b;
long long n, w;

void DFS (int flag, int cur, long long sum)
{
    if (cur == flag)
    {
        if (flag == n / 2)
            sa[len_a++] = sum;

        else
            sb[len_b++] = sum;

        return ;
    }


    DFS (flag, cur + 1, sum);
    DFS (flag, cur + 1, sum + ans[cur]);

}


int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {

        cin >> n >> w;
        int i;
        for (i = 0; i < n; i++)
            cin >> ans[i];

        len_a = len_b = 0;

        DFS (n / 2, 0, 0);
        DFS (n, n / 2 , 0);

        sort (sa, sa + len_a);

        long long sum = 0;

        for (i = 0; i < len_b; i++)
        {
            sum += upper_bound (sa, sa + len_a, w - sb[i]) - sa;
        }

        cout << "Case " << flag++ << ": " << sum << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 60000 + 66;

long long ans[36], sa[maxn], sb[maxn], len_a, len_b;

long long n, w;

void DFS (int flag, int cur, long long sum)

{

if (cur == flag)

{

if (flag == n / 2)

sa[len_a++] = sum;

else

sb[len_b++] = sum;

return ;

}

DFS (flag, cur + 1, sum);

DFS (flag, cur + 1, sum + ans[cur]);

}

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cin >> n >> w;

int i;

for (i = 0; i < n; i++)

cin >> ans[i];

len_a = len_b = 0;

DFS (n / 2, 0, 0);

DFS (n, n / 2 , 0);

sort (sa, sa + len_a);

long long sum = 0;

for (i = 0; i < len_b; i++)

{

sum += upper_bound (sa, sa + len_a, w - sb[i]) - sa;

}

cout << "Case " << flag++ << ": " << sum << endl;

}

return 0;

}

lightoj1116

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1116 - Ekka Dokka

They want to divide the cake such that N * M = W, where W is the dashing factor set by them. Now you know their dashing factor, you have to find whether they can buy the desired cake or not.Ekka and his friend Dokka decided to buy a cake. They both love cakes and that's why they want to share the cake after buying it. As the name suggested that Ekka is very fond of odd numbers and Dokka is very fond of even numbers, they want to divide the cake such that Ekka gets a share of N square centimeters and Dokka gets a share of M square centimeters whereN is odd and M is even. Both N and M are positive integers.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains an integer W (2 ≤ W < 2⁶³). And W will not be a power of 2.

Output

For each case, print the case number first. After that print "Impossible" if they can't buy their desired cake. If they can buy such a cake, you have to print N and M. If there are multiple solutions, then print the result where M is as small as possible.

Sample Input	Output for Sample Input
310512	Case 1: 5 2Case 2: ImpossibleCase 3: 3 4

题目类型：位运算

算法分析：直接从小到大枚举所有的合数约数并判断时间复杂度是O(n)的，会TLE。这里使用的方法是首先判断n是否是偶数，如果不是则直接退出判断，输出Impossible；反之则将n左移一位判断移位后的n是否是奇数，如果是则找到，直接退出输出答案即可；反之则继续判断。该方法的时间复杂度也是O(n)的，不过这里的n表示的是输入数的二进制位数，而二进制位数不超过63，所以不会TLE

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 10000007;

const int maxn = 1000 + 66;

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        long long n;
        cin >> n;
        cout << "Case " << flag++ << ": ";

        bool is_find = false;
        long long temp = n;

        while (1)
        {
            if (temp & 1)
                break;

            temp >>= 1;
            if (temp & 1)
            {
                is_find = true;
                break;
            }
        }

        if (is_find)
            cout << temp << " " << n / temp << endl;

        else
            cout << "Impossible" << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 10000007;

const int maxn = 1000 + 66;

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

long long n;

cin >> n;

cout << "Case " << flag++ << ": ";

bool is_find = false;

long long temp = n;

while (1)

{

if (temp & 1)

break;

temp >>= 1;

if (temp & 1)

{

is_find = true;

break;

}

if (is_find)

cout << temp << " " << n / temp << endl;

else

cout << "Impossible" << endl;

}

return 0;

}

lightoj1113

maksyuki 发表于 oj 分类，标签: 数据结构-栈/单调

27 8月 2015

1113 - Discover the Web

BACK: If the backward stack is empty, the command is ignored. Otherwise, push the current page on the top of the forward stack. Pop the page from the top of the backward stack, making it the new current page.Standard web browsers contain features to move backward and forward among the pages recently visited. One way to implement these features is to use two stacks to keep track of the pages that can be reached by moving backward and forward. You are asked to implement this. The commands are:

FORWARD: If the forward stack is empty, the command is ignored. Otherwise, push the current page on the top of the backward stack. Pop the page from the top of the forward stack, making it the new current page.
VISIT <url>: Push the current page on the top of the backward stack, and make the URL specified the new current page. The forward stack is emptied.
QUIT: Quit the browser.

The browser initially loads the web page at the URL 'http://www.lightoj.com/'

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains some commands. The keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. URLs have no whitespace and have at most 50 characters. The end of case is indicated by the QUIT command and it shouldn't be processed. Each case contains at most 100 lines.

Output

For each case, print the case number first. For each command, print the URL of the current page (in a line) after the command is executed if the command is not ignored. Otherwise, print'Ignored'.

Sample Input

Output for Sample Input

1VISIT http://uva.onlinejudge.org/VISIT http://topcoder.com/BACK

BACK

FORWARD

VISIT http://acm.sgu.ru/

BACK

FORWARD

QUIT

Case 1:http://uva.onlinejudge.org/http://topcoder.com/http://uva.onlinejudge.org/

http://www.lightoj.com/

Ignored

http://uva.onlinejudge.org/

http://acm.sgu.ru/

http://uva.onlinejudge.org/

http://www.lightoj.com/

http://uva.onlinejudge.org/

http://acm.sgu.ru/

Ignored

题目类型：简单栈模拟

算法分析：直接按照题目所说的方式进行栈模拟即可

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        string cmd, cur = "http://www.lightoj.com/";
        stack <string> fs, bs;

        cout << "Case " << flag++ << ":" << endl;

        while (cin >> cmd)
        {
            bool is_valid = true;

            if (cmd == "QUIT")
                break;

            else if (cmd == "VISIT")
            {
                string temp;
                cin >> temp;
                bs.push (cur);
                cur = temp;

                while (!fs.empty ())
                    fs.pop ();
            }

            else if (cmd == "BACK")
            {
                if (!bs.empty ())
                {
                    fs.push (cur);
                    string temp = bs.top ();
                    bs.pop ();
                    cur = temp;
                }

                else
                    is_valid = false;
            }

            else if (cmd == "FORWARD")
            {
                if (!fs.empty ())
                {
                    bs.push (cur);
                    string temp = fs.top ();
                    fs.pop ();
                    cur = temp;
                }

                else
                    is_valid = false;
            }

            if (is_valid)
                cout << cur << endl;

            else
                cout << "Ignored" << endl;
        }
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

string cmd, cur = "http://www.lightoj.com/";

stack <string> fs, bs;

cout << "Case " << flag++ << ":" << endl;

while (cin >> cmd)

{

bool is_valid = true;

if (cmd == "QUIT")

break;

else if (cmd == "VISIT")

{

string temp;

cin >> temp;

bs.push (cur);

cur = temp;

while (!fs.empty ())

fs.pop ();

}

else if (cmd == "BACK")

{

if (!bs.empty ())

{

fs.push (cur);

string temp = bs.top ();

bs.pop ();

cur = temp;

}

else

is_valid = false;

}

else if (cmd == "FORWARD")

{

if (!fs.empty ())

{

bs.push (cur);

string temp = fs.top ();

fs.pop ();

cur = temp;

}

else

is_valid = false;

}

if (is_valid)

cout << cur << endl;

else

cout << "Ignored" << endl;

}

return 0;

}

lightoj1112

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

27 8月 2015

1112 - Curious Robin Hood

Now each time he can he can do one of the three tasks.Robin Hood likes to loot rich people since he helps the poor people with this money. Instead of keeping all the money together he does another trick. He keeps n sacks where he keeps this money. The sacks are numbered from 0 to n-1.

1) Give all the money of the i^th sack to the poor, leaving the sack empty.

2) Add new amount (given in input) in the i^th sack.

3) Find the total amount of money from i^th sack to j^th sack.

Since he is not a programmer, he seeks your help.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 10⁵) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers in the range [0, 1000]. The i^th integer denotes the initial amount of money in the i^th sack (0 ≤ i < n).

Each of the next q lines contains a task in one of the following form:

1 i Give all the money of the i^th (0 ≤ i < n) sack to the poor.

2 i v Add money v (1 ≤ v ≤ 1000) to the i^th (0 ≤ i < n) sack.

3 i j Find the total amount of money from i^th sack to j^th sack (0 ≤ i ≤ j < n).

Output

For each test case, print the case number first. If the query type is 1, then print the amount of money given to the poor. If the query type is 3, print the total amount from i^th to j^th sack.

Sample Input

Output for Sample Input

15 63 2 1 4 51 4

2 3 4

3 0 3

1 2

3 0 4

1 1

Case 1:5141

Notes

Dataset is huge, use faster I/O methods.

题目类型：线段树

算法分析：线段树简单的单点更新和区间求和问题，直接建树，更新和查询即可

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const int maxn = 100000 +66;

int sum[maxn<<2];
int giveval;

void PushUp (int rt)
{
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}


void Build (int rt, int l, int r)
{
    if (l == r)
    {
        scanf ("%d", &sum[rt]);

        return;
    }

    int m = (l + r) >> 1;
    Build (lson);
    Build (rson);
    PushUp (rt);
}

void UpDate (int rt, int l, int r, int val, int num)
{
    if (l == r)
    {
        sum[rt] += num;
        return ;
    }

    int m = (l + r) >> 1;
    if (val <= m)
        UpDate (lson, val, num);

    else
        UpDate (rson, val, num);

    PushUp (rt);
}

void Give (int rt, int l, int r, int val)
{
    if (l == r)
    {
        giveval = sum[rt];
        sum[rt] = 0;
        return ;
    }

    int m = (l + r) >> 1;
    if (val <= m)
        Give (lson, val);

    else
        Give (rson, val);

    PushUp (rt);
}


int Query (int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
        return sum[rt];

    int m = (l + r) >> 1;
    int ans = 0;

    if (L <= m)
        ans += Query (lson, L, R);

    if (R > m)
        ans += Query (rson, L, R);

return ans;
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag =1;
    scanf ("%d", &t);

    while (t--)
    {

        printf ("Case %d:\n", flag++);


        int n, q;
        scanf ("%d%d", &n, &q);

      Build (1, 1, n);

       int i, oper, val_a, val_b;
       for (i = 0; i < q; i++)
       {
            scanf ("%d", &oper);

            if (oper == 1)
            {
                scanf ("%d", &val_a);
                val_a++;
                Give (1, 1, n, val_a);
                printf ("%d\n", giveval);
            }

            else if (oper == 2)
            {
                scanf ("%d%d", &val_a, &val_b);
                val_a++;
                UpDate (1, 1, n, val_a, val_b);
            }

            else if (oper == 3)
            {
                scanf ("%d%d", &val_a, &val_b);
                val_a++, val_b++;
                printf ("%d\n", Query (1, 1, n, val_a, val_b));
            }
       }
    }

return 0;
}

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

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 100000 +66;

int sum[maxn<<2];

int giveval;

void PushUp (int rt)

{

sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void Build (int rt, int l, int r)

{

if (l == r)

{

scanf ("%d", &sum[rt]);

return;

}

int m = (l + r) >> 1;

Build (lson);

Build (rson);

PushUp (rt);

}

void UpDate (int rt, int l, int r, int val, int num)

{

if (l == r)

{

sum[rt] += num;

return ;

}

int m = (l + r) >> 1;

if (val <= m)

UpDate (lson, val, num);

else

UpDate (rson, val, num);

PushUp (rt);

}

void Give (int rt, int l, int r, int val)

{

if (l == r)

{

giveval = sum[rt];

sum[rt] = 0;

return ;

}

int m = (l + r) >> 1;

if (val <= m)

Give (lson, val);

else

Give (rson, val);

PushUp (rt);

}

int Query (int rt, int l, int r, int L, int R)

{

if (L <= l && r <= R)

return sum[rt];

int m = (l + r) >> 1;

int ans = 0;

if (L <= m)

ans += Query (lson, L, R);

if (R > m)

ans += Query (rson, L, R);

return ans;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag =1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

int n, q;

scanf ("%d%d", &n, &q);

Build (1, 1, n);

int i, oper, val_a, val_b;

for (i = 0; i < q; i++)

{

scanf ("%d", &oper);

if (oper == 1)

{

scanf ("%d", &val_a);

val_a++;

Give (1, 1, n, val_a);

printf ("%d\n", giveval);

}

else if (oper == 2)

{

scanf ("%d%d", &val_a, &val_b);

val_a++;

UpDate (1, 1, n, val_a, val_b);

}

else if (oper == 3)

{

scanf ("%d%d", &val_a, &val_b);

val_a++, val_b++;

printf ("%d\n", Query (1, 1, n, val_a, val_b));

}

return 0;

}

lightoj1088

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

27 8月 2015

1088 - Points in Segments

For example if the points are 1, 4, 6, 8, 10. And the segment is 0 to 5. Then there are 2 points that lie in the segment.Given n points (1 dimensional) and q segments, you have to find the number of points that lie in each of the segments. A point p_i will lie in a segment A B if A ≤ p_i ≤ B.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 10⁵) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers denoting the points in ascending order. All the integers are distinct and each of them range in [0, 10⁸].

Each of the next q lines contains two integers A_k B_k (0 ≤ A_k ≤ B_k ≤ 10⁸) denoting a segment.

Output

For each case, print the case number in a single line. Then for each segment, print the number of points that lie in that segment.

Sample Input

Output for Sample Input

15 31 4 6 8 100 5

6 10

7 100000

Case 1:232

Note

Dataset is huge, use faster I/O methods.

题目类型：二分法

算法分析：读入数据，然后二分求得所求区间的上下界在输入序列中的下标pos_low和pos_high，最后直接pos_high – pos_low即可

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 100000 + 66;

int ans[maxn];

int n, q;

int Calc_low (int val)
{
    int low = 0, high = n - 1, mid;

    while (low <= high)
    {
        mid = low + (high - low) / 2;
        if (val <= ans[mid])
            high = mid - 1;

        else
            low = mid + 1;
    }

return low;
}

int Calc_high (int val)
{
    int low = 0, high = n - 1, mid;

    while (low <= high)
    {
        mid = low + (high - low) / 2;
        if (val >= ans[mid])
            low = mid + 1;

        else
            high = mid - 1;
    }

return low;
}

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;

    scanf ("%d", &t);

    while (t--)
    {


        scanf ("%d%d", &n, &q);

        int i;
        for (i = 0; i < n; i++)
            scanf ("%d", &ans[i]);

        printf ("Case %d:\n", flag++);

        int val_low, val_high;
        for (i = 0; i < q; i++)
        {
            scanf ("%d%d", &val_low, &val_high);

            int pos_low = Calc_low (val_low);
            int pos_high = Calc_high (val_high);

            printf ("%d\n", pos_high - pos_low);
        }
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 100000 + 66;

int ans[maxn];

int n, q;

int Calc_low (int val)

{

int low = 0, high = n - 1, mid;

while (low <= high)

{

mid = low + (high - low) / 2;

if (val <= ans[mid])

high = mid - 1;

else

low = mid + 1;

}

return low;

}

int Calc_high (int val)

{

int low = 0, high = n - 1, mid;

while (low <= high)

{

mid = low + (high - low) / 2;

if (val >= ans[mid])

low = mid + 1;

else

high = mid - 1;

}

return low;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

scanf ("%d%d", &n, &q);

int i;

for (i = 0; i < n; i++)

scanf ("%d", &ans[i]);

printf ("Case %d:\n", flag++);

int val_low, val_high;

for (i = 0; i < q; i++)

{

scanf ("%d%d", &val_low, &val_high);

int pos_low = Calc_low (val_low);

int pos_high = Calc_high (val_high);

printf ("%d\n", pos_high - pos_low);

}

return 0;

}

lightoj1083

maksyuki 发表于 oj 分类，标签: 数据结构-队列\双端\单调\优先

27 8月 2015

1083 - Histogram

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3 measured in units where the width of the rectangles is 1.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case contains a line with an integer N (1 ≤ N ≤ 30000) denoting the number of rectangles. The next line contains N space separated positive integers (≤ 30000) denoting the heights.

Output

For each case, print the case number and the largest rectangle that can be made.

Sample Input	Output for Sample Input
272 1 4 5 1 3 354 4 3 2 4	Case 1: 8Case 2: 10

Note

Dataset is huge; use faster I/O methods.

题目类型：单调队列

算法分析：一道经典的使用单调队列思想解的题。坐标从小到大分析，如果存在一个高度不超过先前的高度，则应该将先前高度的矩形块的面积出栈并计算，更新最大值。否则就一直入栈。最后将还在栈中的矩形块的面积计算出来并更新最大值

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 1100 + 66;

struct Node
{
    int w, h;
    Node (int ww, int hh) : w (ww), h (hh) {}
    Node () {}
};


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        int n;
        scanf ("%d", &n);

        deque <Node> deq;

        int hei, maxval = -INF, temp_w;

        for (int i = 0; i < n; i++)
        {
            scanf ("%d", &hei);

            temp_w = 0;
            Node val;
            while (!deq.empty () && deq.back ().h >= hei)
            {
                val = deq.back ();
                deq.pop_back ();
                maxval = max (maxval, val.h * (val.w + temp_w));
                temp_w += val.w;
            }

                deq.push_back (Node (temp_w + 1, hei));
        }

        temp_w = 0;
        while (!deq.empty ())
        {
            Node val = deq.back ();
            deq.pop_back ();
            maxval = max (maxval, val.h * (temp_w + val.w));
            temp_w += val.w;
        }

        printf ("%d\n", maxval);
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1100 + 66;

struct Node

{

int w, h;

Node (int ww, int hh) : w (ww), h (hh) {}

Node () {}

};

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int n;

scanf ("%d", &n);

deque <Node> deq;

int hei, maxval = -INF, temp_w;

for (int i = 0; i < n; i++)

{

scanf ("%d", &hei);

temp_w = 0;

Node val;

while (!deq.empty () && deq.back ().h >= hei)

{

val = deq.back ();

deq.pop_back ();

maxval = max (maxval, val.h * (val.w + temp_w));

temp_w += val.w;

}

deq.push_back (Node (temp_w + 1, hei));

}

temp_w = 0;

while (!deq.empty ())

{

Node val = deq.back ();

deq.pop_back ();

maxval = max (maxval, val.h * (temp_w + val.w));

temp_w += val.w;

}

printf ("%d\n", maxval);

}

return 0;

}

lightoj1080

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

27 8月 2015

1080 - Binary Simulation

'I i j' which means invert the bit from i to j (inclusive)Given a binary number, we are about to do some operations on the number. Two types of operations can be here.

'Q i' answer whether the i^th bit is 0 or 1

The MSB (most significant bit) is the first bit (i.e. i=1). The binary number can contain leading zeroes.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing a binary integer having length n (1 ≤ n ≤ 10⁵). The next line will contain an integer q (1 ≤ q ≤ 50000) denoting the number of queries. Each query will be either in the form 'I i j' where i, j are integers and 1 ≤ i ≤ j ≤ n. Or the query will be in the form 'Q i' where i is an integer and 1 ≤ i ≤ n.

Output

For each case, print the case number in a single line. Then for each query 'Q i' you have to print 1 or 0 depending on the i^th bit.

Sample Input

Output for Sample Input

200110011006I 1 10

I 2 7

Q 2

Q 1

Q 7

Q 5

1011110111

I 1 10

I 2 7

Q 2

Q 1

Q 7

Q 5

Case 1:011

Case 2:

Note

Dataset is huge, use faster i/o methods.

题目类型：线段树

算法分析：需要使用lazy标记来进行区间修改，lazy布尔数组当为false时表示当前区间没有翻转，而true表示当前区间元素需要翻转。由于本题要进行单点查询，所以可以在查询到叶子节点后再判断lazy，且不需要PushUp

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100000 + 66;

bool lazy[maxn<<2];
char sum[maxn];

void PushDown (int rt)
{
    if (lazy[rt])
    {
        lazy[rt<<1] = !lazy[rt<<1];
        lazy[rt<<1|1] = !lazy[rt<<1|1];
        lazy[rt] = !lazy[rt];
    }
}


void UpDate (int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
    {
        lazy[rt] = !lazy[rt];
        return ;
    }

    int m = (l + r) >> 1;
    PushDown (rt);

    if (L <= m)
        UpDate (lson, L, R);

    if (R > m)
        UpDate (rson, L, R);

}

int Query (int rt, int l, int r, int val)
{
   if (l == r)
   {
       if (lazy[rt])
       {
           sum[val] = !(sum[val] - '0') + '0';
           lazy[rt] = !lazy[rt];
       }

       return sum[val] - '0';
   }

    int m = (l + r) >> 1;
    PushDown (rt);

   if (val <= m)
        return Query (lson, val);

   else
        return Query (rson, val);
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:\n", flag++);

        memset (lazy, false, sizeof (lazy));
        scanf ("%s", sum + 1);

        int q, len = strlen (sum + 1);

        scanf ("%d", &q);

        int i;
        char cmd[6];
        for (i = 0; i < q; i++)
        {
            scanf ("%s", cmd);
            if (cmd[0] == 'I')
            {
                int val_a, val_b;
                scanf ("%d%d", &val_a, &val_b);
                UpDate (1, 1, len, val_a, val_b);
            }

            else
            {
                int val;
                scanf ("%d", &val);
                printf ("%d\n", Query (1, 1, len, val));
            }
        }
    }

return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100000 + 66;

bool lazy[maxn<<2];

char sum[maxn];

void PushDown (int rt)

{

if (lazy[rt])

{

lazy[rt<<1] = !lazy[rt<<1];

lazy[rt<<1|1] = !lazy[rt<<1|1];

lazy[rt] = !lazy[rt];

}

void UpDate (int rt, int l, int r, int L, int R)

{

if (L <= l && r <= R)

{

lazy[rt] = !lazy[rt];

return ;

}

int m = (l + r) >> 1;

PushDown (rt);

if (L <= m)

UpDate (lson, L, R);

if (R > m)

UpDate (rson, L, R);

}

int Query (int rt, int l, int r, int val)

{

if (l == r)

{

if (lazy[rt])

{

sum[val] = !(sum[val] - '0') + '0';

lazy[rt] = !lazy[rt];

}

return sum[val] - '0';

}

int m = (l + r) >> 1;

PushDown (rt);

if (val <= m)

return Query (lson, val);

else

return Query (rson, val);

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

memset (lazy, false, sizeof (lazy));

scanf ("%s", sum + 1);

int q, len = strlen (sum + 1);

scanf ("%d", &q);

int i;

char cmd[6];

for (i = 0; i < q; i++)

{

scanf ("%s", cmd);

if (cmd[0] == 'I')

{

int val_a, val_b;

scanf ("%d%d", &val_a, &val_b);

UpDate (1, 1, len, val_a, val_b);

}

else

{

int val;

scanf ("%d", &val);

printf ("%d\n", Query (1, 1, len, val));

}

return 0;

}

lightoj1078

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1078 - Integer Divisibility

For example you have to find a multiple of 3 which contains only 1's. Then the result is 3 because is 111 (3-digit) divisible by 3. Similarly if you are finding some multiple of 7 which contains only 3's then, the result is 6, because 333333 is divisible by 7.If an integer is not divisible by 2 or 5, some multiple of that number in decimal notation is a sequence of only a digit. Now you are given the number and the only allowable digit, you should report the number of digits of such multiple.

Input

Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case will contain two integers n (0 < n ≤ 10⁶ and n will not be divisible by 2 or 5) and the allowable digit (1 ≤ digit ≤ 9).

Output

For each case, print the case number and the number of digits of such multiple. If several solutions are there; report the minimum one.

Sample Input	Output for Sample Input
33 17 39901 1	Case 1: 3Case 2: 6Case 3: 12

题目类型：简单数学

算法分析：直接迭代计算temp = (10 * temp + k) % n直到temp == 0为止，输出迭代的次数即可，因为666 = 66 * 10 + 6，则有666 % n = (66 % n * 10 + 6 % n) % n

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 100000 + 66;

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        int n, k;
        cin >> n >> k;

        int sum = 1;
        long long temp = k % n;

        while (temp)
        {
            temp = (10 * temp + k) % n;
            sum++;
        }

        cout << sum << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 100000 + 66;

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

int n, k;

cin >> n >> k;

int sum = 1;

long long temp = k % n;

while (temp)

{

temp = (10 * temp + k) % n;

sum++;

}

cout << sum << endl;

}

return 0;

}

lightoj1074

maksyuki 发表于 oj 分类，标签: 图论-最短路

27 8月 2015

1074 - Extended Traffic

InputDhaka city is getting crowded and noisy day by day. Certain roads always remain blocked in congestion. In order to convince people avoid shortest routes, and hence the crowded roads, to reach destination, the city authority has made a new plan. Each junction of the city is marked with a positive integer (≤ 20) denoting the busyness of the junction. Whenever someone goes from one junction (the source junction) to another (the destination junction), the city authority gets the amount (busyness of destination - busyness of source)³ (that means the cube of the difference) from the traveler. The authority has appointed you to find out the minimum total amount that can be earned when someone intelligent goes from a certain junction (the zero point) to several others.

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case contains a blank line and an integer n (1 < n ≤ 200) denoting the number of junctions. The next line contains n integers denoting the busyness of the junctions from 1 to nrespectively. The next line contains an integer m, the number of roads in the city. Each of the next m lines (one for each road) contains two junction-numbers (source, destination) that the corresponding road connects (all roads are unidirectional). The next line contains the integer q, the number of queries. The next q lines each contain a destination junction-number. There can be at most one direct road from a junction to another junction.

Output

For each case, print the case number in a single line. Then print q lines, one for each query, each containing the minimum total earning when one travels from junction 1 (the zero point) to the given junction. However, for the queries that gives total earning less than 3, or if the destination is not reachable from the zero point, then print a '?'.

Sample Input

Output for Sample Input

256 7 8 9 106

1 2

2 3

3 4

1 5

5 4

4 5

10 10

1 2

Case 1:34Case 2:?

题目类型：单源最短路径(SPFA)

算法分析：SPFA算法的直接应用，注意判断输出’?’的条件是不可达、最短路径长度小于3或者是不存在负权值回路，注意一定要判断是否存在负权值回路，否则程序会TLE！！！！！！

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int INF = 0x7FFFFFFF;
const int maxn = 366 + 66;

int dis[maxn], ans[maxn], cnt[maxn];
bool inq[maxn];
int n;

struct Node
{
    int v, w;
    Node (int vv, int ww) : v (vv), w (ww) {}
    Node () {}
};

vector <Node> edge[maxn];

inline int power (int val)
{
    return val * val * val;
}

void spfa ()
{
    memset (inq, false, sizeof (inq));
    memset (cnt, 0, sizeof (cnt));

    int i;
    for (i = 1; i <= n; i++)
        dis[i] = INF;

    dis[1] = 0;
    queue <int> qu;

    qu.push (1);
    inq[1] = true;
    cnt[1]++;

    while (!qu.empty ())
    {
        int temp = qu.front ();
        qu.pop ();
        inq[temp] = false;

        if (cnt[temp] >= n)
            break;

        for (i = 0; i < edge[temp].size (); i++)
        {
            if (dis[temp] + edge[temp][i].w < dis[edge[temp][i].v])
            {
                dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w;
                if (!inq[edge[temp][i].v])
                {
                    inq[edge[temp][i].v] = true;
                    qu.push (edge[temp][i].v);
                    cnt[edge[temp][i].v]++;
                }
            }
        }
    }
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {

        scanf ("%d", &n);
        int i;
        for (i = 1; i <= n; i++)
            scanf ("%d", &ans[i]);

        int m, val_a, val_b;
        for (i = 1; i <= n; i++)
        {
            edge[i].clear ();
        }


        cin >> m;
        for (i = 0; i < m; i++)
        {
            scanf ("%d%d", &val_a, &val_b);
            edge[val_a].push_back (Node (val_b, power (ans[val_b] - ans[val_a])));
        }

        spfa ();

        printf ("Case %d:\n", flag++);

        int q, temp;
        scanf ("%d", &q);
        for (i = 0; i < q; i++)
        {
            scanf ("%d", &temp);
            if (dis[temp] < 3 || dis[temp] == INF || cnt[temp] >= n)
                printf ("?\n");

            else
                printf ("%d\n", dis[temp]);
        }
    }

return 0;
}

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

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 366 + 66;

int dis[maxn], ans[maxn], cnt[maxn];

bool inq[maxn];

int n;

struct Node

{

int v, w;

Node (int vv, int ww) : v (vv), w (ww) {}

Node () {}

};

vector <Node> edge[maxn];

inline int power (int val)

{

return val * val * val;

}

void spfa ()

{

memset (inq, false, sizeof (inq));

memset (cnt, 0, sizeof (cnt));

int i;

for (i = 1; i <= n; i++)

dis[i] = INF;

dis[1] = 0;

queue <int> qu;

qu.push (1);

inq[1] = true;

cnt[1]++;

while (!qu.empty ())

{

int temp = qu.front ();

qu.pop ();

inq[temp] = false;

if (cnt[temp] >= n)

break;

for (i = 0; i < edge[temp].size (); i++)

{

if (dis[temp] + edge[temp][i].w < dis[edge[temp][i].v])

{

dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w;

if (!inq[edge[temp][i].v])

{

inq[edge[temp][i].v] = true;

qu.push (edge[temp][i].v);

cnt[edge[temp][i].v]++;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

scanf ("%d", &n);

int i;

for (i = 1; i <= n; i++)

scanf ("%d", &ans[i]);

int m, val_a, val_b;

for (i = 1; i <= n; i++)

{

edge[i].clear ();

}

cin >> m;

for (i = 0; i < m; i++)

{

scanf ("%d%d", &val_a, &val_b);

edge[val_a].push_back (Node (val_b, power (ans[val_b] - ans[val_a])));

}

spfa ();

printf ("Case %d:\n", flag++);

int q, temp;

scanf ("%d", &q);

for (i = 0; i < q; i++)

{

scanf ("%d", &temp);

if (dis[temp] < 3 || dis[temp] == INF || cnt[temp] >= n)

printf ("?\n");

else

printf ("%d\n", dis[temp]);

}

return 0;

}

lightoj1070

maksyuki 发表于 oj 分类，标签: 数值-矩阵快速幂取模

27 8月 2015

1070 - Algebraic Problem

InputGiven the value of a+b and ab you will have to find the value of aⁿ+bⁿ. a and b not necessarily have to be real numbers.

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be no such input so that you have to find the value of 0⁰.

Output

For each test case, print the case number and (aⁿ+bⁿ) modulo 2⁶⁴.

Sample Input	Output for Sample Input
210 16 27 12 3	Case 1: 68Case 2: 91

题目类型：递推+矩阵快速幂取模

算法分析：首先推出递推公式：Sn = p*Sn-1 - q * Sn-2，然后使用矩阵快速幂取模求解。注意要使用unsigned long long 来定义变量，输入、输出！！！！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const unsigned long long MOD = 18446744073709551615uLL;
//18446744073709551615
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 2;

unsigned long long n = 2;//表示方阵的尺寸，必须恰好为运算的大小

//申请变量
struct Mat
{
    unsigned long long mat[maxn][maxn];
};


//重载Mat乘法运算
Mat operator * (Mat a, Mat b)
{
    Mat c;
    memset (c.mat, 0, sizeof (c.mat));
    for (unsigned long long k = 0; k < n; k++)
    {
        for (unsigned long long i = 0; i < n; i++)
        {
            if (a.mat[i][k] == 0) continue;

            for (unsigned long long j = 0; j < n; j++)
            {
                if (b.mat[k][j] == 0) continue;

                //c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD;
                c.mat[i][j] = (c.mat[i][j] + (a.mat[i][k] * b.mat[k][j]) % MOD) % MOD;
            }
        }
    }
return c;
}

//重载Mat乘幂运算
Mat operator ^ (Mat a, unsigned long long k)
{
    Mat c;
    for (unsigned long long i = 0; i < n; i++)
        for(unsigned long long j = 0; j < n; j++)
        c.mat[i][j] = (i == j);

    while (k)
    {
        if(k & 1)
            c = c * a;

        a = a * a;
        k >>= 1;
    }

return c;
}


int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

	Mat aa;
	int t, flag =1;
	scanf ("%d", &t);

	while (t--)
	{
		unsigned long long p, q, n;
		scanf ("%llu%llu%llu", &p, &q, &n);
        printf ("Case %d: ", flag++);

		if (n == 0)
			puts ("2");

		else if (n == 1)
            printf ("%llu\n", p % MOD);
            //cout << p % MOD << endl;

		else if (n == 2)
			printf ("%llu\n", (p * p - 2 * q) % MOD);
			//cout << (p * p - 2 * q) % MOD << endl;

		else
		{
			aa.mat[0][0] = p, aa.mat[0][1] = -q;
			aa.mat[1][0] = 1, aa.mat[1][1] = 0;
			Mat bb = aa ^ (n - 2), cc;

//			cout << aa.mat[0][0] << " " << aa.mat[0][1] << endl;

//			cout << aa.mat[1][0] << " " << aa.mat[1][1] << endl;

			cc.mat[0][0] = (p * p - 2 * q) % MOD;
			cc.mat[1][0] = p % MOD;

            bb = bb * cc;
            //printf ("%ulld\n", (bb.mat[0][0] + MOD) % MOD);

            if (bb.mat[0][0] > 0)
                printf ("%llu\n", bb.mat[0][0] % MOD);
                //cout << bb.mat[0][0] % MOD << endl;

			else
				printf ("%llu\n", (bb.mat[0][0] + MOD) %MOD);
				//cout << (bb.mat[0][0] + MOD) % MOD + 1<< endl;
		}
	}
return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const unsigned long long MOD = 18446744073709551615uLL;

//18446744073709551615

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 2;

unsigned long long n = 2;//表示方阵的尺寸，必须恰好为运算的大小

//申请变量

struct Mat

{

unsigned long long mat[maxn][maxn];

};

//重载Mat乘法运算

Mat operator * (Mat a, Mat b)

{

Mat c;

memset (c.mat, 0, sizeof (c.mat));

for (unsigned long long k = 0; k < n; k++)

{

for (unsigned long long i = 0; i < n; i++)

{

if (a.mat[i][k] == 0) continue;

for (unsigned long long j = 0; j < n; j++)

{

if (b.mat[k][j] == 0) continue;

//c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD;

c.mat[i][j] = (c.mat[i][j] + (a.mat[i][k] * b.mat[k][j]) % MOD) % MOD;

}

return c;

}

//重载Mat乘幂运算

Mat operator ^ (Mat a, unsigned long long k)

{

Mat c;

for (unsigned long long i = 0; i < n; i++)

for(unsigned long long j = 0; j < n; j++)

c.mat[i][j] = (i == j);

while (k)

{

if(k & 1)

c = c * a;

a = a * a;

k >>= 1;

}

return c;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

Mat aa;

int t, flag =1;

scanf ("%d", &t);

while (t--)

{

unsigned long long p, q, n;

scanf ("%llu%llu%llu", &p, &q, &n);

printf ("Case %d: ", flag++);

if (n == 0)

puts ("2");

else if (n == 1)

printf ("%llu\n", p % MOD);

//cout << p % MOD << endl;

else if (n == 2)

printf ("%llu\n", (p * p - 2 * q) % MOD);

//cout << (p * p - 2 * q) % MOD << endl;

else

{

aa.mat[0][0] = p, aa.mat[0][1] = -q;

aa.mat[1][0] = 1, aa.mat[1][1] = 0;

Mat bb = aa ^ (n - 2), cc;

// cout << aa.mat[0][0] << " " << aa.mat[0][1] << endl;

// cout << aa.mat[1][0] << " " << aa.mat[1][1] << endl;

cc.mat[0][0] = (p * p - 2 * q) % MOD;

cc.mat[1][0] = p % MOD;

bb = bb * cc;

//printf ("%ulld\n", (bb.mat[0][0] + MOD) % MOD);

if (bb.mat[0][0] > 0)

printf ("%llu\n", bb.mat[0][0] % MOD);

//cout << bb.mat[0][0] % MOD << endl;

else

printf ("%llu\n", (bb.mat[0][0] + MOD) %MOD);

//cout << (bb.mat[0][0] + MOD) % MOD + 1<< endl;

}

return 0;

}

lightoj1067

maksyuki 发表于 oj 分类，标签: 组合数学-组合数取模(Lucas)

27 8月 2015

1067 - Combinations

For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.Given n different objects, you want to take k of them. How many ways to can do it?

Input

Input starts with an integer T (≤ 2000), denoting the number of test cases.

Each test case contains two integers n (1 ≤ n ≤ 10⁶), k (0 ≤ k ≤ n).

Output

For each case, output the case number and the desired value. Since the result can be very large, you have to print the result modulo 1000003.

Sample Input	Output for Sample Input
34 25 06 4	Case 1: 6Case 2: 1Case 3: 15

题目类型：组合数取模(Lucas)

算法分析：由于模值p不算太大且为质数，则可以使用Lucas定理求解

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1000000 + 3;

const int maxn = 1000000 + 66;

long long mult_mod (long long a,long long b,long long mod)
{
    a %= mod;
    b %= mod;
    long long ans = 0;
    long long temp = a;

    while (b)
    {
        if (b & 1)
        {
            ans += temp;
            if (ans > mod)
                ans -= mod;
        }

        temp <<= 1;
        if (temp > mod)
            temp -= mod;
        b >>= 1;
    }

return ans;
}

long long pow_mod (long long a,long long n,long long mod)
{
    long long ans = 1;
    long long temp = a % mod;
    while (n)
    {
        if (n & 1)
            ans = mult_mod (ans, temp, mod);

        temp = mult_mod (temp, temp, mod);
        n >>= 1;
    }

return ans;
}

long long fac[maxn];//注意fac数组的大小一定要小于模值p

//在调用Lucas之前一定要先调用GetFactor函数
long long GetFactor (long long p)
{
    fac[0] = 1;
    for (long long i = 1; i <= p; i++)
        fac[i] = (fac[i-1] * i) % p;
}

long long Lucas (long long n, long long m, long long p)
{
    long long ret = 1;
    while (n && m)
    {
        long long a = n % p, b = m % p;
        if (a < b)
            return 0;

        ret = (ret * fac[a] * pow_mod (fac[b] * fac[a-b] % p, p - 2, p)) % p;
        n /= p;
        m /= p;
    }

return ret;
}

int main()
{
//    ifstream cin ("aaa.txt");
//    freopen ("aaa.txt", "r", stdin);

    GetFactor (MOD);

    long long flag = 1, t, n, k;
    scanf ("%lld", &t);

    while (t--)
    {
        scanf ("%lld%lld", &n, &k);
        printf ("Case %lld: %lld\n",  flag++, Lucas (n, k, MOD));
    }

return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1000000 + 3;

const int maxn = 1000000 + 66;

long long mult_mod (long long a,long long b,long long mod)

{

a %= mod;

b %= mod;

long long ans = 0;

long long temp = a;

while (b)

{

if (b & 1)

{

ans += temp;

if (ans > mod)

ans -= mod;

}

temp <<= 1;

if (temp > mod)

temp -= mod;

b >>= 1;

}

return ans;

}

long long pow_mod (long long a,long long n,long long mod)

{

long long ans = 1;

long long temp = a % mod;

while (n)

{

if (n & 1)

ans = mult_mod (ans, temp, mod);

temp = mult_mod (temp, temp, mod);

n >>= 1;

}

return ans;

}

long long fac[maxn];//注意fac数组的大小一定要小于模值p

//在调用Lucas之前一定要先调用GetFactor函数

long long GetFactor (long long p)

{

fac[0] = 1;

for (long long i = 1; i <= p; i++)

fac[i] = (fac[i-1] * i) % p;

}

long long Lucas (long long n, long long m, long long p)

{

long long ret = 1;

while (n && m)

{

long long a = n % p, b = m % p;

if (a < b)

return 0;

ret = (ret * fac[a] * pow_mod (fac[b] * fac[a-b] % p, p - 2, p)) % p;

n /= p;

m /= p;

}

return ret;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

GetFactor (MOD);

long long flag = 1, t, n, k;

scanf ("%lld", &t);

while (t--)

{

scanf ("%lld%lld", &n, &k);

printf ("Case %lld: %lld\n", flag++, Lucas (n, k, MOD));

}

return 0;

}

返回首页上一页 1 2 3 4 下一页最后一页

2015年8月
一	二	三	四	五	六	日
« 7月				9月 »
					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

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Note

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Notes

Input

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Output

Sample Input

Output for Sample Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论