2015
04-14

# Random Function

Cover is an admin of HOJ, MUT is coming and he needs to generate passwords for every team of MUT. Thus he needs a pesudo-random number generator.

As we know, random numbers are usually gernerated by a random number table and a random seed. The random table is an large array. Using random seed to calculate a subscript, we can use the corresponding number in the talbe as a pesudo-random number.

But Cover is a geek and he won’t do this as others did. He uses a circle array of length N as random table and three numbers ( a, b, c) as random seed. The random nubmer is defined as the product of table[a], table[(a+b-1)%N+1], table[(a+2b-1)%N+1] … table[c] ( see Sample Input for more details). Of course this product P may be too large, so Cover use P % 1000000007 as the result.

Now it’s your task, given the table and a query( a, b, c), help Cover find out the pesudo-random number.

Multiple test cases, at most 20. Process to the end of the file.

The first line of input contains three numbers, N, Q, (1 ≤ N ≤ 50000, 1 ≤ Q ≤ 50000) descripting the length of the circle array, the number of queries, and M mentioned above. The second line contains N positive integers less than 10^9, denotes the (1..N)th numbers of the circle array. Then comes Q lines, each line contains three number, means a query of a, b, c ( 1 ≤ a, b, c ≤ N). It’s guaranteed that there’s an interger i makes c = a + b * i or c + N = a + b * i;

Multiple test cases, at most 20. Process to the end of the file.

The first line of input contains three numbers, N, Q, (1 ≤ N ≤ 50000, 1 ≤ Q ≤ 50000) descripting the length of the circle array, the number of queries, and M mentioned above. The second line contains N positive integers less than 10^9, denotes the (1..N)th numbers of the circle array. Then comes Q lines, each line contains three number, means a query of a, b, c ( 1 ≤ a, b, c ≤ N). It’s guaranteed that there’s an interger i makes c = a + b * i or c + N = a + b * i;

6 5
1 2 3 4 5 6
1 1 6
1 3 1
1 3 4
2 4 6
3 5 2

720
1
4
12
6

#include <iostream>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define clr(a, b) memset(a, b, sizeof(a))
#define SZ(a) ((int)a.size())
#define PB push_back
#define MP make_pair
#define inf 0x3f3f3f3f
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

#ifdef ecust
#define R "%lld"
#else
#define R "%I64d"
#endif

namespace acm {

#define maxn 100000
int in[maxn];
#define canshu 50
#define mod 1000000007
int mul[canshu + 1][maxn + 1];
int n, q;

void init() {
for (int i = 1; i < canshu; ++i) {
forn(j, n * 2)
if (j >= i)
mul[i][j] = (ll)mul[i][j - i] * in[j] % mod;
else
mul[i][j] = in[j];
}
}

ll pow(ll a, ll b){
if (b == 0)
return 1;
ll t = pow(a, b / 2);
t = t * t % mod;
if (b & 1)
return t * a % mod;
return t;
}

void solve() {
forn(i, n) {
scanf("%d", in + i);
in[n + i] = in[i];
}
init();
while (q--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a--;
c--;
if ((c - a) % b != 0){
c += n;
} else if (c < a) {
c += n;
}
if (b >= canshu) {
ll ans = 1;
for(int i = a; i <= c; i += b)
ans = ans * in[i] % mod;
printf(R"\n", ans);
}
else {
if (a < b)
printf("%d\n", mul[b][c]);
else {
ll ans = mul[b][c];
ans = ans * pow(mul[b][a - b], mod - 2) % mod;
printf(R"\n", ans);
}
}
}
}

void icpc() {
while (scanf("%d%d", &n, &q) != EOF){
solve();
}
}

}

int main() {
#ifdef ecust
freopen("in", "r", stdin);
#endif
acm::icpc();
return 0;
}

1. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}