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 <iostream>
#include <bits/stdc++.h>
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<y)
        swap(x,y);
    return w[x]*p(w[x-y]*w[y]%N,N-2)%N;
}
int main()
{
    register ll a,b;
    cin>>a>>b;
    ll y=2*a-b;
    ll x=2*b-a;
    if(x%3!=0||y%3!=0||x<0||y<0)
    {
        printf("0\n");
        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<<w3<<endl;
    return 0;
}

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 <iostream>
#include <bits/stdc++.h>
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<y)
        swap(x,y);
    return w[x]*p(w[x-y]*w[y]%N,N-2)%N;
}
int main()
{
    register ll n,k;
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%lld",&num[i]);
    sort(num,num+n);
    w[0]=1;
    for(ll i=1;i<=2000500;i++)
        w[i]=(w[i-1]*i)%N;
    ll sum=0;
    for(ll i=0;i<n-k+1;i++)
    {
        sum=(sum+(num[n-i-1]-num[i])%N*c1(n-i-1,k-1)%N)%N;
    }
    printf("%lld\n",(sum%N+N)%N);
    return 0;
}