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;↵
}[submission:53500731] in the mashup and [submission:53500951] in the contest.
(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)↵
#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;↵
}
