首页 > ACM题库 > HDU-杭电 > HDU 3965-Random Function[解题报告]HOJ
2015
04-14

HDU 3965-Random Function[解题报告]HOJ

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;
    }