356。。。
实际上求的就是N的排列中多少个排列只有K个不在位置上。。
那么答案就是C(N,K)*D(N-K)。。D是错排。。错排不知道者可以google之。。
但是高精十分BT。。实际上我怎么会没时间写模拟题呢？都是栽在这题上了。。555
不过总算是在比赛结束前过了。。
由于输出居然是要用不可约分数。。莫非要写一个高精度欧几里得算法吗？天阿。。
如果你真去写那你就傻了。。。
答案是D(n-k)/((n-k)!(k)!)
换句话说公约数的素因子《＝100。。。
那么一个个化就OK了。。
不过程序还是很长。。好羡慕JAVA阿。。自带高精度运算功能的。。
#include<iostream>
#include<cstring>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=110;
int Prime[]=
{2,3,5,7,11,
13,17,19,23,29
,31,37,41,43,47
,53,59,61,67,71
,73,79,83,89,97};
const int ps=25;
int N,K;
struct Num
{
int P;
Num(){memset(P,0,sizeof(P));}
void mult(int a)
{
for(int i=0;i<ps;i++)
{
if(a==1) break;
while(a%Prime[i]==0)
a/=Prime[i],P[i]++;
}
}
void divide(int a)
{
for(int i=0;i<ps;i++)
{
if(a==1) break;
while(a%Prime[i]==0)
a/=Prime[i],P[i]–;
}
}
};
const int maxlen=200;
struct BigNum
{
int Q[maxlen],last;
BigNum(int x=0)
{memset(Q,0,sizeof(Q));Q[0]=x;last=0;}
int operator[](int v) const
{return Q[v];}
int& operator[](int v)
{return Q[v];}
BigNum operator+(const BigNum&x)
{
BigNum now;now.last=max(last,x.last);
int d=0;
for(int i=0;i<=now.last;i++)
{
d+=Q[i]+x[i];
now[i]=d%10;
d/=10;
}
while(d)
{
now[++now.last]=d%10;
d/=10;
}
return now;
}
void operator*=(int x)
{
int d=0;
for(int i=0;i<=last;i++)
{
d+=Q[i]*x;
Q[i]=d%10;
d/=10;
}
while(d>0)
{
Q[++last]=d%10;
d/=10;
}
}
BigNum operator*(const BigNum&x)
{
BigNum now;now.last=x.last+last;
memset(now.Q,0,sizeof(Q));
for(int i=0;i<=last;i++)
for(int j=0;j<=x.last;j++)
now[i+j]+=Q[i]*x[j];
int d=0;
for(int i=0;i<=now.last;i++)
{
d+=now[i];
now[i]=d%10;
d/=10;
}
while(d)
{
now[++now.last]=d%10;
d/=10;
}
}
int Mod(int x)
{
int d=0;
for(int i=last;i>=0;i–)
{
d*=10;
d+=Q[i];
d%=x;
}
return d;
}
void Divide(int x)
{
int rest=0;
for(int i=last;i>=0;i–)
{
rest=rest*10+Q[i];
Q[i]=rest/x;
rest%=x;
}
while(Q[last]==0)
last–;
}
void operator=(const BigNum&x)
{
last=x.last;
memmove(Q,x.Q,sizeof(Q));
}
void show()
{
for(int i=last;i>=0;i–)
cout<<Q[i];
}
};
BigNum Get(Num x)
{
BigNum now(1);
for(int i=0;i<ps;i++)
{
for(int j=0;j<x.P[i];j++)
now*=Prime[i];
}
return now;
}
BigNum D[maxn];
void CalD(int n)
{
D[0][0]=1;D[1][0]=0;
for(int i=2;i<=n;i++)
{
D[i]=D[i-1]+D[i-2];
D[i]*=(i-1);
}
}
Num C;
int main()
{
cin>>K>>N;
if(N-K==1)
{
cout<<0<<endl;
return 0;
}
CalD(N-K);
for(int i=1;i<=K;i++)
C.mult(i);
for(int i=1;i<=N-K;i++)
C.mult(i);
BigNum left,right;
left=D[N-K];
for(int i=0;i<ps;i++)
{
while(left.Mod(Prime[i])==0&&C.P[i]>0)
left.Divide(Prime[i]),C.P[i]–;
}
right=Get(C);
left.show();cout<<"/";right.show();
}
357。。。好无聊的水题阿。。要是能跳明显一开始就跳。。
然后枚举每个开始UP or DOWN的点算答案。。。
Code。。。
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>2;
bool Digit[10]={0};
bool UP,DOWN,FLY;
int dist[100],s,t;
void init()
{
cin>>Digit[1]>>Digit[2]>>Digit[3]>>UP>>
Digit[4]>>Digit[5]>>Digit[6]>>DOWN>>
Digit[7]>>Digit[8]>>Digit[9]>>FLY>>Digit[0];
}
void renew(int&x,int c)
{
x=min(x,c);
}
void Fly()
{
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
if(Digit[i]&&Digit[j])
renew(dist[i*10+j],3);
}
void Go(int j)
{
int c=dist[j];
if(UP)
renew(dist[(j+1)%100],c+1);
if(DOWN)
renew(dist[(j+99)%100],c+1);
}
int main()
{
init();cin>>s>>t;
REP(i,100) dist[i]=inf;
dist[s]=0;
if(FLY)
Fly();
for(int i=0;i<10;i++)
if(Digit[i])
renew(dist[i],1);
int ans=dist[t];
for(int i=0;i<100;i++)
if(dist[i]!=inf)
{
if(UP)
renew(ans,(t-i+100)%100+dist[i]);
if(DOWN)
renew(ans,(i-t+100)%100+dist[i]);
}
if(ans==inf)
cout<<-1<<endl;
else
cout<<ans<<endl;
}