Участник:Muradyan Armen/ADATOMAT

Материал из DISCOPAL
< Участник:Muradyan Armen
Версия от 14:16, 9 декабря 2020; Muradyan Armen (обсуждение | вклад) (Новая страница: «C++ (gcc 8.3) https://www.spoj.com/problems/ADATOMAT/ <code-cpp> #include <iostream> #include <string.h> using namespace std; void radixSort(int*, int); long l…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

C++ (gcc 8.3)

https://www.spoj.com/problems/ADATOMAT/

#include <iostream>
#include <string.h>
 
using namespace std;
void radixSort(int*, int);
long long mod = 1000000007;
 
void radixSort(int* a, int N){
    const int INT_BIT_SIZE = sizeof(int)<<3, RADIX = 0x100, MASK = RADIX-1, MASK_BIT_LENGTH = 8;
    int *result = new int[N](), *buckets = new int[RADIX](), *startIndex = new int[RADIX](), *temp = nullptr;
    int flag = 0, key = 0;
    bool hasNeg = false;
    while (flag < INT_BIT_SIZE){
        for (int i = 0; i < N; ++i) {
            key = (a[i] & (MASK << flag)) >> flag;
            if(key < 0){
                key += MASK;
                hasNeg = true;
            }
            ++buckets[key];
        }
        startIndex[0] = 0;
        for (int j = 1; j < RADIX; ++j) startIndex[j] = startIndex[j - 1] + buckets[j - 1];
        for (int i = N-1; i >= 0; --i){
            key = (a[i] & (MASK << flag)) >> flag;
            if(key < 0) key += MASK;
            result[startIndex[key] + --buckets[key]] = a[i];
        }
        memcpy(a,result,N*sizeof(int));
        flag += MASK_BIT_LENGTH;
    }
    if(hasNeg){
        int indexOfNeg = 0;
        for (int i = 0; i < N; i++) {
            if(a[i] < 0) {
                indexOfNeg = i;
                break;
            }
        }
        memcpy(a,result+indexOfNeg,(N-indexOfNeg)*sizeof(int));
        memcpy(a+(N-indexOfNeg),result,indexOfNeg*sizeof(int));
    }
    delete[] result;
    delete[] buckets;
    delete[] startIndex;
}
 
int main(){
 
	int T,x1,aa,b,n;
	cin >> T;
	while(T--){
		cin >> n >> aa >> b >> x1;
		int a[n+1];
		unsigned long long sum = 0;
		a[0]=x1;
		for(int i=1;i<n;i++){
			unsigned long long  aux = 1;
			aux = (a[i-1] * aux * aa + b)%mod;
			a[i] = (int)aux;
		}
		radixSort(a,n);
		for(int i=0;i<n;i++){
			unsigned long long  aux = 1;
			aux = aux * a[i] * (i + 1)%mod;
			sum += aux;
			sum>=mod?sum-=mod:sum;
		}
		cout << sum <<endl;
	}
}