2017 사천성 새엘나이스 트릭 사유+dp
제목:
제목은 임의의 수에서 세 개의 수를 골라서 곱하고 합친 공식을 주었습니다. 이제 임의의 수에서 네 개의 수를 골라서 곱하고 합친 다음에 마지막 답안을 물어보세요. 1e9+7에 대한 모범을 얻으세요.
아이디어:
이 문제는 정말 내 솥이다. 시합 후에 팀원들에게 한바탕 자극을 받아 막다른 골목으로 들어갔다. 그때 세 가지 공식을 주었기 때문에 나는 네 가지 공식을 밀어야 한다고 오도했다.결국 5시간, 정말 5시간, 나는 계속 밀고 있다가 죽어라 나오지 못했다...
사실 이 문제는 정말 엉터리이다. 첫 번째 방법은 dp야. dp[i][j]는 전 i개수이고 임의의 j항의 곱셈의 합이 얼마면 다음과 같은 방정식을 내놓을 수 있다.
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*ai, 그리고 경계를 처리하면 됩니다...
우리는 네 가지를 구하기 때문에 j는 최대 4이고 복잡도는 O(n)이다.
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+10;
int n;
ll a[maxn];
ll dp[maxn][10];
ll ans;
int main(){
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
dp[1][1]=a[1];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=min(i,4);j++)
{
if(j==1)
{
dp[i][j]=dp[i-1][j]+a[i];
dp[i][j]%=mod;
}
else
{
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*a[i];
dp[i][j]%=mod;
}
}
}
printf("%lld
",dp[n][4]);
}
return 0;
}
또 다른 사고방식은 네가 네 가지 곱셈을 요구하고 너에게 세 가지 곱셈의 합을 주었으니 너는 이용해야 한다!!!우리는 i개수에 대해 그 앞의 i-1개수에 대해 3개를 곱해서 그것과 더하는 것은 i를 추출하는 것과 같다. 앞의 i-1개수는 임의의 3항의 곱셈의 합을 취하고 다시 i를 곱한다.그러면 이 세 항목의 곱셈과 공식이 쓸모가 있을 것이다.
(i 뒤에 있는ai가 포함된 것은 뒤에 있는 것으로 해결하면 중복을 피할 수 있다)
복잡도도 O(n)와 비슷하다.
우리는 하나만 계산하고 대응하는 a[i]를 안에 넣으면 돼...매거의 번거로움을 덜었다.
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+10;
int n;
ll a[maxn];
ll ans;
ll quick(ll x,ll y)
{
ll res=1;
while(y)
{
if(y&1)
res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res%mod;
}
ll inv6=quick(6,mod-2);
ll solve(ll x,ll y,ll z)
{
ll s=0;
s=quick(x,3);
s=(s-3*x*y%mod+mod)%mod;
s=(s+2*z)%mod;
return s*inv6%mod;
}
int main(){
while(~scanf("%d",&n))
{
ll x=0,y=0,z=0;
ans=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
if(i>3)
{
ans=(ans+solve(x,y,z)*a[i]%mod)%mod;
}
x=(x+a[i])%mod;
y+=quick(a[i],2);
z+=quick(a[i],3);
y%=mod;
z%=mod;
}
printf("%lld
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
codeforce 991E(조합수 반복 검색)제목 링크: 링크 열기 클릭 샤오밍이 헷갈릴 때 본 자동차 번호판 숫자를 실제 숫자와 비교해 보자. ① 실제로 나온 숫자는 샤오밍이 다 봤다 ② 샤오밍은 같은 숫자만 보고 적을 수는 없다 ③ 차량 번호는 전도 제로가...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
