Advertisement
najim

1318 - Strange Game_WA

Nov 23rd, 2013
401
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //http://www.lightoj.com/volume_showproblem.php?problem=1318
  2. #include<algorithm>
  3. #include<stdio.h>
  4. #include<vector>
  5. using namespace std;
  6. typedef long long int LLI;
  7. typedef pair<int,int> PII;
  8. #define REP(i,n) for(int i=0;i<n;i++)
  9. #define PB push_back
  10. #define MP make_pair
  11. #define Mx 100003
  12. #define MxS 320
  13. vector<PII>V[Mx+9];
  14. int T[Mx+9];
  15. bool vis[Mx+9];
  16. void precal()
  17. {
  18.     int ct;
  19.     REP(i,Mx)T[i]=i;
  20.     for(int i=2;i<=MxS;i++)
  21.     {
  22.         if(!vis[i])
  23.         {
  24.             for(int j=i+i;j<=Mx;j+=i)
  25.             {
  26.                 ct=0;
  27.                 while(T[j]%i==0)
  28.                 {
  29.                     ct++;
  30.                     T[j]/=i;
  31.                 }
  32.                 V[j].PB(MP(i,ct));
  33.                 vis[j]=1;
  34.             }
  35.         }
  36.     }
  37.     for(int i=2;i<Mx;i++)
  38.     {
  39.         if(!vis[i])
  40.         {
  41.             V[i].PB(MP(i,1));
  42.         }
  43.         else if(T[i]!=1)
  44.         {
  45.             V[i].PB(MP(T[i],1));
  46.         }
  47.     }
  48. }
  49.  
  50. template<class T> inline T BIGMOD(T n, T m, T mod)
  51. {
  52.     if(m<0)return 1;
  53.     LLI ans = 1;
  54.     LLI k = n;
  55.     while(m){
  56.         if(m & 1) {
  57.             ans *= k;
  58.             if(ans>mod) ans %= mod;
  59.         }
  60.         k *= k;
  61.         if(k>mod) k %= mod;
  62.         m >>= 1;
  63.     }
  64.     return ans;
  65. }
  66.  
  67. long long nCr(LLI n,LLI r,LLI modv)
  68. {
  69.     if(r==0)return 1%modv;
  70.     REP(i,Mx)T[i]=0;
  71.     for(int i=max(r,n-r)+1;i<=n;i++)
  72.     {
  73.         for(int j=V[i].size()-1;j>=0;j--)
  74.         {
  75.             T[V[i][j].first]+=V[i][j].second;
  76.         }
  77.     }
  78.     for(int i=min(r,n-r);i>=2;i--)
  79.     {
  80.         for(int j=V[i].size()-1;j>=0;j--)
  81.         {
  82.             T[V[i][j].first]-=V[i][j].second;
  83.         }
  84.     }
  85.     LLI ret=1;
  86.     for(int i=2;i<Mx;i++)
  87.     {
  88.         if(T[i] && !vis[i])
  89.         {
  90.             ret=(ret * BIGMOD((LLI)i,(LLI)T[i],modv))%modv;
  91.         }
  92.     }
  93.     return ret;
  94. }
  95.  
  96.  
  97. int main()
  98. {
  99.     //read(inp);
  100.     //write(out);
  101.     precal();
  102.     int kase,ks=0;
  103.     scanf("%d",&kase);
  104.     while(kase--)
  105.     {
  106.          LLI N,K,L,M;
  107.          scanf("%lld %lld %lld %lld",&N,&K,&L,&M);
  108.          LLI fu=(K)*(K-1);
  109.          //cout << fu << "......." << endl;
  110.          //fu>>=1;
  111.          LLI gg=fu/2;//m
  112.          LLI res=nCr(L,L-M,N);
  113.          res = (res * BIGMOD(K,L-M,N))%N;
  114.          res = (res * BIGMOD(gg,M,N))%N;
  115.          res = (res * BIGMOD(2LL,M-1,N))%N;
  116.          //cout << nCr(L,L-M,N) << " -> " << power(K,L-M) << " " << (fu * M) << endl;
  117.          printf("Case %d: %lld\n",++ks,(res%N)+1LL);
  118.     }
  119.     return 0;
  120. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement