I tried to solve 1153F. I got up with an unusual idea.Then this is my code.I clone the 1153F to a mashup.And I accepted with maximum time 1825 ms.But the time limit is only 1 second. Can some one help me to optimize the code? (Because it is not so slow,I think I don't need to change the algorithm,And I only get this way to solve the problem) Code:

include<bits/stdc++.h>

//#include<ext/pb_ds/assoc_container.hpp> using namespace std; //using namespace __gnu_pbds;

define int long long

const int inf=0x3f3f3f3f; const double eps=1e-6; const int mod=998244353; typedef long long ll; int modpow(int x,int y,int md=mod){if(y==0)return 1;int ret=modpow(x,y>>1,md);ret=(ll)ret*ret%md;if(y&1)ret=(ll)ret*x%md;return ret;} int n,k,l; int dp[2][4005],c[4005][4005]; inline int inv(int x){return modpow(x,mod-2);} inline void add(int &x,int y){x=(x+y)%mod;} signed main(){ c[0][0]=1;dp[0][0]=1; cin>>n>>k>>l; for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) if(i||j)c[i][j]=((!i?0:c[i-1][j]*(i-j))+(!j?0:c[i][j-1])),c[i][j]%=mod; // while(1){int x,y;cin>>x>>y;cout<<c[x][y]<<endl;} int ans=0; for(int i=0;i<=n+n;i++){ for(int j=0;j<=n&&j<=i&&j<=(n+n-i);j++){ //dp[i][j]->dp[i+1][j+1] if(!dp[i&1][j])continue; int right=(i-j)/2,left=(i+j)/2; left=n-left;right=n-right; int Left=!left?0ll:c[right][left-1],Right=(left==right)?0ll:c[right-1][left]*j; Left%=mod;Right%=mod; add(dp[(i+1)&1][j+1],dp[i&1][j]*(Left)%mod*inv(Left+Right)%mod); if(j)add(dp[(i+1)&1][j-1],dp[i&1][j]*(Right)%mod*inv(Left+Right)%mod); if(j>=k)ans+=dp[i&1][j],ans%=mod; // fprintf(stderr,"i:%I64d j:%I64d dp:%I64d left:%I64d right:%I64d Left:%I64d Right:%I64d\n",i,j,dp[i][j],left,right,Left,Right); }memset(dp[i&1],0,sizeof dp[i&1]); } ans=ans*l%mod*inv(n+n+1)%mod; cout<<ans<<endl; return 0; }