Atcoder D - Knight（规律 +组合数）

78 阅读 0 评论 52 点赞

我是靠谱客的博主外向煎蛋，最近开发中收集的这篇文章主要介绍Atcoder D - Knight（规律 +组合数），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

题意：有一个网格，你只能从（0,0）开始，然后每次只能走到（i +1,j + 2）或者（i + 2,j + 1）。问你从（0,0）走到（x,y）有多少方案数。

思路：找规律，发现可以分层次，（0,0）是第0层，（1,2），（2,1）是第1层，（2,4），（3,3），（4,2）是第2层，（3,6），（4,5），（5,4），（6，3）是第3层。然后对于每一层你可以找出他们的方案数。

1 1

1 2 1

1 3 3 1

1 4 6 4 1

................

这个就是杨辉三角啊。又可以发现，对于每个坐标（x,y），如果这个坐标可以到达的话，（x + y）/ 3 就是他们的层数，所以，你只需要找出这个坐标是第几层的第几个（参看上面的三角形）。然后用组合数计算就可以了。

AC Code：

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<cstdio>
#include<sstream>
#include<vector>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define read(x) scanf("%d",&x)
#define Read(x,y) scanf("%d%d",&x,&y)
#define gc(x)  scanf(" %c",&x);
#define mmt(x,y)  memset(x,y,sizeof x)
#define write(x) printf("%dn",x)
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define ll long long
#define mod (ll)(1e9 + 7)
const int N = 1e6 + 5;
const int M = 1e6 + 5;
ll mulit(ll a,ll b,ll m)
{
    ll ans=0;
    while(b)
    {
        if(b&1)
            ans=(ans+a)%m;
        a=(a<<1)%m;
        b>>=1;
    }
    return ans;
}
ll quick_mod(ll a,ll b,ll m)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=mulit(ans,a,m);
        a=mulit(a,a,m);
        b>>=1;
    }
    return ans;
}
ll comp(ll a,ll b,ll m)
{
    if(a<b)
        return 0;
    if(a==b)
        return 1;
    if(b>a-b)
        b=a-b;
    ll ans=1,ca=1,cb=1;
    for(int i=0; i<b; i++)
    {
        ca=ca*(a-i)%m;
        cb=cb*(b-i)%m;
    }
    ans=ca*quick_mod(cb,m-2,m)%m;
    return ans;
}
ll lucas(ll a,ll b,ll m)
{
    ll ans=1;
    while(a&&b)
    {
        ans=(ans*comp(a%m,b%m,m))%m;
        a/=m;
        b/=m;
    }
    return ans;
}
int main()
{
    ll x,y;
    cin>>x>>y;
    if((x + y)%3!=0) return cout<<0,0;
    ll num = (x + y) /3;
    if(x <= 2*num&&x >= num&&y <= 2*num&&y >= num) {}
    else return cout<<0,0;
    ll a = num,b = 2*num;
    ll sum = 0;
    while(a != x&&b != y){
         a ++;b --;
         sum ++;
    }
    if(sum == 0 || sum == num) cout<<1;
    else cout<<lucas(num,sum,mod);

}

正解
每一步是（+1，+2），（+2，+1）。所以最后的X + Y 肯定是 3 的倍数。

我们设（+1，+2）走了 n 步，（+2，+1）走了 m步。

然后根据题意列个方程

n + 2*m = X

2 * n + m = Y

解出n，m值。若最后n,m出现负值，则肯定无解。

否则我们只需要求 $C_{n + m}^{n}$ 就可以了。

AC Code：

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#include<cstdio>
#include<sstream>
#include<vector>
#include<bitset>
#include<algorithm>

using namespace std;
#define read(x) scanf("%d",&x)
#define Read(x,y) scanf("%d%d",&x,&y)
#define gc(x)  scanf(" %c",&x);
#define mmt(x,y)  memset(x,y,sizeof x)
#define write(x) printf("%dn",x)
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define ll long long
const ll mod =   1000000007;
const int N = 100000 + 100;
const int M = 3e6 + 1005;
ll mulit(ll a,ll b,ll m)
{
    ll ans=0;
    while(b)
    {
        if(b&1)
            ans=(ans+a)%m;
        a=(a<<1)%m;
        b>>=1;
    }
    return ans;
}
ll quick_mod(ll a,ll b,ll m)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=mulit(ans,a,m);
        a=mulit(a,a,m);
        b>>=1;
    }
    return ans;
}
ll comp(ll a,ll b,ll m)
{
    if(a<b)
        return 0;
    if(a==b)
        return 1;
    if(b>a-b)
        b=a-b;
    ll ans=1,ca=1,cb=1;
    for(int i=0; i<b; i++)
    {
        ca=ca*(a-i)%m;
        cb=cb*(b-i)%m;
    }
    ans=ca*quick_mod(cb,m-2,m)%m;
    return ans;
}
ll lucas(ll a,ll b,ll m)
{
    ll ans=1;
    while(a&&b)
    {
        ans=(ans*comp(a%m,b%m,m))%m;
        a/=m;
        b/=m;
    }
    return ans;
}
int main()
{
    ll x,y;
    cin>>x>>y;
    if((x + y) % 3) return cout<<0,0;
    ll m = (2 * x - y)/3;
    ll n = (y - m)/2;
    if(n < 0||m < 0) return cout<<0,0;
    cout<<lucas(n + m,n,mod);
}