HDU 5794 A Simple Chess - dblank

HDU 5794 A Simple Chess

<div class="panel_title" align="left">Problem Description</div>
<div class="panel_content">There is a <span id="MathJax-Element-1-Frame" class="MathJax"><span id="MathJax-Span-1" class="math"><span id="MathJax-Span-2" class="mrow"><span id="MathJax-Span-3" class="mi">n</span><span id="MathJax-Span-4" class="mo">×</span><span id="MathJax-Span-5" class="mi">m</span></span></span></span> board, a chess want to go to the position
<span id="MathJax-Element-2-Frame" class="MathJax"><span id="MathJax-Span-6" class="math"><span id="MathJax-Span-7" class="mrow"><span id="MathJax-Span-8" class="mo">(</span><span id="MathJax-Span-9" class="mi">n</span><span id="MathJax-Span-10" class="mo">,</span><span id="MathJax-Span-11" class="mi">m</span><span id="MathJax-Span-12" class="mo">)</span></span></span></span> from the position <span id="MathJax-Element-3-Frame" class="MathJax"><span id="MathJax-Span-13" class="math"><span id="MathJax-Span-14" class="mrow"><span id="MathJax-Span-15" class="mo">(</span><span id="MathJax-Span-16" class="mn">1</span><span id="MathJax-Span-17" class="mo">,</span><span id="MathJax-Span-18" class="mn">1</span><span id="MathJax-Span-19" class="mo">)</span></span></span></span>.
The chess is able to go to position <span id="MathJax-Element-4-Frame" class="MathJax"><span id="MathJax-Span-20" class="math"><span id="MathJax-Span-21" class="mrow"><span id="MathJax-Span-22" class="mo">(</span><span id="MathJax-Span-23" class="msubsup"><span id="MathJax-Span-24" class="mi">x</span><span id="MathJax-Span-25" class="mn">2</span></span><span id="MathJax-Span-26" class="mo">,</span><span id="MathJax-Span-27" class="msubsup"><span id="MathJax-Span-28" class="mi">y</span><span id="MathJax-Span-29" class="mn">2</span></span><span id="MathJax-Span-30" class="mo">)</span></span></span></span> from the position <span id="MathJax-Element-5-Frame" class="MathJax"><span id="MathJax-Span-31" class="math"><span id="MathJax-Span-32" class="mrow"><span id="MathJax-Span-33" class="mo">(</span><span id="MathJax-Span-34" class="msubsup"><span id="MathJax-Span-35" class="mi">x</span><span id="MathJax-Span-36" class="mn">1</span></span><span id="MathJax-Span-37" class="mo">,</span><span id="MathJax-Span-38" class="msubsup"><span id="MathJax-Span-39" class="mi">y</span><span id="MathJax-Span-40" class="mn">1</span></span><span id="MathJax-Span-41" class="mo">)</span></span></span></span>, only and if only <span id="MathJax-Element-6-Frame" class="MathJax"><span id="MathJax-Span-42" class="math"><span id="MathJax-Span-43" class="mrow"><span id="MathJax-Span-44" class="msubsup"><span id="MathJax-Span-45" class="mi">x</span><span id="MathJax-Span-46" class="mn">1</span></span><span id="MathJax-Span-47" class="mo">,</span><span id="MathJax-Span-48" class="msubsup"><span id="MathJax-Span-49" class="mi">y</span><span id="MathJax-Span-50" class="mn">1</span></span><span id="MathJax-Span-51" class="mo">,</span><span id="MathJax-Span-52" class="msubsup"><span id="MathJax-Span-53" class="mi">x</span><span id="MathJax-Span-54" class="mn">2</span></span><span id="MathJax-Span-55" class="mo">,</span><span id="MathJax-Span-56" class="msubsup"><span id="MathJax-Span-57" class="mi">y</span><span id="MathJax-Span-58" class="mn">2</span></span></span></span></span> is satisfied that <span id="MathJax-Element-7-Frame" class="MathJax"><span id="MathJax-Span-59" class="math"><span id="MathJax-Span-60" class="mrow"><span id="MathJax-Span-61" class="mo">(</span><span id="MathJax-Span-62" class="msubsup"><span id="MathJax-Span-63" class="mi">x</span><span id="MathJax-Span-64" class="mn">2</span></span><span id="MathJax-Span-65" class="mo">−</span><span id="MathJax-Span-66" class="msubsup"><span id="MathJax-Span-67" class="mi">x</span><span id="MathJax-Span-68" class="mn">1</span></span><span id="MathJax-Span-69" class="msubsup"><span id="MathJax-Span-70" class="mo">)</span><span id="MathJax-Span-71" class="mn">2</span></span><span id="MathJax-Span-72" class="mo">+</span><span id="MathJax-Span-73" class="mo">(</span><span id="MathJax-Span-74" class="msubsup"><span id="MathJax-Span-75" class="mi">y</span><span id="MathJax-Span-76" class="mn">2</span></span><span id="MathJax-Span-77" class="mo">−</span><span id="MathJax-Span-78" class="msubsup"><span id="MathJax-Span-79" class="mi">y</span><span id="MathJax-Span-80" class="mn">1</span></span><span id="MathJax-Span-81" class="msubsup"><span id="MathJax-Span-82" class="mo">)</span><span id="MathJax-Span-83" class="mn">2</span></span><span id="MathJax-Span-84" class="mo">=</span><span id="MathJax-Span-85" class="mn">5</span><span id="MathJax-Span-86" class="mo">,</span><span id="MathJax-Span-87" class="mtext"> </span><span id="MathJax-Span-88" class="msubsup"><span id="MathJax-Span-89" class="mi">x</span><span id="MathJax-Span-90" class="mn">2</span></span><span id="MathJax-Span-91" class="mo">></span><span id="MathJax-Span-92" class="msubsup"><span id="MathJax-Span-93" class="mi">x</span><span id="MathJax-Span-94" class="mn">1</span></span><span id="MathJax-Span-95" class="mo">,</span><span id="MathJax-Span-96" class="mtext"> </span><span id="MathJax-Span-97" class="msubsup"><span id="MathJax-Span-98" class="mi">y</span><span id="MathJax-Span-99" class="mn">2</span></span><span id="MathJax-Span-100" class="mo">></span><span id="MathJax-Span-101" class="msubsup"><span id="MathJax-Span-102" class="mi">y</span><span id="MathJax-Span-103" class="mn">1</span></span></span></span></span>.
Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle.
I want you to tell me, There are how may ways the chess can achieve its goal.</div>
<div class="panel_bottom"></div>
 
<div class="panel_title" align="left">Input</div>
<div class="panel_content">The input consists of multiple test cases.
For each test case:
The first line is three integers, <span id="MathJax-Element-8-Frame" class="MathJax"><span id="MathJax-Span-104" class="math"><span id="MathJax-Span-105" class="mrow"><span id="MathJax-Span-106" class="mi">n</span><span id="MathJax-Span-107" class="mo">,</span><span id="MathJax-Span-108" class="mi">m</span><span id="MathJax-Span-109" class="mo">,</span><span id="MathJax-Span-110" class="mi">r</span><span id="MathJax-Span-111" class="mo">,</span><span id="MathJax-Span-112" class="mo">(</span><span id="MathJax-Span-113" class="mn">1</span><span id="MathJax-Span-114" class="mo">≤</span><span id="MathJax-Span-115" class="mi">n</span><span id="MathJax-Span-116" class="mo">,</span><span id="MathJax-Span-117" class="mi">m</span><span id="MathJax-Span-118" class="mo">≤</span><span id="MathJax-Span-119" class="msubsup"><span id="MathJax-Span-120" class="mn">10</span><span id="MathJax-Span-121" class="texatom"><span id="MathJax-Span-122" class="mrow"><span id="MathJax-Span-123" class="mn">18</span></span></span></span><span id="MathJax-Span-124" class="mo">,</span><span id="MathJax-Span-125" class="mn">0</span><span id="MathJax-Span-126" class="mo">≤</span><span id="MathJax-Span-127" class="mi">r</span><span id="MathJax-Span-128" class="mo">≤</span><span id="MathJax-Span-129" class="mn">100</span><span id="MathJax-Span-130" class="mo">)</span></span></span></span>, denoting the height of the board, the weight of the board, and the number of the obstacles on the board.
Then follow <span id="MathJax-Element-9-Frame" class="MathJax"><span id="MathJax-Span-131" class="math"><span id="MathJax-Span-132" class="mrow"><span id="MathJax-Span-133" class="mi">r</span></span></span></span> lines, each lines have two integers, <span id="MathJax-Element-10-Frame" class="MathJax"><span id="MathJax-Span-134" class="math"><span id="MathJax-Span-135" class="mrow"><span id="MathJax-Span-136" class="mi">x</span><span id="MathJax-Span-137" class="mo">,</span><span id="MathJax-Span-138" class="mi">y</span><span id="MathJax-Span-139" class="mo">(</span><span id="MathJax-Span-140" class="mn">1</span><span id="MathJax-Span-141" class="mo">≤</span><span id="MathJax-Span-142" class="mi">x</span><span id="MathJax-Span-143" class="mo">≤</span><span id="MathJax-Span-144" class="mi">n</span><span id="MathJax-Span-145" class="mo">,</span><span id="MathJax-Span-146" class="mn">1</span><span id="MathJax-Span-147" class="mo">≤</span><span id="MathJax-Span-148" class="mi">y</span><span id="MathJax-Span-149" class="mo">≤</span><span id="MathJax-Span-150" class="mi">m</span><span id="MathJax-Span-151" class="mo">)</span></span></span></span>, denoting the position of the obstacles. please note there aren't never a obstacles at position <span id="MathJax-Element-11-Frame" class="MathJax"><span id="MathJax-Span-152" class="math"><span id="MathJax-Span-153" class="mrow"><span id="MathJax-Span-154" class="mo">(</span><span id="MathJax-Span-155" class="mn">1</span><span id="MathJax-Span-156" class="mo">,</span><span id="MathJax-Span-157" class="mn">1</span><span id="MathJax-Span-158" class="mo">)</span></span></span></span>.</div>
<div class="panel_bottom"></div>
 
<div class="panel_title" align="left">Output</div>
<div class="panel_content">For each test case,output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer after module <span id="MathJax-Element-12-Frame" class="MathJax"><span id="MathJax-Span-159" class="math"><span id="MathJax-Span-160" class="mrow"><span id="MathJax-Span-161" class="mn">110119</span></span></span></span>.</div>
<div class="panel_content"></div>
<div class="panel_bottom"> 思路: 首先不考虑坏点的问题,我们可以看出其实方案数是一个杨辉三角,然后我们把坐标化简成杨辉三角的坐标,x' = (x+y-2)/3, y' = y - 1 -(x+y-2)。如果得到负数坐标或者(x+y-2)不能被三整除,都说明到达不了。然后考虑坏点问题,对于一个坏点,我们要减去从起点到坏点的方案数*坏点到终点的方案数,但是这个地方会有重复的情况,我们可以用dp[i]表示到达坏点i,并且不经过其他坏点 的方案数,用总的方案数减掉就好了。然后这个坐标很大,然而mod很小而且是一个质数,我们就可以用lucas定理求得组合数。</div>

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 200000 + 10, Mod = 110119;
typedef long long  ll;
ll fact[N], inv[N], cnt;
typedef pair<ll, ll> P;
P p[200];
ll dp[200];
int quick_pow(ll x, ll y)
{
    ll res = 1;
    while(y)
    {
        if(y&1) res = res*x%Mod;
        x = x*x%Mod;
        y>>=1;
    }
    return res;
}
void init()
{
    fact[0] = 1;
    inv[0] = 1;
    for(int i = 1; i<=Mod; i++)
    {
        fact[i] = fact[i-1]*i%Mod;
        inv[i] = quick_pow(fact[i], Mod-2)%Mod;
    }
}
inline ll C(int n, int m)
{
    return 1LL*fact[n]*inv[m]%Mod*inv[n-m]%Mod;
}
int lucas(ll n, ll m)
{
    if(!m) return 1;
    int a = n%Mod, b = m%Mod;
    if(a<b) return 0;
    return 1LL*C(a, b)*lucas(n/Mod, m/Mod)%Mod;
}
int change(ll &x, ll &y)
{
    x--, y--;
    ll xx = x + y, yy = 3*y - x - y;
    if(xx%3 || yy%3 || xx < 0 || yy < 0) return 0;
    x = xx / 3, y = yy /3;
    return 1;
}
ll get(ll f, ll e, ll x, ll y)
{
    x -= f, y -= e;
    return lucas(x, y);
}
ll solve(int x)
{
    if(dp[x]) return dp[x];
    ll res = get(0, 0, p[x].first, p[x].second);
    for(int i = 0; i<x; i++)
    {
        if(p[i].first <= p[x].first && p[i].second <= p[x].second)
        {
            res = (res - 1LL*get(p[i].first, p[i].second, p[x].first, p[x].second)*solve(i)%Mod+Mod)%Mod;
        }
    }
    return dp[x] = res;
}
int main()
{
    int cas = 1;
    ll n, m, r;
    init();
    while(cin>>n>>m>>r)
    {
        memset(dp, 0, sizeof(dp));
        printf("Case #%d: ", cas++);
        for(int i = 0; i<r; i++)
            scanf("%I64d%I64d", &p[i].first, &p[i].second);
        if(!change(n, m))
        {
            printf("0\n");
            continue;
        }
        ll ans = get(0, 0, n, m);
        cnt = 0;
        sort(p, p+r);
        for(int i = 0; i<r; i++)
        {
            if(change(p[i].first, p[i].second))
                p[cnt++] = p[i];
        }
        for(int i = 0; i<cnt; i++)
        {

            if(p[i].first <= n && p[i].second <= m)
            {
                ans = (ans - 1LL*get(p[i].first, p[i].second, n, m)*solve(i)%Mod+Mod)%Mod;
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

相关文章

发表新评论