Cerinta completa
Lukas is a Civil Engineer who loves designing road networks to connect cities numbered from to . He can build any number of bidirectional roads as long as the resultant network satisfies these constraints:
- It must be possible to reach any city from any other city by traveling along the network of roads.
- No two roads can directly connect the same two cities.
- A road cannot directly connect a city to itself.
In other words, the roads and cities must form a simple connected labeled graph.
You must answer queries, where each query consists of some denoting the number of cities Lukas wants to design a bidirectional network of roads for. For each query, find and print the number of ways he can build roads connecting cities on a new line; as the number of ways can be quite large, print it modulo .
Input Format
The first line contains an integer, , denoting the number of queries.
Each of the subsequent lines contains an integer denoting the value of for a query.
Constraints
Output Format
For each of the queries, print the number of ways Lukas can build a network of bidirectional roads connecting cities, modulo , on a new line.
Sample Input 0
3
1
3
10
Sample Output 0
1
4
201986643
Explanation 0
We answer the first two queries like this:
- When , the only option satisfying Lukas’ three constraints is to not build any roads at all. Thus, we print the result of on a new line.
-
When , there are four ways for Lukas to build roads that satisfy his three constraints:
Thus, we print the result of on a new line.
Limbajul de programare folosit: cpp14
Cod:
#include<stdio.h>
#define MAX_N 150000
#define MODULE 663224321
static long long f[MAX_N];
static long long g[MAX_N];
static long long factorial_inverse[MAX_N];
static long long factorial[MAX_N];
static long long x1[MAX_N];
static long long x2[MAX_N];
static long long y[MAX_N];
long long power(long long x, long long n)
{
long long res = 1;
for( ; n ; n >>= 1, x = x * x % MODULE )
{
if( n & 1 )
{
res = ( res * x ) % MODULE;
}
}
return res;
}
void Run(long long *x, long long n, long long rev)
{
for( long long i = 1, j, k, t ; i < n ; ++i )
{
for( j = 0, t = i, k = n >> 1 ; k ; t >>= 1, k >>= 1 )
{
j = j << 1 | t & 1;
}
if( i < j )
{
long long tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
}
for( long long s = 2, ds = 1 ; s <= n ; ds = s, s <<= 1 )
{
long long wn = power(3, (MODULE - 1) / s);
if( rev < 0 )
{
wn = power(wn, MODULE - 2);
}
for( long long k = 0 ; k < n ; k += s )
{
long long w = 1, t;
for( long long i = k ; i < k + ds ; ++ i, w = w * wn % MODULE )
{
x[i+ds] = ( x[i] - ( t = w * x[i+ds] % MODULE ) + MODULE ) % MODULE;
x[i] = ( x[i] + t ) % MODULE;
}
}
}
if( rev < 0 )
{
long long invn = power(n, MODULE - 2);
for( long long i = 0 ; i < n ; ++i )
{
x[i] = x[i] * invn % MODULE;
}
}
}
void divide_conquer(long long left, long long right)
{
if( left == right )
{
return;
}
long long mid = ( left + right ) / 2;
divide_conquer(left, mid);
long long n1;
for( n1 = 1 ; n1 <= right - left ; n1 <<= 1 );
for( long long i = 0 ; i < n1 ; ++i )
{
x1[i] = ( i + left <= mid ) ? f[i+left] * factorial_inverse[i+left-1] % MODULE : 0;
x2[i] = (i + left <= right) ? factorial_inverse[i+1] * g[i+1] % MODULE : 0;
}
Run(x1, n1, 1);
Run(x2, n1, 1);
for( long long i = 0 ; i < n1 ; ++i )
{
y[i] = x1[i] * x2[i] % MODULE;
}
Run(y, n1, -1);
for( long long i = mid + 1 ; i <= right ; ++i )
{
f[i] = ( f[i] - ( factorial[i-1] * y[i-left-1] % MODULE ) + MODULE ) % MODULE;
}
divide_conquer(mid + 1, right);
}
void initialize()
{
factorial[0] = 1;
factorial_inverse[0] = 1;
for( long long i = 1 ; i < MAX_N ; ++i )
{
factorial[i] = ( factorial[i-1] * i ) % MODULE;
factorial_inverse[i] = power(factorial[i], MODULE - 2);
g[i] = power(2, (long long)i * (long long)(i - 1) / 2);
f[i] = g[i];
}
divide_conquer(1, 100000);
}
int main()
{
int q, n;
initialize();
scanf("%d", &q);
for( long long i = 0 ; i < q ; ++i )
{
scanf("%d", &n);
printf("%lld\n", f[n]);
}
return 0;
}
Scor obtinut: 1.0
Submission ID: 464649069
Link challenge: https://www.hackerrank.com/challenges/counting-road-networks/problem