CodeChef submission 757700 (C++ 4.3.2) plaintext list. Status: AC, problem COLCHAIN, contest . By kamranmaharov (kamranmaharov), 2011-12-15 19:27:00.

#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <queue> #include <stack> #include <fstream> #include <set> #include <map> #include <cmath> #pragma comment(linker,"/STACK:16777216") #define inf 1000000000 #define MP make_pair using namespace std; typedef long long i64; typedef unsigned long long u64; const i64 mod=1000000007; i64 f[100100],sum[100100]; i64 fact[100100]; i64 res; int main() { int t,n,m; fact[0]=1; for(int i=1;i<=100050;i++)fact[i]=(fact[i-1]*i)%mod; cin>>t; while(t--){ cin>>n>>m; for(int i=2;i<=m+1;i++){f[i]=1;sum[i]=sum[i-1]+f[i];} for(int i=m+2;i<=n;i++){//sum up f[i-m],f[i-m+1]...f[i-1] f[i]=(sum[i-1]+mod-sum[i-m-1])%mod; sum[i]=(sum[i-1]+f[i])%mod; } res=0; for(int i=n-m+1;i<=n;i++)res=(res+f[i]*(i-(n-m))%mod)%mod; res=res*fact[m]%mod; cout<<res<<endl; } return 0; }

## Comments

**Please login at the top to post a comment.**