oj.uz

Submission #907958

# Submission time Handle Problem Language Result Execution time Memory
907958 2024-01-16T06:35:14 Z ibm2006 Ljetopica (COI19_ljetopica) C++17
100 / 100
 65 ms 230336 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)%mod;
        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)%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)%mod+C(x-2,y)*((two(n-1)-1+z+two(n-1)-1+z+two(x-2)-1)%mod)%mod-dp[x-1][y];
               // printf("{%lld}",s);
            }
            s+=f(x-1,y-1,z+two(x-2),w^1);
            s%=mod;
            s+=mod;
            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)%mod;
            }
            else
            {
                s=-C(x-2,y-1)*((two(n-1)+z-1-two(x-2))%mod)%mod+C(x-2,y-1)*((two(n-1)-1+z+two(n-1)-1+z+two(x-2)-1)%mod)%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;
            s+=mod;
            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)%mod*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:90:22: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   90 |         if(a[n-x+1]^w==0)
      |                     ~^~~
ljetopica.cpp:95:18: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   95 |     if(a[n-x+1]^w==0)
      |                 ~^~~
ljetopica.cpp:86:8: warning: unused variable 'i' [-Wunused-variable]
   86 |     ll i;
      |        ^
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     scanf("%lld %lld\n",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
ljetopica.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf("%c",&c);
      |         ~~~~~^~~~~~~~~
ljetopica.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         scanf("%01lld",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
ljetopica.cpp:192:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         scanf("%01lld",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 230128 KB Output is correct
2 Correct 54 ms 230320 KB Output is correct
3 Correct 61 ms 230172 KB Output is correct
4 Correct 56 ms 230236 KB Output is correct
5 Correct 55 ms 230312 KB Output is correct
6 Correct 59 ms 230244 KB Output is correct
7 Correct 59 ms 228172 KB Output is correct
8 Correct 54 ms 228180 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 224104 KB Output is correct
2 Correct 54 ms 224080 KB Output is correct
3 Correct 52 ms 224084 KB Output is correct
4 Correct 55 ms 224092 KB Output is correct
5 Correct 53 ms 224084 KB Output is correct
6 Correct 56 ms 224080 KB Output is correct
7 Correct 56 ms 224268 KB Output is correct
8 Correct 50 ms 223988 KB Output is correct
9 Correct 51 ms 224028 KB Output is correct
10 Correct 51 ms 222036 KB Output is correct
11 Correct 53 ms 224112 KB Output is correct
12 Correct 56 ms 222032 KB Output is correct
13 Correct 51 ms 224080 KB Output is correct
14 Correct 52 ms 224056 KB Output is correct
15 Correct 51 ms 224172 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 230228 KB Output is correct
2 Correct 59 ms 230312 KB Output is correct
3 Correct 55 ms 230224 KB Output is correct
4 Correct 55 ms 230284 KB Output is correct
5 Correct 61 ms 230220 KB Output is correct
6 Correct 56 ms 230224 KB Output is correct
7 Correct 55 ms 230224 KB Output is correct
8 Correct 55 ms 230228 KB Output is correct
9 Correct 56 ms 230252 KB Output is correct
10 Correct 57 ms 230228 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 230128 KB Output is correct
2 Correct 54 ms 230320 KB Output is correct
3 Correct 61 ms 230172 KB Output is correct
4 Correct 56 ms 230236 KB Output is correct
5 Correct 55 ms 230312 KB Output is correct
6 Correct 59 ms 230244 KB Output is correct
7 Correct 59 ms 228172 KB Output is correct
8 Correct 54 ms 228180 KB Output is correct
9 Correct 50 ms 224104 KB Output is correct
10 Correct 54 ms 224080 KB Output is correct
11 Correct 52 ms 224084 KB Output is correct
12 Correct 55 ms 224092 KB Output is correct
13 Correct 53 ms 224084 KB Output is correct
14 Correct 56 ms 224080 KB Output is correct
15 Correct 56 ms 224268 KB Output is correct
16 Correct 50 ms 223988 KB Output is correct
17 Correct 51 ms 224028 KB Output is correct
18 Correct 51 ms 222036 KB Output is correct
19 Correct 53 ms 224112 KB Output is correct
20 Correct 56 ms 222032 KB Output is correct
21 Correct 51 ms 224080 KB Output is correct
22 Correct 52 ms 224056 KB Output is correct
23 Correct 51 ms 224172 KB Output is correct
24 Correct 56 ms 230228 KB Output is correct
25 Correct 59 ms 230312 KB Output is correct
26 Correct 55 ms 230224 KB Output is correct
27 Correct 55 ms 230284 KB Output is correct
28 Correct 61 ms 230220 KB Output is correct
29 Correct 56 ms 230224 KB Output is correct
30 Correct 55 ms 230224 KB Output is correct
31 Correct 55 ms 230228 KB Output is correct
32 Correct 56 ms 230252 KB Output is correct
33 Correct 57 ms 230228 KB Output is correct
34 Correct 58 ms 230140 KB Output is correct
35 Correct 60 ms 230316 KB Output is correct
36 Correct 56 ms 230220 KB Output is correct
37 Correct 56 ms 230228 KB Output is correct
38 Correct 55 ms 230276 KB Output is correct
39 Correct 55 ms 230228 KB Output is correct
40 Correct 55 ms 230224 KB Output is correct
41 Correct 56 ms 230228 KB Output is correct
42 Correct 55 ms 230224 KB Output is correct
43 Correct 55 ms 230228 KB Output is correct
44 Correct 56 ms 230208 KB Output is correct
45 Correct 55 ms 230224 KB Output is correct
46 Correct 56 ms 230208 KB Output is correct
47 Correct 56 ms 230228 KB Output is correct
48 Correct 55 ms 230224 KB Output is correct
49 Correct 56 ms 230292 KB Output is correct
50 Correct 56 ms 230228 KB Output is correct
51 Correct 55 ms 230132 KB Output is correct
52 Correct 59 ms 230320 KB Output is correct
53 Correct 55 ms 230224 KB Output is correct
54 Correct 55 ms 230232 KB Output is correct
55 Correct 56 ms 230216 KB Output is correct
56 Correct 57 ms 230336 KB Output is correct
57 Correct 58 ms 230228 KB Output is correct
58 Correct 61 ms 230228 KB Output is correct