首页 > 搜索 > DFS搜索 > hdu 2481 Toy-分治-[解题报告]C++
2014
01-26

hdu 2481 Toy-分治-[解题报告]C++

Toy

问题描述 :

On birthday, Anthony got a toy. It is constructed with N+1(N>=3) balls and 2*N sticks. All balls are in a same plane. One of them is special, while the other N balls are connected to it by N sticks with the same length. The angles between any two adjacent sticks are equal. And finally, any two adjacent balls(except the central one) are connected by a stick.
  Here are two examples:

Anthony wanted to remove N sticks, leaving all balls still connected. He wanted to know the number of all legal solutions. Your task is to solve this problem for him.
  Notice that if a solution will be the same as another one by rotation, these two solutions should be consider as the same.
The answer may be quite large. You just need to calculate the remainder of the answer when divided by M.

输入:

Input contains several test cases.
For each test case, there is only one line containing two integers N and M(3<=N<=10^9, 2<=M<=10^9).
Input is terminated by EOF.

输出:

Input contains several test cases.
For each test case, there is only one line containing two integers N and M(3<=N<=10^9, 2<=M<=10^9).
Input is terminated by EOF.

样例输入:

3 10000
4 10000
4 10

样例输出:

6
13
3


       08年成都现场赛的神题,传说现场就清华一支队伍出了此题。这题的难点在于递推方程。网上有万物皆数大神和AekdyCoin大神的详细解题报告,先找递推式,然后用矩阵快速幂求答案的方法,这种方法速度很快,但是递推过程比较繁琐,并且代码量不小。另一种方法是直接转化为生成树计数问题,然后根据题目的特殊性质对行列式进行化简,代码比较短。还有一个很恶心的地方就是这题的取模数<=10^18,所以long long装不下,要二分模拟乘法,贴了一个别人的模板- -

       我实现了一下第一种方法,最后惊奇的发现居然登顶了,看来质因数分解后DFS在大数据的时候效率还是很不错的- -
       HDU 2481 Toy - endlesscount - Memento

 

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 32000
#define ll long long
using namespace std;
int G;
ll mod;
bool notprime[ N ];
int prime[ N ],pp;
int fac[ 50 ][ 3 ],fp;
struct matrix{
ll num[2][2];
}ma[ 32 ];
ll mult_mod(ll a,ll b ){
ll ret=0,tmp=a;
if(b<0)b+=mod;
if(tmp<0)tmp+=mod;
while(b){
if(b&0x1)if((ret+=tmp)>=mod)ret-=mod;
if((tmp<<=1)>=mod)tmp-=mod;
b>>=1;
}
return ret;
}
matrix mult( matrix &a,matrix &b ){
matrix ret;
for( int i=0;i<2;i++ )
for( int j=0;j<2;j++ ){
ret.num[i][j]=0;
for( int k=0;k<2;k++ )
ret.num[i][j]+=mult_mod( a.num[i][k],b.num[k][j] );
ret.num[i][j]%=mod;
}
return ret;
}
void init_prime( ){
for( int i=2;i<N;i++ ){
if( !notprime[i] ) prime[ pp++ ]=i;
for( int j=0;j<pp&&i*prime[ j ]<N;j++ ){
notprime[ i*prime[ j ] ]=true;
if( i%prime[ j ]==0 ) break;
}
}
}
void init_ma(){
ma[0].num[0][0]=3,ma[0].num[0][1]=1,ma[0].num[1][0]=-1;
for( int i=1;i<32;i++ )
ma[i]=mult( ma[i-1],ma[i-1] );
}
void fact( int n ){
fp=0;
for( int i=0;i<pp&&n>1;i++ )
if(n%prime[ i ]==0){
for(fac[fp][0]=prime[i],fac[fp][1]=0,fac[fp][2]=1;n%prime[i]==0;n/=prime[i],fac[fp][1]++,fac[fp][2]*=prime[i]);
fp++;
}
if(n>1) fac[fp][0]=n,fac[fp][1]=1,fac[fp++][2]=n;
}
long long getv( int n ){
if( n==1 ) return 1;
n-=2;
matrix ans;
memset( ans.num,0,sizeof( ans.num ) );
ans.num[0][0]=3,ans.num[0][1]=1;
for(int i=0;n;n>>=1,i++)
if( n&1 )
ans=mult( ans,ma[i]);
return ( 3*ans.num[0][0]%mod-2*ans.num[0][1]%mod-2 )%mod;
}
void DFS( ll &res,int g,int phi,int d ){
if( d==fp ){
res=( res+mult_mod( phi,getv( g ) ) )%mod;
return;
}
for( int i=0,p=fac[d][2];i<=fac[d][1];i++,p/=fac[d][0] )
DFS( res,fac[d][2]/p*g,phi*(p-p/fac[d][0]),d+1 );
}
long long cal(int m){
fact( G );
long long ret=0;
DFS( ret,1,1,0 );
ret=( ret/G%m+m )%m;
return ret;
}
int main( void ){
int m;
init_prime();
while( cin>>G>>m ){
mod=1ll*G*m;
init_ma();
cout<<cal(m)<<endl;
}
}


解题转自:http://endlesscount.blog.163.com/blog/static/8211978720122149120772/


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。