XXY 的 NOIP 模拟赛 3
题目		全排列	埃及分数	走楼梯
英文题目与子目录名		permutation	egypt	stair
可执行文件名		permutation	egypt	stair
输入文件		permutation.in	egypt.in	stair.in
输出文件		permutation.out	egypt.out	stair.out
单个测试点时间限制		1 秒	1 秒	1 秒
内存限制		256M	256M	256M
测试点数目		10	10	10
每个测试点分值		10	10	10
比较方式		全文比较（过滤行末空格及文末回车）
题目类型		传统	传统	传统
是否有部分分		无	无	无
	C++	permutation.cpp	egypt.cpp	stair.cpp
提交文件	C	permutation.c	egypt.c	stair.c
	Pascal	permutation.pas	egypt.pas	stair.pas

1. 文件名（程序名和输入输出文件名）必须使用英文小写。

1. C / C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须为 0。由于没有 return 0 造成的程序无输出，后果自负。

1. 评测使用 Cena 评测软件，Microsoft Windows XP(32 位 / SP3)操作系统

1. Long long 的输入输出 请使用%I64d

1. 题目难度与顺序无

 

全排列

(permutation.cpp/c/pas)

Description

从 n 个不同元素中任取 m(m≤n)个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。当 m=n 时所有的排列情况叫全排列。

你觉得 xxy 会问你全排列的个数吗？Xxy：这个问题能淹死你，我才不问呢。我要问的是求 n 的全排列中，先递增后递

减、先递减后递增的全排列的个数。由于答案可能很大，对 p 取余

Input

输入包含多组测试数据每组测试数据一行两个整数 n，p

Output

对于每组测试数据输出一行表示答案

Example

 permutation.in　　　　　　　　　　　　　　　　　　　permutation.out

3 5 　　　　　　　　　　　　　　　　　　　　　　　　4

2 233     　　　　　　　　　　　　　　　　　　　　　　0

Hint 

设数据组数为 T

对于 10%的数据，n<=10,p<=1000,T=1

对于另外 10%的数据，n<=12,p<=1000,T<=12

对于另外 10%的数据，n<=100,p<=100000,T<=100

对于另外 10%的数据，n<=100000,p<=1000000,T=1

对于另外 10%的数据，n<=100000,p<=1000000,T<=1000

对于另外 20%的数据，n<=1e9,p<=1e9,T<=1000

对于 100%的数据，n<=1e18,p<=1e18,T<=1000

 

 Ｏ(≧口≦)Ｏ   zz啊，考试的时候看到了多组数据还激动了半天，结果！！！！忘记写！EOF！！！！了！！！还忘记写输出换行符了！w(ﾟДﾟ)w

知道会暴long long写了个快速乘结果返回了个int（仿佛看到了一个大在zz！！）

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long long using namespace std;ll n,p;ll qchen(ll a,ll b,ll p){    ll ans=0;    while(b)    {        if(b&1) ans=(ans+a)%p;        a=(a*2)%p;        b/=2;    }    return ans;}ll qpow(ll a,ll b,ll p){    ll res=1;    while(b)    {        if(b&1) res=qchen(res,a,p);        a=qchen(a,a,p);        b/=2;    }    return res;}int main(){    freopen("permutation.in","r",stdin);    freopen("permutation.out","w",stdout);    while(scanf("%I64d%I64d",&n,&p)!=EOF)    {        if(n==1) printf("0\n");         else printf("%I64d\n",(qpow(2,n,p)-4+p)%p);    }    return 0;}
           
          
         
        
       

 

埃及分数

(egypt.cpp/c/pas)

Description

对于一个分数 a/b（a！=1），将它表示为 1/x + 1/y + 1/z ……的形式，x，y，z……互不相同。

多解取加数少的。加数相同时，取最小的分数最大的，最小分数相同时，取次小分数最大的，以此类推。

输入保证a<b且gcd（a，b）=1

Input

输入包含多组测试数据每组测试数据包含一行 2 个数 a，b

Output

对于每组测试数据，输出一行表示答案，只输出分母，每个分母之间空 1 格

从小到大输出

Example

egypt.in　　　　　　　　　　egypt.out

5 6                                           2    3

8 9　　　　　　　　　　　　　2   3   18

Hint 

对于 10%的数据，a，b<=10

对于另外 10%的数据，a,b<=100

对于另外 20%的数据，a，b<=10000对于另外 30%的数据，a，b<=100000对于 100%的数据，a，b<=1000000

由于本题时间复杂度不随数据范围的递增而递增，在此给出 std 耗时：

30%  <=0.01s

10%  <=0.2s

40%  <=0.5s

20%  <=0.9s

 出自：

 不过出题人很没良心的将这个题数据加强了、、、

 不过这个题正解还是搜索 

我们以原分数可以分解成的分数的个数为层数，从一开始的状态将分母从小到大枚举。若在某一曾搜到了解因为我们要输出最少的，因此最先搜到的即为最优解。

然后我们在进行搜索，我们先预处理出最小的分母，然后在从最小的分母开始循环，这样可以将时间复杂度降低。

 最小的分母是什么？？因为a/b>=1/x;此处的x为最小的分母，即1/x为最接近a/b的分数，我们将这个式子进行移项，可以得到，ax>=b,最小的分数一定是第一个是这个式子成立的，我们枚举x然后判断式子是否成立。

然后我们在进行搜索，void dfs(ll fz,ll fm,ll now,ll cnt)  fz为当前的分子，fm为当前的分母，now为当前所分解到的分母的大小，cnt为我当前剩下的要分解的分母的个数。

如果当前分子为负数直接返回值即可，如果当前分子为1或者分母最接近now这说明我们当前的now即为最后的值，直接将其赋到tmp中，然后在判断当前是否为最优解，如果是，进行更新。（在这个地方我们的最优解为分解成的分母个数相同时，在按照题目中给出的另一个条件来判断是否为最优解）

判断函数：我们要求最小的分数最大，即最大的分母最小，然后我们判断我们新更新出来的答案是否和原来的答案相同，如果不相同，我们更新答案

如果当前为最后一个分解成的分母，直接return；

反之，继续进行分解，我们要限制一下枚举的头结点跟尾结点，防止超时、、、

边界条件：从now跟能找得到的最小的分母中取一个最大值，防止枚举到的分数大于要拆分的分数，最后的边界条件：(i*fz)<=(fm*cnt)，可以转化为：我们当前枚举到的i为当前拆分的最小的分母，即为最大的分数，cnt是我们剩下的还没确定的分母的个数，剩下的分数一定比当前分数小，如果我们分母的个数*最大的这个分数都比我们要分解的这个分数小的话，那么这种分解方法一定是不合理的，直接结束枚举。

如果这种分解是合法的，我们继续分解减去当前分解出的分数后的分数，为fz/fm-1/i  我们进行通分原式就可以化成fz*i-fm/fm*i 我们对我们通分出式子约分，即为(fz*i-fm)/gcd   /  fm*i/gcd。然后继续进行搜索

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 1000005#define LL long longusing namespace std;bool flag;LL a,b,n,tmp[N],ans[N];LL read(){    LL x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}LL get_gcd(LL a,LL b){    if(b==0) return a;    return get_gcd(b,a%b);}void DFS(LL x,LL y,LL now,LL cnt){    if(x<0) return ;    if(cnt==1)    {        if(x==1&&y>=now)          if(y
            
             1;--i) ans[i]=tmp[i]; } return ; } for(int i=now;(x*i)<=(y*cnt);++i) { LL gcd; tmp[cnt]=i; gcd=get_gcd(x*i-y,y*i); DFS((x*i/gcd-y/gcd),y*i/gcd,i+1,cnt-1); }}int main(){ freopen("egypt.in","r",stdin); freopen("egypt.out","w",stdout); a=read(),b=read(); ans[1]=1<<30; for(n=1;;++n) { DFS(a,b,2,n); if(flag) { for(int i=n;i>=1;i--) printf("%I64d ",ans[i]); break; } } return 0;}
            
           
          
         
        
       

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 110000#define ll long long using namespace std;bool flag;ll a,b,m,ans[N],tmp[N];ll read(){    ll x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}ll get_gcd(ll a,ll b){    if(!b) return a;    return get_gcd(b,a%b);}ll get_min(ll a,ll b){    for(int i=1;;i++)     if(a*i>=b) return i;}ll if_change(){    for(int i=1;i<=m;i++)     if(tmp[i]!=ans[i]) return ans[i]>tmp[i];    return 0;}void dfs(ll fz,ll fm,ll now,ll cnt){    if(fz<0) return ;    if(fz==1&&fm>=now)    {        tmp[cnt]=fm;        if(if_change()||!flag)        {            for(int i=m;i>=1;--i)             ans[i]=tmp[i];        }        flag=true;        return ;    }    if(cnt==1) return ;    ll gcd;    for(int i=max(now,get_min(fz,fm));(i*fz)<=(fm*cnt);i++)    {        tmp[cnt]=i;        gcd=get_gcd(fz*i-fm,fm*i);        dfs((fz*i-fm)/gcd,fm*i/gcd,i+1,cnt-1);    }}int main(){    freopen("egypt.in","r",stdin);    freopen("egypt.out","w",stdout);    a=read(),b=read();    for(m=1;;m++)    {        dfs(a,b,get_min(a,b),m);        if(flag)        {            while(m)              printf("%I64d ",ans[m--]);            break;        }    }    return 0;}
           
          
         
        
       

 

 

 

走楼梯

(stair.cpp/c/pas)

Description

由于经典走楼梯问题被 xxy 升级了 2 次，上帝非常满意，所以当 xxy 完成这最后一次跳跃时，会有一定的几率开启轮回之梯。轮回之梯有 n 阶，每一阶上都会有一个轮回指数，xxy 用不同的策略走到轮回之梯的第 n 阶，会得到不同的轮回值。

由于轮回之梯不是普通的楼梯，每走一步需要消耗极大的体力，xxy 体力有限。上帝允许 xxy 在中途休息。所以 xxy 如果在第 i 阶，他可以选择立刻走到第 i+1 阶，也可以选择在第 i 阶休息一会儿。休息和立刻走看做不同的走楼梯方式。

上帝说：我现在给你提供所有台阶的轮回指数，我需要你回答所有不同的走轮回之梯的方式获得的轮回值之和。如果某种方式你算不出来，你可以亲自去走一遍。你走的次数越少，就会有越大的几率开启六道轮回。Xxy 非常想开启六道轮回，但由于之前在楼梯上跳来非常累，现在不想动弹，连飞也不想飞。所以只能在求助学信息学奥赛的你了。

轮回值计算方式：

轮回值为所有的轮回子值之和。

设第 i 个台阶的轮回指数为 xi，如果 xxy 连续从第 L 阶走到第 R 阶，那么 xxy 可以得到的轮回子值为 xL 一直累乘到 xR。特别的，当 L=R 时，轮回子值为 xL。

注意：xxy 开始在轮回之梯的第 1 阶，可以选择先休息一会儿，也可以立刻走到第 2 阶。走一遍轮回之梯指的是从第 1 阶走到第 n 阶。

由于答案很大，上帝可不想看到几千几百个数字，所以你只需要告诉他答案对

1000000007 取模。

Input

第一行一个整数 n。

接下来 n 个整数，表示 xi

Output

输出一行表示答案

Example

stair.in　　　　　　　　　　　　　　stair。out

2　　　　　　　　　　　　　　　　　　30

1  2   4

Hint

对于 10%的数据，1<=n<=10,1<=xi<=10

对于另外 20%的数据,所有的 Xi=1

对于另外 20%的数据,n<=100,xi<=1e5对于另外 20%的数据,n<=1000,xi<=1e5对于 100%的数据，n<=100000,xi<=1e9

 

仔细读题目你就会发现题目描述的是这样一个问题：

在纸上有一个长为n的数列，第i项值为ai。我们如果要在这些数之间添加加号或乘号。问对于不同的2n−1种方案，所有答案的和是多少？

正解：dp

我们用dp【i】记录我们更新到了序列中的第i个数。用a【i】表示当前位置上的数字的值。

我们枚举最后一个放加号的位置j，这样从这个位置往后我们放的都是乘号。这样在这j个位置我们对于每一个位置可以选择放乘号也可以选择放加号，这样我们一共有2^j-1种方法（因为最后一个位置我们已经确定要放加号了）乘法原理。

这样dp【i】=dp[i]=Σ（dp[j]+2^（j-1）*（a[j+1]*a[j+2]……*a[i]））

这样我们能看到我们暴力枚举i在枚举最后一个放加号的位置j然后在枚举累成，这样的时间复杂度是o(n^3)的，显然会T的很惨。

我们看看有什么方法可以优化的，我们可以发现（a[j+1]*a[j+2]……*a[i]）累成的这个地方可以优化，我们可以用一个前缀积来进行优化，这样这一坨我们就可以不枚举，直接用sum[i]/sum[j]来表示，当然这个地方我们要进行取模就要用到拓展欧几里得求逆元了。然后我们还可以预处理2的j-1次方，这样我们就把时间复杂度降到o（n^2）然后我们在用一下前缀和优化，就可以将时间复杂度降到o（n）。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 210000#define mod 1000000007#define ll long longusing namespace std;ll x,y,n,gcd,a[N],ans;ll c[N],dp[N],sum[N],ji[N],f[N];ll  read(){    ll x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}ll exgcd(ll a,ll b,ll &x,ll &y){    if(!b)    {        x=1,y=0;        return a;    }    int tmp,r=exgcd(b,a%b,x,y);    tmp=x,x=y,y=tmp-a/b*y;    return r;}int main(){    freopen("sequenceQBXT.in","r",stdin);   freopen("sequenceQBXT.out","w",stdout);    n=read(); f[0]=1;    for(int i=1;i<=n;i++) f[i]=f[i-1]*2%mod;    for(int i=1;i<=n;i++) a[i]=read(); ji[1]=a[1];    for(int i=2;i<=n;i++) ji[i]=ji[i-1]*a[i]%mod;    for(int i=1;i<=n;i++)     {        x=0,y=0;        gcd=exgcd(ji[i],mod,x,y);        x=(x+mod)%mod;        c[i]=x;//c为pre[i]在膜mod下的乘法逆元。     }    long long sum1=0,sum2=1;    for(int i=1;i<=n;i++)    {        dp[i]=(sum1+sum2%mod*ji[i]%mod)%mod;        sum1=(sum1+dp[i])%mod;        sum2=(sum2+f[i-1]%mod*c[i]%mod)%mod;    }    printf("%lld",dp[n]);    return 0;}
          
         
        
       
      

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 210000#define mod 1000000007#define ll long longusing namespace std;ll x,y,n,gcd,a[N],ans;ll c[N],dp[N],sum[N],ji[N],f[N];ll  read(){    ll x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}long long pow(long long a,long long b){    long long res=1;    while(b){        if(b&1)            res=res*a%mod;        a=a*a%mod;        b>>=1;     }    return res;}int main(){    freopen("sequenceQBXT.in","r",stdin);    freopen("sequenceQBXT.out","w",stdout);    n=read(); f[0]=1;    for(int i=1;i<=n;i++) f[i]=f[i-1]*2%mod;    for(int i=1;i<=n;i++) a[i]=read(); ji[1]=a[1];    for(int i=2;i<=n;i++) ji[i]=ji[i-1]*a[i]%mod;    for(int i=1;i<=n;i++) c[i]=pow(ji[i],mod-2);    long long sum1=0,sum2=1;    for(int i=1;i<=n;i++)    {        dp[i]=(sum1+ji[i]*sum2%mod)%mod;        sum1=(sum1+dp[i])%mod;        sum2=(sum2+f[i-1]%mod*c[i]%mod)%mod;    }    printf("%lld",dp[n]);    return 0;}