传送门：Problem - C - Codeforces
传送门：Problem - E - Codeforces
dp存储迭代传送+打表找规律emmmm
#include<iostream>#include<algorithm>#include<string.h>#include<stdio.h>#include<math.h>#include<vector>#include<map>#include<set>#include<queue>using namespace std;typedef long long ll;typedef pair<ll, ll> PII;int t;ll n,m; ll N=998244353;ll dp[100];void pan(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return;}pan(b,a%b,x,y);ll tmp=x;x=y;y=tmp-(a/b)*y;}ll ni(ll a,ll mod){ll x,y;pan(a,mod,x,y);return (x%mod+mod)%mod;}ll solve(int x,int p){int s=x;ll u=p;ll ans=1;while(u){ans=ans*s%N;ans=ans*ni(u,N)%N;u--;s--;}return ans%N;}int main() {ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>t;dp[2]=1,dp[4]=3;for(int i=6;i<=60;i+=2){dp[i]=(dp[i-4]+solve(i-4,i/2-3)+solve(i-1,i/2-1))%N;}while(t--){cin>>n;if(n==2){printf("1 0 1\n");}else if(n==4){printf("3 2 1\n");}else{ll ans=solve(n,n/2);printf("%lld %lld 1\n",dp[n],(ans-dp[n]-1+N)%N);}}}
这题只能说jiangly佬tql永远的神！！！太nb了！！！之后又看了睿博佬的代码，dfs也很妙，和dp一样
dp==优化的dfs
dp版代码：
#include<iostream>#include<algorithm>#include<string.h>#include<stdio.h>#include<math.h>#include<vector>#include<map>#include<set>#include<queue>using namespace std;typedef long long ll;typedef pair<ll, ll> PII;int t;ll dp[5][5];ll b[200005];int main() {ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>t;while(t--){ll n,m;cin>>n>>m;for(int i=0;i<=2;i++){for(int j=0;j<=2;j++)dp[i][j]=0;}for(int i=1;i<=n;i++)cin>>b[i];dp[2][1]=m;sort(b+1,b+1+n);ll ans=0;for(int i=1;i<=n;i++){for(int x=2;x>=0;x--){for(int y=1;y>=0;y--){if(x)dp[x-1][y]=max(dp[x-1][y],2*dp[x][y]);if(y)dp[x][y-1]=max(dp[x][y-1],3*dp[x][y]);if(dp[x][y]>b[i]){dp[x][y]+=b[i]/2;ans=i;}}}}printf("%lld\n",ans);}}
dfs版：
#include<iostream>#include<algorithm>#include<string.h>#include<stdio.h>#include<math.h>#include<vector>#include<map>#include<set>#include<queue>using namespace std;typedef long long ll;typedef pair<ll, ll> PII;int t;ll dp[5][5];ll b[200005];int main() {ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>t;while(t--){ll n,m;cin>>n>>m;for(int i=0;i<=2;i++){for(int j=0;j<=2;j++)dp[i][j]=0;}for(int i=1;i<=n;i++)cin>>b[i];dp[2][1]=m;sort(b+1,b+1+n);ll ans=0;for(int i=1;i<=n;i++){for(int x=2;x>=0;x--){for(int y=1;y>=0;y--){if(x)dp[x-1][y]=max(dp[x-1][y],2*dp[x][y]);if(y)dp[x][y-1]=max(dp[x][y-1],3*dp[x][y]);if(dp[x][y]>b[i]){dp[x][y]+=b[i]/2;ans=i;}}}}printf("%lld\n",ans);}}
