数论集训

墨蓝 2024-02-18 22:22 46阅读 0赞

我们知道，在编程中，我们时常需要考虑到时间复杂度，特别是对于循环的部分。例如，  
如果代码中出现  
for(i=1;i<=n;i++) OP ;  
那么做了n次OP运算，如果代码中出现  
fori=1;i<=n; i++)  
for(j=i+1;j<=n; j++) OP;  
那么做了n\*(n-1)/2 次OP 操作。  
现在给你已知有m层for循环操作，且每次for中变量的起始值是上一个变量的起始值＋1（第一个变量的起始值是1），终止值都是一个输入的n，问最后OP有总共多少计算量。

Input

有T组case，T<=10000。每个case有两个整数m和n，0<m<=2000，0<n<=2000.

Output

对于每个case，输出一个值，表示总的计算量，也许这个数字很大，那么你只需要输出除1007留下的余数即可。

Sample Input

2
    1 3
    2 3

Sample Output

3
    3

没想到是组合数求模，害我想了半天。

n为终止条件，m为循环层数，就相当于从n里面取出m个数。

\#include<iostream>  
\#include<algorithm>  
\#include<string.h>  
\#define LL long long  
\#define mod 1007  
using namespace std;  
int a\[2003\]\[2003\];  
void ki()  
\{  
for(int i=0;i<2001;i++)  
\{  
a\[0\]\[i\]=0;  
a\[i\]\[0\]=1;  
  
\}  
for(int i=1;i<2001;i++)  
for(int j=1;j<2001;j++)  
a\[i\]\[j\]=(a\[i-1\]\[j\]+a\[i-1\]\[j-1\])%mod;  
\}  
int main()  
\{  
int n,i,j,k;  
LL m,t;  
ki();

cin>>n;  
while(n--)  
\{  
cin>>m>>t;  
printf("%d\\n",a\[t\]\[m\]);  
\}  
return 0;  
\}

打表算的组合数

有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第$n$行第$m$列的格子有几种方案，答案对$1000000007$取模。

![6be27c7c8f0609e142553195f49b804c_v_1533173013][]

Input

多组测试数据。  
  
两个整数$n,m(2\\leq n,m\\leq 100000)$

Output

一个整数表示答案

Sample Input

4 5

Sample Output

\#include<iostream>  
\#include<string.h>  
\#define LL long long  
\#define mod 1000000007  
using namespace std;  
LL a\[200005\]=\{1,1\};  
void kk()  
\{  
for(int i=2;i<200005;i++)  
\{  
a\[i\]=a\[i-1\]\*i%mod;  
  
\}  
  
\}  
LL quick\_mod(LL n,LL k)  
\{  
LL sum=1;  
n=n%mod;  
while(k!=0)  
\{  
if(k&1)  
sum=sum\*n%mod;  
n=n\*n%mod;  
k>>=1;  
\}  
return sum;  
\}  
LL D(LL n,LL k)  
\{  
if(n<k)  
return 0;  
else  
return a\[n\]\*(quick\_mod(a\[n-k\]\*a\[k\]%mod,mod-2))%mod;  
\}  
LL Lucas(LL n,LL k)  
\{  
if(k==0)  
return 1;  
else  
return D(n%mod,k%mod)\*Lucas(n/mod,k/mod)%mod;  
\}  
int main()  
\{  
int n,i,j;  
LL m,t;  
kk();  
  
while(cin>>n>>m)  
\{  
;  
printf("%lld\\n",Lucas(n+m-4,n-2));  
\}  
return 0;  
\}

任何正整数都能分解成2的幂，给定整数N，求N的此类划分方法的数量！由于方案数量较大，输出Mod 1000000007的结果。  
比如N = 7时，共有6种划分方法。  
  
7=1+1+1+1+1+1+1  
=1+1+1+1+1+2  
=1+1+1+2+2  
=1+2+2+2  
=1+1+1+4  
=1+2+4

Input

输入一个数N（1 <= N <= 10^6)

Output

输出划分方法的数量Mod 1000000007

Sample Input

Sample Output

规律题，找好前十个，一定要找好，细心，不能错，

\#include<iostream>  
\#include<string.h>

\#define LL long long  
using namespace std;  
int a\[1000005\]=\{1,1\};  
int M=1e9+7;  
void kt()  
\{  
for(int i=2;i<1000001;i++)  
\{  
if(i%2==0)  
a\[i\]=(a\[i-1\]+a\[i/2\])%M;  
else  
a\[i\]=(a\[i-1\])%M;  
\}  
\}  
int main()  
\{  
kt();  
int n;  
while(~scanf("%d",&n))  
\{  
cout<<a\[n\]<<endl;  
\}  
return 0;  
\}

如果数组满足以下三个条件，则这个数组是有趣的：

*  它刚开始是严格递增的
 *  之后是不变的
 *  再之后它是严格递减的

但除了第二个条件，其他两个条件（递增和递减）不存在的数组也可以是有趣的。

例如，以下三个数组是有趣的： \[5, 7, 11, 11, 2, 1\], \[4, 4, 2\], \[7\], 但以下三个却不是有趣的: \[5, 5, 6, 6, 1\], \[1, 2, 1, 2\], \[4, 5, 5, 6\].

请您编写一个程序判断一个数组是否有趣

Input

第一行是一个整数 *n* (1 ≤ *n* ≤ 100) —数组内元素的个数

第二行包括*n* 个整数 *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 1 000) — 数组的元素

Output

如果这个数组是有趣的，请输出"YES" 否则请输出 "NO".

Examples

输入

6
    1 5 5 5 4 2

输出

YES

输入

5
    10 20 30 20 10

输出

YES

输入

4
    1 2 1 2

输出

输入

7
    3 3 3 3 3 3 3

输出

YES

这题，先搞懂题意，1.先升后平再降，2.一直平，括号里的这句话就是这个意思，（但除了第二个条件，其他两个条件（递增和递减）不存在的数组也可以是有趣的。）3.或者是先平，后降；先升后平

\#include<iostream>  
using namespace std;  
int a\[1050\];  
int main()  
\{  
int n,i,j,t;  
cin>>n;  
for(i=0;i<n;i++)  
cin>>a\[i\];  
i=1;  
for(;i<n;)  
\{  
if(a\[i\]>a\[i-1\])  
i++;  
else  
break;  
\}  
for(;i<n;)  
\{  
if(a\[i\]==a\[i-1\])  
i++;  
else  
break;  
\}  
for(;i<n;)  
\{  
if(a\[i\]>a\[i-1\])  
i++;  
else  
break;  
\}  
if(i==n)  
cout<<"YES"<<endl;  
else  
cout<<"NO"<<endl;  
return 0;  
\}

[6be27c7c8f0609e142553195f49b804c_v_1533173013]: https://odzkskevi.qnssl.com/6be27c7c8f0609e142553195f49b804c?v=1533173013