9.13——模拟赛

T1 全排列

(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

 1 #include <cstdio>
 2 
 3 #define LL long long
 4 inline void read(LL &x)
 5 {
 6     x=0; register char ch=getchar();
 7     for(; ch>'9'||ch<'0'; ) ch=getchar();
 8     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
 9 }
10 
11 LL n,p;
12 inline LL mul(LL a,LL b,LL mod)
13 {
14     LL ret=0;
15     for(; b; b>>=1)
16     {
17         if(b&1) (ret+=a) %=mod;
18         (a<<=1) %=mod;
19     }
20     return ret;
21 }
22 inline LL Quick_pow(LL b,LL mod)
23 {
24     LL ret=1,base=2;
25     for(; b; b>>=1)
26     {
27 //        if(b&1) ret=((ret%mod)*(base%mod))%mod;
28 //        base=((base%mod)*(base%mod))%mod;
29         if(b&1) ret=mul(ret,base,mod);
30         base=mul(base,base,mod);
31     }
32     return (ret-4+mod)%mod;
33 }
34 int Persist()
35 {
36 //    freopen("permutation.in","r",stdin);
37 //    freopen("permutation.out","w",stdout);
38     for(;~scanf("%I64d%I64d",&n,&p); )
39         if(n==1) puts("0");
40         else printf("%I64d
",Quick_pow(n,p));
41     return 0;
42 }
43 
44 int Aptal=Persist();
45 int main(){;}
打表找规律+快速幂+快速乘

T2  埃及分数（题目要求多余codevs）

(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的分数的个数、

剪枝：用没用过的最小的分母，且保证对于当前使用的分母i，剩余分数个数cnt，满足fz/fm<=cnt/i

 1 #include <cstring>
 2 #include <cstdio>
 3 
 4 #define LL long long
 5 inline void read(LL &x)
 6 {
 7     x=0; register char ch=getchar();
 8     for(; ch>'9'||ch<'0'; ) ch=getchar();
 9     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
10 }
11 
12 const int N(1e5+5);
13 LL a,b,n,tmp[N],ans[N];
14 bool flag;
15 
16 #define max(a,b) (a>b?a:b)
17 inline int get_first(int a,int b)
18 {
19     for(int i=1; ; i++)
20         if(1.0/i<=a*1.0/b) return i;
21 }
22 inline bool if_change()
23 {
24     for(int i=1; i<=n; ++i)
25         if(tmp[i]!=ans[i]) return ans[i]>tmp[i];
26     return 0;
27 }
28 LL GCD(LL a,LL b)
29 {
30     return !b? a: GCD(b,a%b);
31 }
32 void DFS(LL fz,LL fm,LL now,LL cnt)
33 {
34     if(fz<0) return ;
35     if(fz==1&&fm>=now)
36     {
37         tmp[cnt]=fm;
38         if(if_change()||!flag)
39         {
40             for(int i=n; i>=1; --i)
41                 ans[i]=tmp[i];
42         }
43         flag=1;
44         return ;
45     }
46     if(cnt==1) return ;
47     for(LL gcd,i=max(now,get_first(fz,fm)); (fz*i)<=(fm*cnt); ++i)
48     {
49         tmp[cnt]=i;
50         gcd=GCD(fz*i-fm,fm*i);
51         DFS((fz*i-fm)/gcd,fm*i/gcd,i+1,cnt-1);
52     }
53 }
54 
55 int Persist()
56 {
57     freopen("egypt.in","r",stdin);
58     freopen("egypt.out","w",stdout);
59     
60     read(a),read(b);
61     ans[1]=1<<30;
62     for( n=1; !flag; ++n)
63         DFS(a,b,get_first(a,b),n);
64     for( ; --n; ) printf("%I64d ",ans[n]);
65     return 0;
66 }
67 
68 int Aptal=Persist();
69 int main(){;}
迭代加深+剪枝
 1 #include <cstdio>
 2 
 3 #define LL long long
 4 inline void read(LL &x)
 5 {
 6     x=0; register char ch=getchar();
 7     for(; ch>'9'||ch<'0'; ) ch=getchar();
 8     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
 9 }
10 
11 const int N(1e5+5);
12 LL a,b,n,tmp[N],ans[N];
13 bool flag;
14 
15 LL GCD(LL a,LL b)
16 {
17     return !b? a: GCD(b,a%b);
18 }
19 void DFS(LL fz,LL fm,LL now,LL cnt)
20 {
21     if(fz<0) return ;
22     if(cnt==1)
23     {
24         if(fz==1&&fm>=now)
25             if(fm<ans[1])
26             {
27                 flag=1;
28                 ans[1]=fm;
29                 for(int i=n; i>1; --i)
30                     ans[i]=tmp[i];
31             }
32         return ;
33     }
34     for(LL gcd,i=now; (fz*i)<=(fm*cnt); ++i)
35     {
36         tmp[cnt]=i;
37         gcd=GCD(fz*i-fm,fm*i);
38         DFS((fz*i/gcd-fm/gcd),fm*i/gcd,i+1,cnt-1);
39     }
40 }
41 
42 int Persist()
43 {
44     read(a),read(b);
45     ans[1]=1<<30;
46     for( n=1; ; ++n)
47     {
48         DFS(a,b,2,n);
49         if(flag) break;
50     }
51     for( ; n; n--) printf("%lld ",ans[n]);
52     return 0;
53 }
54 
55 int Aptal=Persist();
56 int main(){;}
CODEVS AC

T3走楼梯  （COGS 2752. [济南集训 2017] 数列运算）

(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

dp[i]表示到第i个数的答案

枚举前一个加号在j后面

那么到j一共有2^(j-1)种方案，每种方案在j后面都是一个加号，加号后面全是乘号

令tot=a[j+1]*a[j+2]……*a[i]

dp[i]=Σ（dp[j]+2^（j-1）*tot）（n^3）

优化——

预处理前缀积O（n^2）

省去上面循环计算tot的部分，预处理前缀积,

tot=pre[i]/pre[j]=pre[i]*pre[j]的逆元

预处理前缀积的逆元

优化——

处理前缀和（ o(n) ）

 1 #include <cstdio>
 2 
 3 const int mod(1000000007);
 4 const int N(1e6+5);
 5 #define LL long long
 6 inline void read(int &x)
 7 {
 8     x=0; register char ch=getchar();
 9     for(; ch>'9'||ch<'0'; ) ch=getchar();
10     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
11 }
12 
13 int a[N];
14 LL f[N],tow_mi[N],sum_mul[N],inv[N];
15 inline LL Quick_pow(LL a,LL b)
16 {
17     LL ret=1;
18     for(; b; b>>=1)
19     {
20         if(b&1) ret*=a,ret%=mod;
21         a*=a; a%=mod;
22     }
23     return ret;
24 }
25 
26 int Presist()
27 {
28     freopen("sequenceQBXT.in","r",stdin);
29     freopen("sequenceQBXT.out","w",stdout);
30     
31     int n;    read(n);
32     tow_mi[0]=sum_mul[0]=1;
33     for(int i=1; i<=n; ++i)
34     {
35         read(a[i]);
36         tow_mi[i]=(tow_mi[i-1]<<1)%mod;
37         sum_mul[i]=(sum_mul[i-1]*a[i])%mod;
38         inv[i]=Quick_pow(sum_mul[i],mod-2);
39     }
40     LL sum1=0,sum2=1;
41     for(int i=1; i<=n; ++i)
42     {
43         f[i]=(sum1+sum2*sum_mul[i]%mod)%mod;
44         sum1=(sum1+f[i])%mod;
45         sum2=(sum2+tow_mi[i-1]*inv[i]%mod)%mod;
46     }
47     printf("%lld",f[n]);
48     return 0;
49 }
50 
51 int Aptal=Presist();
52 int main(){;}
AC
——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Shy-key/p/7516303.html