답안 #448265

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
448265 2021-07-29T12:56:02 Z stefantaga 힘 센 거북 (IZhO11_turtle) C++14
65 / 100
1979 ms 2156 KB
#include <bits/stdc++.h>

using namespace std;
int frec[300005];
int fr[1005][1005],din[1005][1005][21];
long long k,t,z,n,m;
struct wow
{
    int x,y;
} v[105];
vector <int> prime;
bool c[300005];
long long lim;
long long ridput (long long a,long long b)
{
    if (b==0)
    {
        return 1;
    }
    long long rez=ridput(a,b/2);
    if (b%2==0)
    {
        return (rez*rez)%z;
    }
    return ((rez*rez)%z*a)%z;
}
void adauga(int n,int val)
{
    int j;
    for (j=0; j<(int)prime.size(); j++)
    {
        long long p=prime[j];
        while (p<=n)
        {
            frec[prime[j]]+=(n/p)*val;
            p=p*prime[j];
        }
    }
}
long long combinari(int k,int n)
{
    int j;
    for (j=0; j<(int)prime.size(); j++)
    {
        frec[prime[j]]=0;
    }
    adauga(n,1);
    adauga(k,-1);
    adauga(n-k,-1);
    long long p=1;
    for (j=0; j<(int)prime.size(); j++)
    {
        p=(p*ridput(prime[j],frec[prime[j]]))%z;
    }
    return p;
}
bool dif (int x,int y,int x2,int y2)
{
    if (x!=x2||y!=y2)
    {
        return 1;
    }
    return 0;
}
bool nimic(int x,int y,int x2,int y2)
{
    for (int i=1; i<=k; i++)
    {
        if (dif(v[i].x,v[i].y,x,y)==1&&dif(v[i].x,v[i].y,x2,y2)==1)
        {
            if (x<=v[i].x&&v[i].x<=x2&&y<=v[i].y&&v[i].y<=y2)
            {
                return 0;
            }
        }
    }
    return 1;
}
map <pair <int,int> ,long long > mr;
long long nimicpr[105][105];
long long nr(int st,int dr)
{
    int x=v[st].x;
    int y=v[st].y;
    int x2=v[dr].x;
    int y2=v[dr].y;
    if (x>x2||y>y2)
    {
        swap(st,dr);
        swap(x,x2);
        swap(y,y2);
    }
    long long inc=combinari(x2-x,x2-x+y2-y);
    if (nimic(x,y,x2,y2)==1)
    {
        return combinari(x2-x,x2-x+y2-y);
    }
    if (mr.find({st,dr})!=mr.end())
    {
            return mr[{st,dr}];
    }
    for (int i=1;i<=k;i++)
    {
        if (dif(v[i].x,v[i].y,x,y)==1&&dif(v[i].x,v[i].y,x2,y2)==1)
        {
            if (x<=v[i].x&&v[i].x<=x2&&y<=v[i].y&&v[i].y<=y2)
            {
                inc=(inc-(1LL*nr(st,i)*combinari(x2-v[i].x,x2-v[i].x+y2-v[i].y))%z+z)%z;
            }
        }
    }
    mr[{st,dr}]=mr[{dr,st}]=inc;
    return inc;
}
long long brut()
{
    int i,j;
    for (i=1; i<=k; i++)
    {
        fr[v[i].x][v[i].y]=1;
    }
    din[1][1][0]=1;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            if (i!=1||j!=1)
            {
                for (int r=fr[i][j]; r<=k; r++)
                {
                    din[i][j][r]=(din[i][j][r]+din[i-1][j][r-fr[i][j]]+din[i][j-1][r-fr[i][j]])%z;
                }
            }
        }
    }
    long long sum=0;
    for (int r=0; r<=t; r++)
    {
        sum=(sum+din[n][m][r])%z;
    }
    return sum;
}
bool compare(int a,int b)
{
    return v[a].x<v[b].x||(v[a].x==v[b].x&&v[a].y<v[b].y);
}
long long i,j,dist[105][105];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("turtle.in");
    ofstream cout("turtle.out");
#endif // HOME
    cin>>n>>m>>k>>t>>z;
    n++;
    m++;
    lim=300000;
    c[0]=c[1]=1;
    for (i=2; i<=lim; i++)
    {
        if (c[i]==0)
        {
            prime.push_back(i);
            for (j=i*i; j<=lim; j+=i)
            {
                c[j]=1;
            }
        }
    }
    for (i=1; i<=k; i++)
    {
        cin>>v[i].x>>v[i].y;
        v[i].x++;
        v[i].y++;
    }
    v[0].x=1;
    v[0].y=1;
    v[k+1].x=n;
    v[k+1].y=m;
    lim=(1<<k);
    for (i=0;i<=k+1;i++)
    {
        for (j=0;j<=k+1;j++)
        {
            if (i!=j)
            {
                dist[i][j]=dist[j][i]=nr(i,j);
            }
        }
    }
    long long sum=nr(0,k+1);
    for (int i=1;i<lim;i++)
    {
        vector <int> sol;
        for (int j=0;j<k;j++)
        {
            if (i&(1<<j))
            {
                sol.push_back(j+1);
            }
        }
        int ok=1;
        sort (sol.begin(),sol.end(),compare);
        for (int j=1;j<sol.size();j++)
        {
            if (v[sol[j-1]].y>v[sol[j]].y)
            {
                ok=0;
                break;
            }
        }
        if (sol.size()>t)
        {
            ok=0;
        }
        if (ok==0)
        {
            continue;
        }
        long long p=dist[0][sol[0]];
        for (int j=1;j<sol.size();j++)
        {
            p=(p*dist[sol[j-1]][sol[j]])%z;
        }
        int ult=(int)sol.size()-1;
        p=(p*dist[sol[ult]][k+1])%z;
        sum=(sum+p)%z;
    }
    cout<<sum;
    return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:206:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |         for (int j=1;j<sol.size();j++)
      |                      ~^~~~~~~~~~~
turtle.cpp:214:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  214 |         if (sol.size()>t)
      |             ~~~~~~~~~~^~
turtle.cpp:223:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |         for (int j=1;j<sol.size();j++)
      |                      ~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1996 KB Output is correct
2 Correct 64 ms 2028 KB Output is correct
3 Correct 41 ms 1996 KB Output is correct
4 Correct 329 ms 2024 KB Output is correct
5 Correct 988 ms 2032 KB Output is correct
6 Correct 285 ms 2016 KB Output is correct
7 Correct 394 ms 2028 KB Output is correct
8 Correct 192 ms 1988 KB Output is correct
9 Correct 593 ms 2140 KB Output is correct
10 Correct 637 ms 2156 KB Output is correct
11 Correct 466 ms 1996 KB Output is correct
12 Incorrect 893 ms 2024 KB Output isn't correct
13 Incorrect 211 ms 1996 KB Output isn't correct
14 Correct 1029 ms 2136 KB Output is correct
15 Correct 1276 ms 2028 KB Output is correct
16 Incorrect 1169 ms 2036 KB Output isn't correct
17 Incorrect 727 ms 2036 KB Output isn't correct
18 Incorrect 1955 ms 2024 KB Output isn't correct
19 Incorrect 1979 ms 2152 KB Output isn't correct
20 Incorrect 1026 ms 2028 KB Output isn't correct