fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define db double
  5. #define ll long long int
  6. #define ld long double
  7. #define li long int
  8. #define pb push_back
  9. #define mp make_pair
  10. #define FOR(i,a,b) for(i=a;i<b;i++)
  11. #define RFOR(i,a,b) for(i=a;i>b;i--)
  12. #define f first
  13. #define s second
  14. #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
  15. #define pl pair<ll,ll>
  16. #define pll pair<ll,pl>
  17. #define plll pair<ll,pll>
  18. #define all(a) a.begin(),a.end()
  19. #define nl cout<<endl
  20. #define inf LONG_LONG_MAX
  21. #define minf LONG_LONG_MIN
  22. #define pq priority_queue
  23. #define pi 3.1415926535897932
  24.  
  25. bool isPrime(ll n)
  26. {
  27.  
  28.         if (n <= 1)  return false;
  29.         if (n <= 3)  return true;
  30.  
  31.         if (n%2 == 0 || n%3 == 0) 
  32.             return false;
  33.  
  34.         for (ll i=5; i*i<=n; i=i+6)
  35.         {
  36.             if (n%i == 0 || n%(i+2) == 0)
  37.                return false;
  38.         }
  39.  
  40.         return true;
  41. }
  42. ll gcd(ll a,ll b)
  43. {
  44.     if(a==0)    return b;
  45.     if(a<b) swap(a,b);
  46.     return gcd(a%b,b);
  47. }
  48. ll gcdextended(ll a,ll b,ll &x,ll &y)
  49. {
  50.     if(a==0)
  51.     {
  52.         x=0;
  53.         y=1;
  54.         return b;
  55.     }
  56.     ll x1,y1,gcd=gcdextended(b%a,a,x1,y1);
  57.     x=y1-(b/a)*x1;
  58.     y=x1;
  59.     return gcd;
  60. }
  61. ll modinverse(ll a,ll m)
  62. {
  63.     ll x,y;
  64.     ll g=gcdextended(a,m,x,y);
  65.     if(g!=1)
  66.     {
  67.         cout<<"NOT POSSIBLE";
  68.         return -1;
  69.     }
  70.     else
  71.         return (x%m+m)%m;
  72. }
  73. ll po(ll x,ll y) 
  74. { 
  75.     ll res = 1;        
  76.     while (y > 0) 
  77.     { 
  78.         if (y & 1) 
  79.             res = (res*x); 
  80.         y = y>>1;
  81.         x = (x*x);   
  82.     } 
  83.     return res; 
  84. }
  85. ll pom(ll x,ll y,ll p)
  86. {
  87.     ll res=1;
  88.     x=x%p;
  89.     while(y>0)
  90.     {
  91.         if(y&1)
  92.             res=(res*x)%p;
  93.         y= y>>1;
  94.         x=(x*x)%p;
  95.     }
  96.     return res;
  97. }
  98. ll modinv(ll x,ll p)
  99. {
  100. 	ll y=pom(x,p-2,p);
  101. 	return y;
  102. }
  103. ll root(ll x,vector<ll> &id)
  104. {
  105.     while(id[x]!=x)
  106.     {
  107.         id[x]=id[id[x]];
  108.         x=id[x];
  109.     }
  110.     return x;
  111. }
  112. void uni(ll x,ll y,vector<ll> &id)
  113. {
  114.     ll a=root(x,id);
  115.     ll b=root(y,id);
  116.     id[a]=id[b];
  117. }
  118. ll mst(vector<pll> &e,vector<ll> &id)
  119. {
  120.     ll x,y,i,j;
  121.     ll mic=0,c;
  122.     FOR(i,0,e.size())
  123.     {
  124.         x=e[i].s.f;
  125.         y=e[i].s.s;
  126.         c=e[i].f;
  127.         if(root(x,id)!=root(y,id))
  128.         {
  129.             uni(x,y,id);
  130.             mic+=c;
  131.         }
  132.     }
  133.     return mic;
  134. }
  135. bool sec(const pl &a,const pl &b)  
  136. {
  137.     if(a.s==b.s)    return a.f>b.f;
  138.     return a.s>b.s;
  139. }
  140. ll ff(ll in,vector<ll> &a,ll n)
  141. {
  142. 	ll i,x=0,y=2*n-1;
  143. 	while(x<y)
  144. 	{
  145. 		if(x==in || x==in+1)	x++;
  146. 		if(y==in || y==in+1)	y--;
  147. 		if((x<in || x>in+1) && (y<in || y>in+1))
  148. 		{
  149. 			if(a[x]+a[y]==a[in])	x++,y--;
  150. 			else	return 0;
  151. 		}
  152. 	}
  153. 	return 1;
  154. }
  155. int main()
  156. {
  157.     //fast;
  158.     ll t;
  159.     scanf("%lld",&t);
  160.     while(t--)
  161.     {
  162.     	ll n,p=1e9+7,i,an,x,y;
  163.     	scanf("%lld",&n);
  164.     	vector<ll> fact(n+1),inv(n+1),a(2*n);
  165.     	fact[0]=1,fact[1]=1;
  166.     	FOR(i,2,n+1)	fact[i]=(fact[i-1]*i)%p;
  167.     	inv[n]=modinv(fact[n],p); 
  168.     	RFOR(i,n-1,-1)	inv[i]=(inv[i+1]*(i+1))%p;
  169.     	FOR(i,0,2*n)	scanf("%lld",&a[i]);
  170.     	sort(all(a));
  171.     	if(n==1)
  172.     	{
  173.     		if(a[0]==a[1])	printf("1\n");
  174.     		else	printf("0\n");
  175.     	}
  176.     	else
  177.     	{
  178. 	 		map<ll,ll> m;
  179. 	 		map<pl,ll> fr;
  180. 	 		map<pl,ll>::iterator it;
  181. 	    	FOR(i,0,2*n-1)
  182. 	    	{
  183. 	    		if(a[i]==a[i+1] && m.find(a[i])==m.end() && ff(i,a,n))
  184. 	    			break;
  185. 	    		if(a[i]==a[i+1]) 	m[a[i]]=1;
  186. 	    	}
  187. 	    	//cout<<i<<" ";
  188. 	    	if(i==2*n-1)	printf("0\n");
  189. 	    	else
  190. 	    	{
  191. 	    		an=fact[n-1];
  192. 		    	x=0,y=2*n-1;
  193. 		    	while(x<y)
  194. 		    	{
  195. 		    		if(x==i || x==i+1)	x++;
  196. 		    		if(y==i || y==i+1)	y--;
  197. 		    		if((x<i || x>i+1) && (y<i || y>i+1))
  198. 		    		{
  199. 		    			if(a[x]!=a[y])	an=(an*2)%p;
  200. 		    			fr[mp(a[x],a[y])]++;
  201. 		    			x++,y--;
  202. 		    		}	
  203. 		    	}
  204. 		    	for(it=fr.begin();it!=fr.end();it++)
  205. 		    	{
  206. 		    		x=it->s;
  207. 		    		an=(an*inv[x])%p;
  208. 		    	}
  209. 		    	printf("%lld\n",an);
  210. 		    }
  211. 		}
  212.     }
  213. }
  214.  
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
4
1
-1 1
1
0 0
2
4 1 1 4
3
5 3 7 10 5 10
stdout
copy 
0
1
0
4
https://ideone.com/pae3M8
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!