Yue Fei's Battle
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 760 Accepted Submission(s): 266
Then Yue Fei was put into * and was killed under a charge of "maybe there is" treason. But later Yue Fei was posthumously pardoned and rehabilitated, and became a symbol of loyalty to the country. The four corrupted officers who set him up were Qin Hui,Qin Hui's wife Lady Wang, Moqi Xie and Zhang Jun. People made kneeling iron statues of them and put the statues before Yue Fei's tomb (located by the West Lake, Hangzhou). For centuries, these statues have been cursed, spat and urinated upon by people. (Now please don't do that if you go to Hangzhou and see the statues.)
One of the most important battle Yue Fei won is the battle in Zhuxian town. In Zhuxian town, Yue Fei wanted to deploy some barracks, and connected those barracks with roads. Yue Fei needed all the barracks to be connected, and in order to save money, he wanted to build as less roads as possible. There couldn't be a barrack which is too important, or else it would be attacked by enemies. So Yue Fei required that NO barrack could connect with more than 3 roads. According to his battle theory, Yue Fei also required that the length of the longest route among the barracks is exactly K. Note that the length of a route is defined as the number of barracks lied on it and there may be several longest routes with the same length K.
Yue Fei wanted to know, in how many different ways could he deploy the barracks and roads. All barracks could be considered as no different. Yue Fei could deploy as many barracks as he wanted.
For example, if K is 3,Yue Fei had 2 ways to deploy the barracks and roads as shown in figure1. If K is 4, the 3 kinds of layouts is shown in figure 2. (Thick dots stand for barracks, and segments stand for roads):
Please bring your computer and go back to Yue Fei's time to help him so that you may change the history.
For each test, there is only one line containing a integer K(1<=K<=100,000) denoting the length of the longest route.
The input ends by K = 0.
引用了别人的题解。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=,Mod=;
long long dp[N],sum[N],ans;int T,n;
long long Inv(long long x){
return x==?:(Mod-Mod/x)*Inv(Mod%x)%Mod;
}
long long i2,i6;
int main(){
sum[]=;dp[]=;
sum[]=;dp[]=;
i2=Inv();i6=Inv();
for(int i=;i<N;i++){
dp[i]=dp[i-]*(dp[i-]+)%Mod*i2%Mod;
(dp[i]+=dp[i-]*sum[i-]%Mod)%=Mod;
sum[i]=(sum[i-]+dp[i])%Mod;
} while(scanf("%d",&n)!=EOF&&n){
if(n==){printf("1\n");continue;}
else if(n%==){
ans=sum[n/-]*(dp[n/]*(dp[n/]+)%Mod*i2%Mod)%Mod;
ans+=dp[n/]*(dp[n/]-+Mod)%Mod*(dp[n/]-+Mod)%Mod*i6%Mod;
ans=((ans+dp[n/]*(dp[n/]-+Mod)%Mod)%Mod+dp[n/])%Mod;
}
else ans=dp[n/]*(dp[n/]+)%Mod*i2%Mod;
printf("%lld\n",ans);
}
return ;
}