fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cmath>
  5. #define ll long long int
  6. #define mod 1000000009
  7.  
  8. using namespace std;
  9.  
  10. ll pow1(ll a,ll b)
  11. {
  12.     ll z;
  13.     if(b==0)
  14.         return 1;
  15.     z=pow1(a,b/2)%mod;
  16.     z=(z*z)%mod;
  17.     if(b%2==1)
  18.         z=(z*a)%mod;
  19.     return z;
  20. }
  21.  
  22. ll abs1(ll x)
  23. {
  24.     if(x<0)
  25.         return -x;
  26.     return x;
  27. }
  28.  
  29. ll min1(ll a,ll b)
  30. {
  31.       return a<b?a:b;
  32. }
  33.  
  34. ll max1(ll a,ll b)
  35. {
  36.       return a<b?b:a;
  37. }
  38.  
  39. ll fact[100005],in_fact[100005];
  40.  
  41. ll factorial()
  42. {
  43.     ll i,j,k,l,m,n;
  44.     fact[0]=1;
  45.     in_fact[0]=1;
  46.     for(i=1;i<=100000;i++)
  47.     {
  48.         fact[i]=(i*fact[i-1])%mod;
  49.         in_fact[i]=pow1(fact[i],mod-2);
  50.     }
  51.  
  52. }
  53.  
  54.  
  55.  
  56. int main()
  57. {
  58.     factorial();
  59.     int t;
  60.     scanf("%d",&t);
  61.     while(t--)
  62.     {
  63.         ll i,j,k,m,n,temp,q,query;
  64.         scanf("%lld %lld",&n,&q);
  65.  
  66.         ll arr[100005]={0};
  67.         for(i=0;i<n;i++)
  68.         {
  69.             scanf("%lld",&arr[i]);
  70.         }
  71.         for(query=0;query<q;query++)
  72.         {
  73.             ll fr[105]={0},temp2;
  74.             scanf("%lld",&m);
  75.             for(i=0;i<n;i++)
  76.             {
  77.                 if(arr[i]<0)
  78.                 {
  79.                     temp=abs1(arr[i]);
  80.                     temp=temp/m;
  81.                     temp++;
  82.                     temp2=((temp)*m+arr[i])%m;
  83.                 }
  84.                 else
  85.                 {
  86.                     temp2=arr[i]%m;
  87.                 }
  88.                 fr[temp2]++;
  89.             }
  90.  
  91.             ll dp[105][105]={{0}};
  92.  
  93.             dp[0][0]=1;
  94.             dp[0][0]=1;
  95.             for(i=0;i<m;i++)
  96.             {
  97.                 temp=min(m,fr[i]);
  98.                 for(j=1;j<=temp;j++)
  99.                 {
  100.                     ll no;
  101.                     no=(j*i)%m;
  102.                     ll temp3=0,l;
  103.                     for(l=j;l<=fr[i];l=l+m)
  104.                         temp3=(temp3+ (((fact[fr[i]]*in_fact[l])%mod)*in_fact[fr[i]-l])%mod  )%mod;
  105.                     for(k=0;k<m;k++)
  106.                     {
  107.                         dp[i+1][k]=(dp[i+1][k]+(dp[i][(m+k-no)%m]*temp3)%mod)%mod;
  108.                     }
  109.                 }
  110.  
  111.  
  112.  
  113.                 for(k=0;k<m;k++)
  114.                     dp[i+1][k]=(dp[i+1][k]+dp[i][k])%mod;
  115.             }
  116.  
  117.  
  118.             printf("%lld\n",dp[m][0]);
  119.         }
  120.     }
  121.  
  122.  
  123.     return 0;
  124. }
  125.  
Time limit exceeded #stdin #stdout 15s 5032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jE7LlL
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

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!