[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

蓝桥杯第十届省赛软件类C++A组解题报告

Apare_xzc 2020/2/13

考生须知

A. 平方和（5分）

分析：

        这个题就是简单的模拟。只要循环一遍，判断每个数是否含有2019，然后平方相加即可。注意，答案大概在2019^3这个范围，要用long long或者__int64。
        判断2019的时候我们可以进行十进制的数位分解。如145这个数，个位是：145%10 = 5。十位是(145/10)%10 = 14%10=4。百位是：(145/100)%10 = 1%10 = 1。循环取模，每次x除以10，便可以得到从个位到最高位的值。

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
bool ok(int x)
{
    int y;
    while(x)
    {
        y = x%10;
        if(y==2||y==0||y==1||y==9) return true;
        x /= 10;
    }
    return false;
}
//2658417853
int main()
{
    LL sum = 0;
    for(int i=1;i<=2019;++i)
    {
        if(ok(i)) sum += 1ll*i*i;
    }
    cout<<sum<<endl;
    return 0; 
}

我觉得用python更好写

附赠一份python代码：

ans = 0
for x in range(1,2020):
    for c in str(x):
        if c in '2019':
            ans += x * x;break
print(ans)

答案为(右上角可复制)：

2658417853

B. 数列求值（5分）

分析：

        这也是个简单的模拟题，只要按题意模拟即可。但是存在两个要注意的地方：

  • 第一，这个数比斐波那契增长还迅速，我们要一边计算一边取模。由于题目只求后四位，所以我们可以对10000取模
  • 第二，20190324这个数比较大，我们没必要开这么大的数组，可能可用的内存也没这么大，每个数只和前面3个数有关，开4个整型变量足矣。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d;
    a = b = 1; c = 3; //初始化 
    for(int i=4;i<=20190324;++i)
    {
        d = (a+b+c)%10000;
        a = b; //相当于滚动数组 
        b = c;
        c = d;
    }
   // 6293
    cout<<d<<endl;
    return 0; 
}

附赠一份Python代码：

a,b,c = 1,1,1
for i in range(4,20190325):
    a,b,c = b,c,(a+b+c)%10000
print(c)

答案为：

4659

C. 最大降雨量（10分）

分析：

        这个题我们都不需要写代码，分析即可口算。
        我们把每周降雨量从小到大排列，再按每周的中位数从小到大排列，可以得到一个7*7的矩阵。
        这个矩阵我们很熟悉，他有一个很好的性质，就是在任意一行，从左到右递增；在任意一列从上到下递增。
        所以，矩阵中某个位置的元素，一定比它右方，下方，右下方的元素要小。我们可以看下面这个图：

我们可以看到，要求的这个中位数的中位数在矩阵的中心(4,4), 算上它自己，右边下边一共16个元素，最大的为49，最小的是我们要求的答案。49-16+1 = 34。
白色的数字是某一种合理的填法

答案为：

34

口算即可~

D. 迷宫

输入文本如下(右上角可复制)：

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

分析：

         首先我们要知道几行几列。我们可以手动数，但是太费眼睛了。

#include <bits/stdc++.h>
using namespace std;
char a[1000][1000];
int main()
{
  freopen("maze.txt","r",stdin);
  int row = 0;
  while(cin>>a[row])
  {
     ++row;
  }
  int col = strlen(a[0]);
  cout<<row<<"行"<<strlen(a[0])<<"列\n"; 
  for(int i=0;i<row;++i)
  cout<<a[i]<<'\n';
  return 0;
}

我们得到了，输入的迷宫矩阵为<mark>30行50列</mark>

    接下来，我们就可以开始正儿八经地BFS了。bfs的同时要注意两点：

  • 第一，要保证字典序，按照D,L,R,U的顺序入队
  • 第二，要记录路径，可以记录每个点的前驱节点到它的方向，逆推回去即可。

代码：

#include <bits/stdc++.h>
#define MP make_pair
using namespace std;
char a[32][52];
bool vis[32][52];
char s[] = "DLRU";
int dx[] = { 1, 0, 0,-1};
int dy[] = { 0,-1, 1, 0};
bool ok(int x,int y)
{
   return x>=0&&x<30&&y>=0&&y<50&&!vis[x][y]&&a[x][y]=='0'; 
} 
int r[32][52];
void bfs()
{
   memset(vis,false,sizeof(vis));
   queue<pair<int,int> > Q;
   Q.push(MP(0,0));
   vis[0][0] = true;
   int x,y,xx,yy;
   while(!Q.empty())
   {
   	x = Q.front().first, 
   	y = Q.front().second;
    	Q.pop();
   	for(int i=0;i<4;++i)
   	{
   	    xx = x+dx[i];
               yy = y+dy[i];
   	    if(ok(xx,yy)) 
   	   {
   	       vis[xx][yy] = true;
   	       Q.push(MP(xx,yy));
   	       r[xx][yy] = i;
   	   }
    }
   }
   stack<char> St;
   x = 29,y=49;
   while(1)
   {
   	St.push(s[r[x][y]]);
    	xx = x - dx[r[x][y]];
    	yy = y - dy[r[x][y]];
   	x = xx, y = yy;
           if(x==0&&y==0) break;
   } 
   while(!St.empty())
       putchar(St.top()),St.pop();
   puts("");
}
int main()
{
   freopen("maze.txt","r",stdin);
   int n = 0,m;
   for(int i=0;i<30;++i)
    cin>>a[i];
   bfs();
   return 0; 
}

路线图如下：

E. RSA解密（15分）

先上一篇去年写的专属题解：RSA解密 Apare_xzc <–

题目数据：

n = 1001733993063167141
d = 212353
c = 20190324

分析：

           之前那篇题解写得很详细了。我忘记去年怎么写的了，直接开始算。

  • 第一步，我们要对n分解质因数
    (n的数量级为10^18 次那么大，可能两个指数都是10^9左右):
    技术操作：先欧拉筛线性晒出1E7之内的素数，用这些素数去试除n,看看有没有好运气可以得到p,q 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+10;
#define LL long long
int cnt; //记录素数的个数 
int sushu[maxn/10]; //得到的素数表 
bool notPrime[maxn]; //记录是不是素数 
const LL n = 1001733993063167141ll;
void getPrime();
void fenjie(LL); 
int main()
{
 getPrime(); 
 //欧拉筛线性筛出1E7之内质数 
 fenjie(n); //分解质因数 
 return 0; 
} 
void getPrime() //欧拉线筛 
{
 int n = maxn-2;
 cnt = 0;
 for(int i=2;i<=n;++i)
 {
  if(!notPrime[i]) sushu[cnt++] = i;
  for(int j=0;j<cnt&&1ll*i*sushu[j]<=n;++j)
  {
   notPrime[i*sushu[j]] = true;
   if(i%sushu[j]==0) break;  
  }
 } 
}
void fenjie(LL x) //分解质因数 
{
 cout<<x<<" = 1";
 for(int i=0;i<cnt&&sushu[i]<=x/sushu[i];++i)
 {
  if(x%sushu[i]) continue;
  while(x%sushu[i]==0)
  {
   x/=sushu[i];
   cout<<" * "<<sushu[i];
  } 
 } 
 if(x!=1) cout<<" * "<<x;
 cout<<endl;
}


很遗憾，没有得到p,q,看来p和q都大于10,000,000
我们暴力分解吧

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e7+10;
const LL n = 1001733993063167141ll;
int main()
{
// getPrime();
// fenjie(n);
 cout<<"1001733993063167141 = 1";
 LL x = n;
 for(LL i=1e7+1;i<=x/i;i+=2)
 {
  while(x%i==0)
   x/=i,cout<<" * "<<i;
 }
 if(x>1) cout<<" * "<<x;
 cout<<endl;
    //1001733993063167141 = 891234941 * 1123984201
 return 0;
}

我们得到了分解质因数的结果：
1001733993063167141 = 891234941 * 1123984201
p = 891234941
q = 1123984201
我们令m = (p-1) * (q-1) = 1001733991047948000
根据欧拉函数的性质，我们可知m就是n的欧拉函数
接下来我们求d关于m的乘法逆元e，即 e * d % m = 1

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL n = 1001733993063167141ll;
void exgcd(LL a,LL b,LL &d,LL&x,LL&y)
{
 if(b==0){d = a; x = 1; y = 0;return;} 
 exgcd(b,a%b,d,y,x);
 y -= (a/b)*x;
}  
LL getNi(LL a,LL b)
{
 LL x,y,d;
 exgcd(a,b,d,x,y);
 return (x%b+b)%b;
}
int main()
{
 LL d = 212353;
 LL m = 1001733991047948000ll; 
 LL e = getNi(d,m);
 cout<<"e = "<<e<<endl;
// cout<<d<<" * "<<e<<" % "<<m<<" = "<<fast_add(e,d,m)<<endl;
 return 0; 
}

如果你不相信拓展欧几里得算法求乘法逆元的话，我们可以验证一下。


恐怕会令你诧异，为什么e*d%m 不是1呢？因为：溢出了(乘爆long long了)
这个时候，我们就要用到<mark>快速乘</mark>(也叫俄罗斯农民乘法)，和快速幂原理相同。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL n = 1001733993063167141ll;
void exgcd(LL a,LL b,LL &d,LL&x,LL&y)
{
 if(b==0){d = a; x = 1; y = 0;return;} 
 exgcd(b,a%b,d,y,x);
 y -= (a/b)*x;
}  
LL getNi(LL a,LL b)
{
 LL x,y,d;
 exgcd(a,b,d,x,y);
 return (x%b+b)%b;
}
LL fast_add(LL a,LL b,LL mod)
{
 if(a==0||b==0) return 0;
 if(a<b) swap(a,b);
 LL ans = 0;
 while(b)
 {
  if(b&1) ans = (ans+a)%mod;
  a = (a<<1)%mod;
  b>>=1; 
 } 
 return ans;
} 
int main()
{
    LL d = 212353,m = 1001733991047948000ll; 
    LL e = getNi(d,m);
    cout<<"e = "<<e<<endl;
    cout<<d<<" * "<<e<<" % "<<m<<" = "<<fast_add(e,d,m)<<endl;
    
    return 0;
}


通过快乘，我们验证了之前求的逆元e是正确的。e = 823816093931522017

           接下来，我们只需要求C^e % n即可，就是求：20190324^823816093931522017 % 1001733993063167141

  • 由于e很大，我们想到了费马小定理，我们上文中提到，n的欧拉函数Fai(n) = m, 我们可以先令指数e对m取模，减少计算量。但是，我们求逆元的过程已经对m取模了。所以这道题，出题人不考费马小定理，不知道这个定理也没关系。
  • 然后就是个快速幂
    但是，这个快速幂还要注意，这个模数太大，依旧会爆long long，还要用快乘。 
//快乘：
#define LL long long
LL fast_Mul(LL a,LL b,LL mod)
{
	if(b==0||a==0) return 0;
 	if(a<b) swap(a,b);
	LL sum = 0;
	while(b)
	{
		if(b&1) sum = (sum+a)%mod;
		a = (a<<1)%mod;
		b>>=1;
	}
	return sum;
}

计算答案：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const 	LL n = 1001733993063167141ll;
LL fast_Mul(LL a,LL b,LL mod)
{
	if(b==0||a==0) return 0;
 	if(a<b) swap(a,b);
	LL sum = 0;
	while(b)
	{
		if(b&1) sum = (sum+a)%mod;
		a = (a<<1)%mod;
		b>>=1;
	}
	return sum;
}
LL fast_pow(LL a,LL b,LL mod)
{
	if(a==0) return 0;
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = fast_Mul(ans,a,mod);
		a = fast_Mul(a,a,mod);
		b>>=1;
	}
	return ans;
} 
int main()
{
	LL c = 20190324, e = 823816093931522017ll;
	cout<<"密文c为："<<c<<endl;
	LL X = fast_pow(c,e,n);
	cout<<"原文为X：c^e = "<<c<<"^"<<e<<" % "<<n<<" = "<<X<<endl; 
// 答案为：579706994112328949
	return 0;	
}


完整代码：

///Author: xzc
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e8+10;
const LL n = 1001733993063167141ll;
const LL p = 891234941ll;
const LL q = 1123984201ll;
const LL d = 212353;
const LL c = 20190324;
int a[maxn];
int sushu[maxn/10];
bool notPrime[maxn]; ///筛素数分解不出来，目测是9位数*10位数 
int cnt;
void getPrime(int n)
{
   for(int i=2;i<=n;++i)
   {
   	if(!notPrime[i]) sushu[cnt++] = i;
   	for(int j=0;j<cnt&&1ll*i*sushu[j]<=n;++j)
   	{
   		notPrime[i*sushu[j]] = true;
   		if(i%sushu[j]==0) break; 
   	} 
   }
   for(int i=0;i<20;++i) cout<<sushu[i]<<" ";cout<<endl;
}
void fenjie(LL x)
{
   cout<<x<<" = 1";
   for(int i=0;i<cnt&&sushu[i]<=x/sushu[i];++i)
   {
   	while(x%sushu[i]==0)
   	{
   		cout<<" * "<<sushu[i];
   		x /= sushu[i];
   	}
   }
   if(x>1) cout<<" * "<<x;
   cout<<endl;
}
void BF(LL x)
{
   cout<<x<<" = "; 
   for(LL i=1e8+1;i<x;i+=2)
   {
   	if(x%i==0)
   		cout<<i<<" * ",x/=i;
   }
   cout<<x<<endl;
}
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
   if(b==0)
   {
   	d = a; x = 1; y = 0; return;
   }
   exgcd(b,a%b,d,y,x);
   y -= (a/b)*x;
}
LL rev(LL t,LL m)
{
   LL d,x,y;
   exgcd(t,m,d,x,y);
   return (x%m+m)%m;
}
LL fast_product(LL a,LL b,LL mod)
{
   LL ans = 0;
   while(b)
   {
   	if(b&1) ans = (ans+a)%mod;
   	a = (a+a)%mod;
   	b>>=1;
   }
   return ans;
} 
LL fast_pow(LL a,LL b,LL mod)
{
   LL ans = 1;
   while(b)
   {
   	if(b&1) ans = fast_product(ans,a,mod);
   	a = fast_product(a,a,mod);
   	b>>=1;		
   } 
   return ans;
}
int main()
{
   //getPrime(maxn-5);
   //fenjie(n);
   BF(n);
   LL y = (p-1)*(q-1);
   LL e = rev(d,y);
   LL answer = fast_pow(c,e,n);
   cout<<answer<<endl;

   return 0;
}

所以，E题的答案为： 579706994112328949

F. 完全二叉树的权值（15分）


分析：

        我们只要计算出每层的和，然后更新答案即可。完全二叉树每一层的最后一个节点的序号为：2^i -1。见代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
	int n,x;
	cin>>n;
	int deep = 1;
	map<int,int> mp;
	for(int i=1;i<=30;++i)
	{
		mp[(1<<i)-1] = i;
	} 
	LL sum = 0;
	LL MaxSum = -100000000000000000ll;
	int ans;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&x);
		sum += x;
		if(mp.count(i)) //到达mp[i]这层的末尾 
		{
			if(sum>MaxSum) MaxSum = sum,ans = mp[i]; 
			sum = 0;	
		}
	} 
	cout<<ans<<endl;
	return 0;	
}

虽然只是过样例，还是挂个图

G. 外卖店优先级（20分）

分析：

        如果从时间的维度上，按秒更新或者按点单的节点对所有商店优先级更新，时间复杂度是N^2的，不明智。我们可以从商店的角度来看。
        先把所有操作按时间排序，然后对于每个商店的订单，可以维护一个列表。同时计算出这些商店最后优先级的值。
        如果大于5，一定在队列中，如果小于3，一定不在队列中，如果在中间，就要判断一下。
        我们从后往前推。发现这个列表用栈维护比较好。
        又发现，对于某个商店来说，时刻T在不在队列只和最后一个订单的时间有关。

  • 如果最后一个订单的时刻优先级为v[i[, 时间为last, 那么到第T秒，下降了 T-last[i]个，T时刻的优先级即为 v[i] - (T-last)
  • 如果大于3 小于等于5，那么我们要知道它之前的状态，在不在队列中。如果之前在队列中，说明虽然在下降，但是没有被踢出队列。只需要维护一个in数组即可。
  • 具体见代码： 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int Last[maxn];
int val[maxn];
bool in[maxn];
int main()
{
	int n,m,T;
	vector<pair<int,int> > vii;
	int pt,id;
	scanf("%d%d%d",&n,&m,&T);
	while(m--)
	{
		scanf("%d%d",&pt,&id);
		vii.push_back(make_pair(pt,id));	
	} 
	sort(vii.begin(),vii.end());
	for(auto x:vii) 
	{
		id = x.second;
		pt = x.first;
		if(Last[id])
		{
			val[id] = max(0,val[id]-(pt-Last[id])+1);
		}
		val[id] += 2;
		if(val[id]>5) in[id] = true;
		Last[id] = pt;
	}
	int cnt = 0;
	for(int i=1;i<=n;++i)
	{
		if(!Last[i]||!in[i]) continue;
		val[i] -= (T-Last[i]);
		if(val[i]>3) ++cnt;
	}
	printf("%d\n",cnt);
		
}

样例是一定过了

H. 修改数组（20分）

分析：

        这个题，题意很简单，暴力大家都会，复杂度n^2, 根据给的数据范围看，暴力可以拿80分。
        但是如果想拿全分，就要好好思考一番。
        暴力模拟的问题在于每次不知道改往哪里放，试错的次数太多。我们如果可以维护之前出现的所有值之中某个值x后面最后一个不连续的数即可。比如之前出现过2,3,4,5,8,9, a[7]为2， 我们查询，2之后连续出现了2.3.4.5，查到了最后一个不连续的是6。于是a[7] 就是6.

  • 思路一：用线段树维护。线段树。插入后，如果a[i]+1也出现过，那么与后面合并，如果a[i]-1出现过，与前面合并，如果都出现过，正好合并前中后。
  • 思路二：我们线段树查询和更新的复杂度都是logn, 而且要维护的是一个值，这个值代表了出现过的连续的一串数字的最大值。相当于集合的代表。那么，我们自然而然可以想到并查集。
    并查集我们不妨把连续的这串数最小的当代表，最大的当作集合的权值。这就是一个非常简单的，维护最大值的带权并查集。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1100000+100;
int a[maxn]; //每个数在数组中连续的长度
int b[maxn]; 
//void insert(int x,int left,int right ) 
int father[maxn]; //并查集的代表元素 
int last[maxn]; //每个集合中值最大的元素 
bool vis[maxn]; //vis[i]表示i是否在之前的数列中出现过 
void initUFset(int n) //初始化并查集 
{
	for(int i=0;i<=n;++i)
		father[i] = i,last[i]=i; 
}
int getFa(int x)
{
	if(x==father[x]) return x;
	int y = father[x];
	int grandfa = getFa(father[x]); //爷爷 
	last[grandfa] = max(last[y],last[x]);
	return father[x] = grandfa;
}
void join(int x,int y)
{
	int fx = getFa(x), fy = getFa(y);
	if(fx==fy) return;
	father[fy] = fx;
	last[fx] = max(last[fx],last[fy]);
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
	int n,x,fx,Max=-1000000;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]),Max = max(Max,a[i]);
	initUFset(Max+n);
	for(int i=1;i<=n;++i)
	{
		x = a[i];
		if(vis[x]) x = last[getFa(x)]+1;
		a[i] = x;
		vis[a[i]] = true;
		if(vis[x+1]) join(x,x+1); 
		if(vis[x-1]) join(x-1,x);
	} 
	printf("%d",a[1]);
	for(int i=2;i<=n;++i)
		printf(" %d",a[i]);
	puts("");
	return 0;	
}

I. 糖果（25分）

去年写的题解：糖果题 状压dp Apare_xzc

分析：

        最暴力的方法，就是枚举出2^n种情况。每件物品，选的话为1，不选的话为0。我们可以dfs出2^n个零一串，每个串代表一个方案。然后用set之类的判断有没有m中，可以水一些分。但是这不是正解。正解是二进制状态压缩DP。dp[i]表示要达到i的二进制这种状态需要的最少袋数。这次我用了滚动数组，开的是char型，节省内存。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[101];
char dp[2][1<<20];
int getKind(int y)
{
	int ans = 0;
	while(y)
	{
		if(y&1) ++ans;
		y>>=1;
	}
	return ans;
}
int main()
{
// freopen("in.txt","r",stdin);
	int m,n,k,x,b;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;++i)
	{
		x = 0;
		for(int j=1;j<=k;++j)
			scanf("%d",&b),x|=(1<<(b-1));
		a[i] = x;			
	} 
	int N = 1<<m, y;
	for(int i=0;i<2;++i)
	{
		for(int j=0;j<N;++j)
			dp[i][j] = n+1;
	}
	dp[0][0] = dp[1][0] = 0; //初始化 
	for(int i=1;i<=n;++i)
	{ 
		for(int j=0;j<N;++j)
		{
			if(dp[0][j]==n+1) continue;
			y = j|a[i];
			dp[1][y] = min((int)dp[1][y],dp[0][j]+1);	
		}  
		for(int j=0;j<N;++j) dp[0][j] = dp[1][j]; //滚动数组 
	}
	int ans = dp[1][N-1];
	if(ans==n+1) ans = -1;
	printf("%d\n",ans);
	
	return 0;	
}

J. 组合数问题（25分）

分析：

        求组合数%k==0的个数。组合数2000之内的可以n^2递推。因为：C[x][y] = C[x-1][y-1]+C[x-1][y] 然后，我们维护矩阵的二维前缀和就可以O(1)查询了。这样就可以拿到40分。后面大的数据暂时没什么好办法。希望有高人不啬赐教，欢迎在评论区留言。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2001;
int a[maxn][maxn],k,mod=1000000007;
int b[maxn][maxn];
int main()
{
	int m,n,t;
	scanf("%d%d",&t,&k);
	a[0][0] = 1;
	for(int i=1;i<=2000;++i)
	{
		a[i][0] = a[i][i] = 1;
		for(int j=1;j<i;++j) a[i][j]= (a[i-1][j-1]+a[i-1][j])%k;
	}
	for(int i=1;i<=2000;++i)
	{
		for(int j=1;j<=i;++j)
			b[i][j] = b[i][j-1]+((a[i][j]==0)?1:0);
		for(int j=i+1;j<=2000;++j)
			b[i][j] = b[i][j-1];
	}
	for(int j=1;j<=2000;++j)
	{
		for(int i=2;i<=2000;++i)
			b[i][j] += b[i-1][j]; //二维前缀和 
	}
	while(t--)
	{
		scanf("%d%d",&n,&m);
		if(n<=2000&&m<=2000) 
		{
			printf("%d\n",b[n][m]);	
		} 
		else //不会 
		{
			printf("1000000\n"); ///大数先不算了 
 		}
	}
	return 0;	
}

写给读者的话：工程量巨大，写的匆匆忙忙，但真的是在用心写。如果有错误和纰漏，欢迎大家在评论区指正。
作者：xzc
QQ : 1363581749 （快乐的xzc）
2020/2/13 20:36

全部评论

相关推荐

11-21 14:45
CVTE_运营管理_HR
拿完offer再挑
目前池子里已经有很多同学泡着了，各个学校的三方也已经陆续开放，但是并不代表着签完三方就结束了，很多同学还会有违约考虑国企央企，所以10月到11月之间对于大部分同学来讲，还是没办法完全放松（已经拿到满意的offer的另说）&nbsp;，还没有投的同学最后都投上吧，春招hc都不一定有秋招中期的剩下的hc多，直入主题，大家都关注的问题cvte加不加班？加还是加的，但是看部门，软硬件基本都是8点钟走其他的一些文职部门我看下班还是六点准时的而且不是强制，你事情做完可以走的，全天不打卡工资待遇怎么样？待遇还是挺不错，校招普遍都是10k以上，目前我见过最高的是18k的。福利待遇有哪些？五险一金啥的不用说了。住房公积...
CVTE公司福利 265人发布
点赞 评论 收藏
分享
11-20 00:09
山西大学 OTA系统工程师
点赞 评论 收藏
分享
11-18 09:44
Java
是项目太简单了吗，投了半个月日常实习，啥也没有😭我是需要去再整个微服务项目吗
小白也想要offer：简历别放洋屁，搞不还还放错了，当然你投外企除外，以上纯属个人观点
点赞 评论 收藏
分享
11-20 14:06
英伟达_算法工程师
英伟达深度学习算法实习生招聘 （CVCG方向）
我们是Nvidia&nbsp;ML&amp;AI&nbsp;specialist&nbsp;team,&nbsp;主要方向是深度学习和AI领域的各类算法（ASR,NLP,CV&amp;CG…）&nbsp;目前团队正在招收CV&amp;CG方向的实习生，以下是岗位的具体要求：&nbsp;面向人群：&nbsp;全日制在校生,&nbsp;博士优先，实习时间6个月以上者优先。&nbsp;工作内容：&nbsp;1.&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;负责计算机视觉前沿研究与技术创新，技术包括但不限于视频模型，扩散模型，3D高斯，3D重建，神经渲染等方向。&nbsp;2.&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;方向一&nbsp;视频生成模型（AIGV）于自动驾驶/人形机器人领域的研究和应用&nbsp;；&nbsp;方向二&nbsp;3D高斯，NeRF...
投递英伟达等公司10个岗位 >
点赞 评论 收藏
分享
点赞 1 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
347086次浏览 3365人参与
# 我的实习求职记录 #
6081554次浏览 83645人参与
# 百度开奖 #
197019次浏览 1314人参与
# 地方国企笔面经互助 #
5036次浏览 13人参与
# 职场吐槽大会 #
90148次浏览 744人参与
# 选完offer后，你后悔学本专业吗 #
22778次浏览 164人参与
# 阿里云管培生offer #
40860次浏览 926人参与
# ai智能作图 #
2021次浏览 47人参与
# 运营商笔面经互助 #
92318次浏览 1331人参与
# 实习中的菜狗时刻 #
278497次浏览 2737人参与
# 如果有时光机，你最想去到哪个年纪？ #
24063次浏览 489人参与
# 风评不好的公司，你会去吗？ #
20628次浏览 94人参与
# 国企还是互联网，你怎么选？ #
89990次浏览 699人参与
# 软件开发2024笔面经 #
2324935次浏览 48213人参与
# 如何一边实习一边秋招 #
999406次浏览 12695人参与
# 远程面试的尴尬瞬间 #
20297次浏览 293人参与
# 银行笔面经互助 #
84570次浏览 893人参与
# 腾讯求职进展汇总 #
198035次浏览 1650人参与
# 第一份工作应该选择高薪还是大平台 #
88871次浏览 590人参与
# bilibili求职进展汇总 #
33869次浏览 361人参与
# 阿里求职进展汇总 #
70699次浏览 757人参与
# 上班苦还是上学苦呢？ #
80108次浏览 767人参与
牛客网
牛客企业服务