0
Your rating: None

CodeChef submission 757698 (C++ 4.3.2)

CodeChef submission 757698 (C++ 4.3.2) plaintext list. Status: WA, problem COLCHAIN, contest . By kamranmaharov (kamranmaharov), 2011-12-15 19:25:16.
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <fstream>
  11. #include <set>
  12. #include <map>
  13. #include <cmath>
  14. #pragma comment(linker,"/STACK:16777216")
  15. #define inf 1000000000
  16. #define MP make_pair
  17. using namespace std;
  18. typedef long long i64;
  19. typedef unsigned long long u64;
  20. const i64 mod=1000000007;
  21. i64 f[100100],sum[100100];
  22. i64 fact[100100];
  23. i64 res;
  24.  
  25. int main()
  26. {
  27.     int t,n,m;
  28.  
  29.     fact[0]=1;
  30.     for(int i=1;i<=100050;i++)fact[i]=(fact[i-1]*i)%mod;
  31.  
  32.     cin>>t;
  33.     while(t--){
  34.         cin>>n>>m;
  35.  
  36.         for(int i=2;i<=m+1;i++){f[i]=1;sum[i]=sum[i-1]+f[i];}
  37.  
  38.         for(int i=m+2;i<=n;i++){//sum up f[i-m],f[i-m+1]...f[i-1]
  39.             f[i]=(sum[i-1]+mod-sum[i-m-1])%mod;
  40.             sum[i]=(sum[i-1]+f[i])%mod;
  41.         }
  42.  
  43.         res=0;
  44.         for(int i=n-m+1;i<=n;i++)res=(res+f[i]*(i-(n-m))%mod);
  45.         res=res*fact[m]%mod;
  46.  
  47.  
  48.         cout<<res<<endl;
  49.     }
  50.  
  51.  
  52.     return 0;
  53. }
  54.

Comments