CSP-S 2019--에미야네 오늘의 밥--DP+사고
dp[j][k]=(dp[j][k]+dp[j-1][k]*(sum[j]-a[j][i]))%mod;
dp[j][k+1]=(dp[j][k+1]+dp[j-1][k])%mod;
dp[j][k+2]=(dp[j][k+2]+dp[j-1][k]*a[j][i])%mod;
코드는 다음과 같습니다.
#include
#include
#include
#include
using namespace std;
long long dp[201][3001],a[201][3001],sum[2001];
long long ans=1,n,m;
int mod=998244353;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
sum[i]=(sum[i]+a[i][j])%mod;
}
ans=(ans*(sum[i]+1))%mod;
}
ans=(ans+mod-1)%mod;
for(int i=1;i<=m;i++)
{
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int j=1;j<=n;j++)
for(int k=0;k<=2*(j-1);k++)
{
dp[j][k]=(dp[j][k]+dp[j-1][k]*(sum[j]-a[j][i]))%mod;
dp[j][k+1]=(dp[j][k+1]+dp[j-1][k])%mod;
dp[j][k+2]=(dp[j][k+2]+dp[j-1][k]*a[j][i])%mod;
}
for(int j=n+1;j<=2*n;j++)
ans=(ans+mod-dp[n][j])%mod;
}
printf("%lld",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[블루 브리지컵 홈페이지 시험문제-알고리즘 향상] 최대치(dp,0-1 가방) 구하기문제 설명 선택한 모든 수의 ai+bi의 정수와 최대치를 선택해야 합니다.그리고 당신이 선택한 수 쌍의ai의 합과 비음,bi의 합과 비음을 요구합니다. 입력 형식 출력 형식 선택한 숫자 쌍의ai+bi의 합을 출력합니...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
