답안 #448261

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

using namespace std;
int frec[300005];
int fr[1005][1005],din[1005][1005][21],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-(nr(st,i)*combinari(x2-v[i].x,x2-v[i].x+y2-v[i].y))%z+z)%z;
            }
        }
    }
    mr[{st,dr}]=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;
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;
    //cout<<brut()<<'\n';
    for (i=0;i<=k+1;i++)
    {
        for (j=0;j<=k+1;j++)
        {
            nimicpr[i][j]=nimic(v[i].x,v[i].y,v[j].x,v[j].y);
        }
    }
    lim=(1<<k);
    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=nr(0,sol[0]);
        for (int j=1;j<sol.size();j++)
        {
            p=(p*nr(sol[j-1],sol[j]))%z;
        }
        int ult=(int)sol.size()-1;
        p=(p*nr(sol[ult],k+1))%z;
        /*for (j=0;j<sol.size();j++)
        {
            cout<<sol[j]<<" ";
        }
        cout<<'\n';
        cout<<p<<'\n';*/
        sum=(sum+p)%z;
    }
    cout<<sum;
    return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:203:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |         for (int j=1;j<sol.size();j++)
      |                      ~^~~~~~~~~~~
turtle.cpp:211:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  211 |         if (sol.size()>t)
      |             ~~~~~~~~~~^~
turtle.cpp:220:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |         for (int j=1;j<sol.size();j++)
      |                      ~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1996 KB Output is correct
2 Correct 50 ms 1996 KB Output is correct
3 Correct 31 ms 1996 KB Output is correct
4 Correct 425 ms 1996 KB Output is correct
5 Correct 1584 ms 2024 KB Output is correct
6 Execution timed out 2049 ms 1996 KB Time limit exceeded
7 Correct 788 ms 1996 KB Output is correct
8 Correct 554 ms 1996 KB Output is correct
9 Correct 1416 ms 2020 KB Output is correct
10 Correct 645 ms 2024 KB Output is correct
11 Correct 1256 ms 2016 KB Output is correct
12 Execution timed out 2065 ms 1996 KB Time limit exceeded
13 Incorrect 233 ms 2020 KB Output isn't correct
14 Execution timed out 2082 ms 1996 KB Time limit exceeded
15 Execution timed out 2094 ms 1996 KB Time limit exceeded
16 Incorrect 1609 ms 2116 KB Output isn't correct
17 Incorrect 186 ms 2028 KB Output isn't correct
18 Execution timed out 2098 ms 2012 KB Time limit exceeded
19 Execution timed out 2097 ms 1996 KB Time limit exceeded
20 Incorrect 1432 ms 2024 KB Output isn't correct