Count RelationsProblem code: COUNTREL |
All submissions for this problem are available.
Let A be a set of the first N positive integers :A={1,2,3,4.........N}
Let B be the set containing all the subsets of A.
Professor Eric is a mathematician who defined two kind of relations R1 and R2 on set B.
The relations are defined as follows:
R1={ (x,y) : x and y belong to B and x is not a subset of y and y is not a subset of x and the intersection of x and y is equal to empty set }
R2={ (x,y) : x and y belong to B and x is not a subset of y and y is not a subset of x and the intersection of x and y is not equal to empty set }
Now given the number N,Professor Eric wants to know how many relations of kind R1 and R2 exists.Help him.
NOTE : (x,y) is the same as (y,x) ,i.e the pairs are unordered.
Input format:
The first line contains the number of test cases T.Each of the test case is denoted by a single integer N.
Output format:
Output T lines, one for each test case,containing two integers denoting the number of relations of kind R1 and R2 respectively, modulo 100000007.
Example
Sample Input:
3
1
2
3
Sample Output:
0 0
1 0
6 3
Constraints:
1 <= T <= 1000
1 <= N <= 10^18
Explanation:
Let A={1,2}
Then B={Phi,{1},{2},{1,2}}
Phi=Empty Set
So R1=Either {({1},{2})} or {({2},{1})}
and R2=No relation exists
So,there is 1 relation of kind R1 and 0 relation of kind R2.
| Author: | nssprogrammer |
| Date Added: | 4-12-2010 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | C, C99 strict, CPP 4.0.0-8, CPP 4.3.2, CS2, D, JAVA, PAS fpc, PAS gpc |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
in the case where N =
in the case where N = 2...
number of relations according to me is 3 :
1. {({1},{2})}
2. {({2},{1})}
3. {({1},{2}), ({2},{1})}
@ swagat: Which are R1 and
@ swagat: Which are R1 and which are R2?
@swagat:Number of relations
@swagat:Number of relations of kind R2 will be 3.You have to produce number of relations for both R1 and R2.
@swagat ({x} ,{y}) and
@swagat
({x} ,{y}) and ({y},{x}) are same according to question
NOTE : (x,y) is the same as (y,x) ,i.e the pairs are unordered.
I get Wrong Answer all the
I get Wrong Answer all the time!
I guess I may misunderstand or misuse something about "modulo".
May you suggest me some good websites that introduce the usage of "modulo"?
@ Tim :
@ Tim : http://en.wikipedia.org/wiki/Modular_arithmetic
That means the output must
That means the output must larger than or equal to 0 and
less than 100000007 (100000007 is NOT acceptable). Am I right?
@ Tim: Yes.
@ Tim: Yes.
Thank you Ashar Fuadi! In
Thank you Ashar Fuadi! In fact, I got nothing wrong about modulo, but only forgot CodeChef judge only allow %lld but not %I64d in cpp.
can any1 plz give a good test
can any1 plz give a good test case...thnx in advance..
That would be against the
That would be against the rules.
Earlier my sol was AC in 0.00
Earlier my sol was AC in 0.00 0M but now it is removed and showing TLE..:(
The question should have
The question should have mentioned that B contains only non-empty subsets of A, otherwise the answers would have been quite different from the ones given to the sample test cases..
B can certainly be the empty
B can certainly be the empty set; that doesn't make the sample output wrong.
Then R1 will contain much
Then R1 will contain much more number of relations, because the intersection of a non-empty set and a null set is always null. But do you mean to say that an empty set is always a sub-set of any non-empty set? If so, then it's okay. Otherwise there will be many more cases, like {[1],[phi]}, {[1,2],[phi]}, etc.
@Kaustav: But in that case y
@Kaustav:
But in that case y will be a subset of x as {phi} is a subset of every set.
There are many possibilities
There are many possibilities for the sets x and y ..right?then how can we directly tell the (un)ordered pairs without mentioning what x and y are.Moreover the question is how many such relationals are possible rather than what are they.Am i wrong?Plz help me.
@sweety u dont need to know
@sweety
u dont need to know the sets rather u need to know the types of sets with which u can derive a simple formula
to find both types of relations
Why in third case (N=3), we
Why in third case (N=3), we have 6 R1? I see there only three: (1, {2,3}), (2, {1,3}), (3, {1,2}). What is extra three R1?
@max {{1},{2}},{{1},{3}},{{2}
@max
{{1},{2}},{{1},{3}},{{2},{3}} are also 3 cases