2020-08-10
http://icpc.upc.edu.cn/problem.php?id=14581
题目
14581: Knight
题目描述
There is a knight – the chess piece – at the origin (0,0) of a two-dimensional grid.
When the knight is at the square (i,j), it can be moved to either (i+1,j+2) or (i+2,j+1).
In how many ways can the knight reach the square (X,Y)?
Find the number of ways modulo 109+7.
Constraints
·1≤X≤106
·1≤Y≤106
·All values in input are integers.
输入
Input is given from Standard Input in the following format:
X Y
输出
Print the number of ways for the knight to reach (X,Y) from (0,0), modulo 109+7.
样例输入
【样例1】
3 3
【样例2】
2 2
【样例3】
999999 999999
样例输出
【样例1】
2
【样例2】
0
【样例3】
151840682
提示
样例1解释
There are two ways: (0,0)→(1,2)→(3,3) and (0,0)→(2,1)→(3,3).
样例2解释
The knight cannot reach (2,2).
样例3解释
Print the number of ways modulo 109+7.
逆元求组合数
#include
#include
using namespace std;
typedef long long ll;
const int N=1e9+7;
long long int w[2005500]={0};
long long int p(long long x,long long y)
{
long long int sum1=1;
while(y)
{
if (y&1)
sum1=(sum1*x)%N;
y>>=1;
x=(x*x)%N;
}
return sum1%N;
}
long long int c1(long long int x,long long int y)
{
if(x>a>>b;
ll y=2*a-b;
ll x=2*b-a;
if(x%3!=0||y%3!=0||x<0||y<0)
{
printf("0n");
return 0;
}
x=x/3;
y=y/3;
ll w2=x+y;
w[0]=1;
for(ll i=1;i<=2000500;i++)
w[i]=(w[i-1]*i)%N;
ll w3=(c1(x,w2)+N)%N;//防止负数出现，取余时注意
cout< http://icpc.upc.edu.cn/problem.php?id=14625
题目
14625: Max-Min Sums
题目描述
For a finite set of integers X, let f(X)=maxX−minX.
Given are N integers A1,…,AN.
We will choose K of them and let S be the set of the integers chosen. If we distinguish elements with different indices even when their values are the same, there are NCK ways to make this choice. Find the sum of f(S) over all those ways.
Since the answer can be enormous, print it mod(109+7).
Constraints
·1≤N≤105
·1≤K≤N
·|Ai|≤109
输入
Input is given from Standard Input in the following format:
N K
A1 … AN
输出
Print the answer mod(109+7).
样例输入
【样例1】
4 2
1 1 3 4
【样例2】
6 3
10 10 10 -10 -10 -10
【样例3】
3 1
1 1 1
【样例4】
10 6
1000000000 1000000000 1000000000 1000000000 1000000000 0 0 0 0 0
样例输出
【样例1】
11
【样例2】
360
【样例3】
0
【样例4】
999998537
提示
样例1解释
There are six ways to choose S: {1,1},{1,3},{1,4},{1,3},{1,4},{3,4} (we distinguish the two
1s). The value of f(S) for these choices are 0,2,3,2,3,1, respectively, for the total of 11.
样例2解释
There are 20 ways to choose S. In 18 of them, f(S)=20, and in 2 of them, f(S)=0.
样例4解释
Print the sum mod(109+7).
统计最大值出现的次数和最小值出现的次数，最后求和。
#include
#include
using namespace std;
typedef long long ll;
const int N=1e9+7;
long long int w[2005500]={0};
ll num[100500]={0};
long long int p(long long x,long long y)
{
long long int sum1=1;
while(y)
{
if (y&1)
sum1=(sum1*x)%N;
y>>=1;
x=(x*x)%N;
}
return sum1%N;
}
long long int c1(long long int x,long long int y)
{
if(x 