oj.uz

Submission #907951

# Submission time Handle Problem Language Result Execution time Memory
907951 2024-01-16T06:31:51 Z ibm2006 Ljetopica (COI19_ljetopica) C++17
22 / 100
 60 ms 230284 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,a[1100000],b[1100000],com[5500][5500],tw[5500],dp[1100][1100],ans;
char c;
const ll mod=1000000007;
ll C(ll x,ll y)
{
    if(x<0||y<0||y>x)
        return 0;
        return com[x][y];
}
ll two(ll x)
{
    return tw[x];
}
ll f(ll x,ll y,ll z,ll w=0)
{
   // printf("(%lld,%lld,%lld,%lld)\n",x,y,z,w);
    if(y<0)
        return 0;
    if(x==1&&y==0)
        return z+two(n-1)-1;
        if(x==1)
            return 0;
    ll i;
    ll s=0;
    if(b[n-x+2]==0)
    {
        if(a[n-x+1]^w==0)
            return f(x-1,y,z,w);
    else
        return f(x-1,y-1,z,w^1);
    }
    else
    {
        if(a[n-x+1]^w==0)
        {
            if(w==0)
            {s=dp[x-1][y]+C(x-2,y)*(two(n-1)+z-1-two(x-2))%mod;
            //printf("[%lld,%lld:%lld]\n",x-1,y,dp[x-1][y]);
            }
            else
            {
                s=-C(x-2,y)*(two(n-1)+z-1-two(x-2))%mod+C(x-2,y)*(two(n-1)-1+z+two(n-1)-1+z+two(x-2)-1)%mod-dp[x-1][y];
               // printf("{%lld}",s);
            }
            s+=f(x-1,y-1,z+two(x-2),w^1);
            s%=mod;
            return s;
        }
        /*printf("!");
        if(w==0)
        if(y>=1)
        {
            s=dp[x-1][y-1]+C(x-2,y-1)*(two(n-1)+z-2)%mod;
        }
        s+=f(x-1,y,z+two(x-2),w);
        s%=mod;
        return s;*/
        if(y>=0)
        {if(w==1)
            {s=dp[x-1][y-1]+C(x-2,y-1)*(two(n-1)+z-1-two(x-2))%mod;
            }
            else
            {
                s=-C(x-2,y-1)*(two(n-1)+z-1-two(x-2))%mod+C(x-2,y-1)*(two(n-1)-1+z+two(n-1)-1+z+two(x-2)-1)%mod-dp[x-1][y-1];
                //printf("{%lld,%lld}",s,dp[x-1][y-1]);
            }
        }
            s+=f(x-1,y,z+two(x-2),w);
            s%=mod;
            return s;
    }
}
ll num(ll x,ll y,ll w=0)
{
    if(y<0)
        return 0;
    if(x==1)
        return z;
    ll i;
    ll s=0;
    if(b[n-x+2]==0)
    {
        if(a[n-x+1]^w==0)
            return num(x-1,y,w);
        else
            return num(x-1,y-1,w^1);
    }
    if(a[n-x+1]^w==0)
    {
        s=C(x-2,y);
        s+=num(x-1,y-1,w^1);
        return s;
    }
    s=C(x-2,y-1);
    s+=num(x-1,y,w);
    return s;
}
int main()
{
    tw[0]=1;
    com[0][0]=1;
    for(i=1;i<=5000;i++)
    {
        for(j=0;j<=i;j++)
        {
            if(j==0)
            {
                com[i][j]=1;
                continue;
            }
            com[i][j]=(com[i-1][j]+com[i-1][j-1])%mod;
        }
    }
    for(i=1;i<=5000;i++)
    {
        tw[i]=tw[i-1]*2%mod;
    }
    scanf("%lld %lld\n",&n,&k);
    for(i=1;i<n;i++)
    {
        scanf("%c",&c);
        if(c=='L')
        {
            a[i]=0;
        }
        else
        {
            a[i]=1;
        }
    }
    dp[1][0]=1;
    for(i=2;i<=n;i++)
    {
        for(j=0;j<i;j++)
        {
            if(a[n-i+1]==0)
            {
                if(j==0)
                {
                    dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-2)%mod;
                }
                else
                {dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-2)%mod+(two(i-2)*3+two(i-1)-1)*C(i-2,j-1)%mod-dp[i-1][j-1];}
                dp[i][j]%=mod;
                dp[i][j]=(dp[i][j]+mod)%mod;
            }
            else
            {
                if(j==0)
                {
                    dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-1)%mod;
                }
                else
                dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-1)%mod+(two(i)-1)*C(i-2,j-1)%mod-dp[i-1][j-1];
                dp[i][j]%=mod;
                dp[i][j]=(dp[i][j]+mod)%mod;
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        scanf("%01lld",&b[i]);
    }
    for(i=n;i>=2;i--)
    {
        b[i]++;
        b[i-1]+=b[i]/2;
        b[i]%=2;
    }
    b[1]=1;
    /*for(i=1;i<=n;i++)
        printf("%lld",b[i]);
    printf("\n");
    */ans-=f(n,k,1);
    //printf("%lld\n",ans);
    /*for(i=2;i<=n;i++)
    {
        b[i]^=1;
    }
    ans-=num(n,k)*(two(n)+two(n-1)-1)%mod-f(n,k,1);*/
    ans-=f(n,k,1,1);
    //printf("%lld\n",ans);
    for(i=1;i<=n;i++)
    {
        scanf("%01lld",&b[i]);
    }
ans+=f(n,k,1);
//printf("%lld\n",ans);
    /*for(i=2;i<=n;i++)
    {
        b[i]^=1;
    }*/
    //ans+=num(n,k)*(two(n)+two(n-1)-1)%mod-f(n,k,1);
    ans+=f(n,k,1,1);
    /*if(k>=1)
    {
        ans=dp[n][k]+dp[n][k-1]+(two(n)-1+two(n-1))*C(n-1,k)%mod-dp[n][k]-dp[n][k-1];
    }
    else
    {
        ans=dp[n][k]+two(n)-1+two(n-1)-dp[n][k];
    }*/
    ans%=mod;
    ans+=mod;
    ans%=mod;
    printf("%lld",ans%mod);
}

Compilation message

ljetopica.cpp: In function 'll C(ll, ll)':
ljetopica.cpp:9:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    9 |     if(x<0||y<0||y>x)
      |     ^~
ljetopica.cpp:11:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   11 |         return com[x][y];
      |         ^~~~~~
ljetopica.cpp: In function 'll f(ll, ll, ll, ll)':
ljetopica.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |     if(x==1&&y==0)
      |     ^~
ljetopica.cpp:24:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |         if(x==1)
      |         ^~
ljetopica.cpp:30:22: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   30 |         if(a[n-x+1]^w==0)
      |                     ~^~~
ljetopica.cpp:37:22: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   37 |         if(a[n-x+1]^w==0)
      |                     ~^~~
ljetopica.cpp:26:8: warning: unused variable 'i' [-Wunused-variable]
   26 |     ll i;
      |        ^
ljetopica.cpp: In function 'll num(ll, ll, ll)':
ljetopica.cpp:86:22: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   86 |         if(a[n-x+1]^w==0)
      |                     ~^~~
ljetopica.cpp:91:18: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   91 |     if(a[n-x+1]^w==0)
      |                 ~^~~
ljetopica.cpp:82:8: warning: unused variable 'i' [-Wunused-variable]
   82 |     ll i;
      |        ^
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     scanf("%lld %lld\n",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
ljetopica.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         scanf("%c",&c);
      |         ~~~~~^~~~~~~~~
ljetopica.cpp:165:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         scanf("%01lld",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
ljetopica.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         scanf("%01lld",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 230228 KB Output is correct
2 Correct 58 ms 230136 KB Output is correct
3 Correct 55 ms 230284 KB Output is correct
4 Correct 54 ms 230228 KB Output is correct
5 Correct 55 ms 230224 KB Output is correct
6 Correct 56 ms 230124 KB Output is correct
7 Correct 58 ms 228176 KB Output is correct
8 Correct 53 ms 228180 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 223988 KB Output is correct
2 Correct 53 ms 221924 KB Output is correct
3 Correct 51 ms 224084 KB Output is correct
4 Correct 53 ms 224168 KB Output is correct
5 Correct 50 ms 224084 KB Output is correct
6 Correct 53 ms 224512 KB Output is correct
7 Correct 50 ms 224080 KB Output is correct
8 Correct 51 ms 224084 KB Output is correct
9 Correct 53 ms 221980 KB Output is correct
10 Correct 50 ms 222284 KB Output is correct
11 Correct 55 ms 224008 KB Output is correct
12 Correct 54 ms 222032 KB Output is correct
13 Correct 52 ms 224084 KB Output is correct
14 Correct 52 ms 224084 KB Output is correct
15 Correct 51 ms 224084 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 230276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 230228 KB Output is correct
2 Correct 58 ms 230136 KB Output is correct
3 Correct 55 ms 230284 KB Output is correct
4 Correct 54 ms 230228 KB Output is correct
5 Correct 55 ms 230224 KB Output is correct
6 Correct 56 ms 230124 KB Output is correct
7 Correct 58 ms 228176 KB Output is correct
8 Correct 53 ms 228180 KB Output is correct
9 Correct 51 ms 223988 KB Output is correct
10 Correct 53 ms 221924 KB Output is correct
11 Correct 51 ms 224084 KB Output is correct
12 Correct 53 ms 224168 KB Output is correct
13 Correct 50 ms 224084 KB Output is correct
14 Correct 53 ms 224512 KB Output is correct
15 Correct 50 ms 224080 KB Output is correct
16 Correct 51 ms 224084 KB Output is correct
17 Correct 53 ms 221980 KB Output is correct
18 Correct 50 ms 222284 KB Output is correct
19 Correct 55 ms 224008 KB Output is correct
20 Correct 54 ms 222032 KB Output is correct
21 Correct 52 ms 224084 KB Output is correct
22 Correct 52 ms 224084 KB Output is correct
23 Correct 51 ms 224084 KB Output is correct
24 Incorrect 55 ms 230276 KB Output isn't correct
25 Halted 0 ms 0 KB -