HDU 5136 Yue Fei's Battle
i=K/2가 짝수일 때 양쪽의 두 갈래 나무의 깊이는 모두 K/2이고 양쪽이 같을 수도 있고 다를 수도 있음을 고려하면 방안수는 dp[i]∗(dp[i]+1)/2이다.
K가 홀수이면 중간 점은 3개의 브랜치를 연결하고 최소 2개의 브랜치 깊이는 K/2입니다.3개의 지점에 하나의 지점 깊이가 K/2보다 작으면 방안수 dp[i](dp[i]+1)/2∗sum[i-1]은 3개의 지점 깊이가 모두 K/2이다. 3개의 지점이 모두 같으면 방안수 dp[i]는 3개의 지점 2개가 같고 방안수는 dp[i]∗(dp[i]-1)이다. 3개의 지점이 서로 다르면 방안수 C(dp[i], 3)의 모든 상황을 합치면 된다.
#include <bits/stdc++.h>
using namespace std;
#define prt(k) cerr<<#k" = "<<k<<endl
typedef long long ll;
const ll mod = 1e9 + 7;
ll pmod(ll a, ll n)
{
ll ret = 1;
for (; n; n>>=1, a=a*a%mod)
if (n&1)
ret = ret * a % mod;
return ret;
}
ll getinv(ll a)
{
return pmod(a, mod - 2);
}
const int N = 100100;
ll dp[N + 5], sum[N + 5];
const ll inv2 = getinv(2);
ll sub(ll a, ll b)
{
return (a - b + mod) % mod;
}
void init()
{
dp[0] = 1;
dp[1] = 1;
sum[0] = 1;
sum[1] = 2;
for (int i=1;i<N;i++)
{
dp[i+1] = (dp[i] * sum[i-1] % mod);
dp[i+1] = (dp[i+1] + (dp[i] + 1)%mod * dp[i] % mod * inv2 % mod) % mod;
sum[i+1] = (sum[i] + dp[i+1]) % mod;
}
}
ll C3(ll a)
{
return ((a*sub(a,1)%mod) * sub(a,2) % mod) * getinv(6) % mod;
}
ll f(int K)
{
int i = K / 2;
ll ans = ((dp[i] * (dp[i] + 1)%mod) % mod * inv2 % mod ) % mod;
ll tmp = ans;
if (K%2==0) {
return ans;
}
ans = (ans * sum[i-1]) % mod;
ans = (ans + dp[i]) % mod;
ans = (ans + (dp[i]-1+mod)%mod * dp[i] % mod) % mod;
ans = (ans + C3(dp[i])) % mod;
return ans;
}
int main()
{
int K;
init();
while (cin>>K, K)
{
ll ans = f(K);
cout<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
