0
Your rating: None

CodeChef submission 738300 (C++ 4.3.2)

CodeChef submission 738300 (C++ 4.3.2) plaintext list. Status: WA, problem COLCHAIN, contest . By kostroma (kostroma), 2011-11-23 16:49:00.
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6. #include <set>
  7. #include <memory.h>
  8. using namespace std;
  9.  
  10. #define pb push_back
  11. #define mp make_pair
  12. typedef pair <int, int> pi;
  13. typedef long long li;
  14. void solve();
  15. int main ()
  16. {
  17. #ifndef ONLINE_JUDGE
  18. freopen ("in.txt", "r", stdin);
  19. #endif
  20. int t=1; cin>>t;
  21. while (t--)
  22. solve();
  23. return 0;
  24. }
  25. #define int li
  26. int n, m;
  27. int mod=1000000007;
  28. int dp[100500][2];
  29. void solve()
  30. {
  31.      memset (dp, 0, sizeof dp);
  32.      cin>>n>>m;
  33.      int fact=1;
  34.      for (int i=1; i<=m; i++)
  35.           fact=(fact*i)%mod;
  36.      dp[m+1][0]=(fact*( (m*(m-1)/2) %mod ))%mod;
  37.      dp[m+1][1]=(fact*m)%mod;
  38.      for (int i=m+1; i<n; i++)
  39.      {
  40.           dp[i+1][true]=dp[i][true]+2*dp[i][false]/m; dp[i+1][true]%=mod;
  41.           dp[i+1][false]=(m-1)*dp[i][true]+(m-2)*dp[i][false]/m; dp[i+1][false]%=mod;
  42.      }
  43.      cout<<(dp[n][true]+dp[n][false])%mod<<endl;
  44. }
  45.

Comments