QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797837#9835. Longest Common SubstringMu_Silk#AC ✓1008ms802608kbC++232.7kb2024-12-03 19:29:592024-12-03 19:30:01

Judging History

你现在查看的是最新测评结果

  • [2024-12-03 19:30:01]
  • 评测
  • 测评结果：AC
  • 用时：1008ms
  • 内存：802608kb
查看
  • [2024-12-03 19:29:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll Mod=998244353;
ll n,m,k;

ll dp[101][65536][8][2],ss[2][65536],ns[2][65536];

void solve(){
    cin>>n>>m>>k;
    string s;
    cin>>s;
    ll w=0,mk=(1<<k);
    for(ll i=k-1;i>=0;i--){
        w=w*2+s[i]-'0';
    }
  //  cout<<w<<'\n';
    for(ll i=0;i<(1<<k);i++) {
        if(i!=w) dp[k][0][i][0]=1;
        else dp[k][0][i][1]=1;
    }
    for(ll i=k;i<=max(n,m)-1;i++){
        for(ll j=0;j<(1<<(1<<(k+1)));j++){
            for(ll u=0;u<(1<<k);u++){
                
                ll v=u*2;
                //cout<<v<<'\n';
                if(v%mk==w){
                    dp[i+1][j|(1<<v)][v%mk][1]+=dp[i][j][u][0]+dp[i][j][u][1];
                    dp[i+1][j|(1<<v)][v%mk][1]%=Mod;
                }
                else {
                    dp[i+1][j|(1<<v)][v%mk][1]+=dp[i][j][u][1];
                    dp[i+1][j|(1<<v)][v%mk][1]%=Mod;
                    dp[i+1][j|(1<<v)][v%mk][0]+=dp[i][j][u][0];
                    dp[i+1][j|(1<<v)][v%mk][0]%=Mod;
                }
                v++;
               // cout<<mk<<" "<<w<<" "<<v%mk<<" "<<'\n';
                if(v%mk==w){
                  
                    dp[i+1][j|(1<<v)][v%mk][1]+=dp[i][j][u][0]+dp[i][j][u][1];
                    
                    dp[i+1][j|(1<<v)][v%mk][1]%=Mod;
                }
                else {
                    dp[i+1][j|(1<<v)][v%mk][1]+=dp[i][j][u][1];
                    dp[i+1][j|(1<<v)][v%mk][1]%=Mod;
                    dp[i+1][j|(1<<v)][v%mk][0]+=dp[i][j][u][0];
                    dp[i+1][j|(1<<v)][v%mk][0]%=Mod;
                }
            }
        }
    }
  //  cout<<dp[2][2][1][1]<<'\n';
    ll ans=0;
    for(ll j=0;j<(1<<(1<<(k+1)));j++){
        for(ll v=0;v<(1<<k);v++) {
            ss[0][j]+=dp[n][j][v][1];
            ss[0][j]%=Mod;
        }
        ns[0][j]=ss[0][j];
    }
    for(ll j=0;j<(1<<(1<<(k+1)));j++){
        for(ll v=0;v<(1<<k);v++) {
            ss[1][j]+=dp[m][j][v][1];
            ss[1][j]%=Mod;
        }
        ns[1][j]=ss[1][j];
    }
    for(ll i=0;i<(1<<(k+1));i++){
        for(ll j=0;j<(1<<(1<<(k+1)));j++){
            if(j&(1<<i)) {
                ss[0][j]+=ss[0][j^(1<<i)];
                ss[0][j]%=Mod;
                ss[1][j]+=ss[1][j^(1<<i)];
                ss[1][j]%=Mod;
            }
        }
    }
    for(ll j=0;j<(1<<(1<<(k+1)));j++){
       // cout<<j<<" "<<ns[0][j]<<" "<<ss[0][j]<<'\n';
        ans+=ns[0][j]*ss[1][((1<<(1<<(k+1)))-1)-j]%Mod;
        ans%=Mod;
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n=1;
     //cin>>n;
    while(n--)solve();
    return 0;
}
源文件, 语言: C++23

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5644kb

input:

2 2 1
1

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5976kb

input:

3 4 2
01

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 39ms
memory: 40484kb

input:

7 5 3
110

output:

399

result:

ok 1 number(s): "399"

Test #4:

score: 0
Accepted
time: 392ms
memory: 327164kb

input:

23 42 3
000

output:

174497840

result:

ok 1 number(s): "174497840"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5644kb

input:

1 1 1
0

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 5672kb

input:

2 2 2
00

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 5952kb

input:

2 2 2
10

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 1ms
memory: 5864kb

input:

2 2 2
01

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 8ms
memory: 7940kb

input:

3 3 3
000

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 2ms
memory: 7732kb

input:

3 3 3
010

output:

1

result:

ok 1 number(s): "1"

Test #11:

score: 0
Accepted
time: 4ms
memory: 7728kb

input:

3 3 3
111

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 8ms
memory: 7624kb

input:

3 3 3
001

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 1ms
memory: 5936kb

input:

10 10 1
0

output:

290

result:

ok 1 number(s): "290"

Test #14:

score: 0
Accepted
time: 1ms
memory: 6296kb

input:

100 100 1
0

output:

485170149

result:

ok 1 number(s): "485170149"

Test #15:

score: 0
Accepted
time: 2ms
memory: 9388kb

input:

100 100 2
01

output:

292747039

result:

ok 1 number(s): "292747039"

Test #16:

score: 0
Accepted
time: 978ms
memory: 802596kb

input:

100 100 3
000

output:

285441949

result:

ok 1 number(s): "285441949"

Test #17:

score: 0
Accepted
time: 1008ms
memory: 802592kb

input:

100 100 3
100

output:

461798427

result:

ok 1 number(s): "461798427"

Test #18:

score: 0
Accepted
time: 948ms
memory: 802356kb

input:

100 100 3
010

output:

847755783

result:

ok 1 number(s): "847755783"

Test #19:

score: 0
Accepted
time: 946ms
memory: 802556kb

input:

100 99 3
001

output:

399963513

result:

ok 1 number(s): "399963513"

Test #20:

score: 0
Accepted
time: 967ms
memory: 802564kb

input:

100 99 3
010

output:

415080

result:

ok 1 number(s): "415080"

Test #21:

score: 0
Accepted
time: 992ms
memory: 802308kb

input:

100 99 3
000

output:

762558612

result:

ok 1 number(s): "762558612"

Test #22:

score: 0
Accepted
time: 960ms
memory: 802560kb

input:

99 100 3
000

output:

762558612

result:

ok 1 number(s): "762558612"

Test #23:

score: 0
Accepted
time: 993ms
memory: 802608kb

input:

99 100 3
001

output:

399963513

result:

ok 1 number(s): "399963513"

Test #24:

score: 0
Accepted
time: 986ms
memory: 802244kb

input:

99 100 3
010

output:

415080

result:

ok 1 number(s): "415080"

Test #25:

score: 0
Accepted
time: 2ms
memory: 6092kb

input:

1 100 1
1

output:

882499717

result:

ok 1 number(s): "882499717"

Test #26:

score: 0
Accepted
time: 2ms
memory: 6296kb

input:

100 1 1
0

output:

882499717

result:

ok 1 number(s): "882499717"

Test #27:

score: 0
Accepted
time: 0ms
memory: 9460kb

input:

2 100 2
01

output:

882499617

result:

ok 1 number(s): "882499617"

Test #28:

score: 0
Accepted
time: 5ms
memory: 9456kb

input:

100 2 2
11

output:

140792468

result:

ok 1 number(s): "140792468"

Test #29:

score: 0
Accepted
time: 890ms
memory: 802292kb

input:

3 100 3
010

output:

54671863

result:

ok 1 number(s): "54671863"

Test #30:

score: 0
Accepted
time: 997ms
memory: 802248kb

input:

100 3 3
111

output:

49612087

result:

ok 1 number(s): "49612087"

Test #31:

score: 0
Accepted
time: 1ms
memory: 5584kb

input:

2 1 1
1

output:

3

result:

ok 1 number(s): "3"

Test #32:

score: 0
Accepted
time: 0ms
memory: 5780kb

input:

6 6 2
01

output:

448

result:

ok 1 number(s): "448"

Test #33:

score: 0
Accepted
time: 1ms
memory: 5748kb

input:

3 4 2
11

output:

13

result:

ok 1 number(s): "13"

Test #34:

score: 0
Accepted
time: 1ms
memory: 5716kb

input:

5 17 1
0

output:

4196

result:

ok 1 number(s): "4196"

Test #35:

score: 0
Accepted
time: 110ms
memory: 89656kb

input:

13 7 3
010

output:

38944

result:

ok 1 number(s): "38944"

Test #36:

score: 0
Accepted
time: 416ms
memory: 343576kb

input:

44 36 3
110

output:

707891542

result:

ok 1 number(s): "707891542"

Test #37:

score: 0
Accepted
time: 0ms
memory: 8916kb

input:

68 93 2
00

output:

208550386

result:

ok 1 number(s): "208550386"

Test #38:

score: 0
Accepted
time: 695ms
memory: 573188kb

input:

72 48 3
000

output:

248284289

result:

ok 1 number(s): "248284289"

Test #39:

score: 0
Accepted
time: 0ms
memory: 7832kb

input:

63 56 2
10

output:

19117488

result:

ok 1 number(s): "19117488"

Test #40:

score: 0
Accepted
time: 1ms
memory: 6016kb

input:

91 94 1
0

output:

537605296

result:

ok 1 number(s): "537605296"

Test #41:

score: 0
Accepted
time: 0ms
memory: 6124kb

input:

97 98 1
0

output:

246748278

result:

ok 1 number(s): "246748278"

Test #42:

score: 0
Accepted
time: 0ms
memory: 9464kb

input:

100 96 2
00

output:

710153430

result:

ok 1 number(s): "710153430"

Test #43:

score: 0
Accepted
time: 1ms
memory: 6092kb

input:

98 100 1
1

output:

238421873

result:

ok 1 number(s): "238421873"

Test #44:

score: 0
Accepted
time: 1ms
memory: 5592kb

input:

1 2 1
1

output:

3

result:

ok 1 number(s): "3"

Test #45:

score: 0
Accepted
time: 36ms
memory: 24356kb

input:

3 5 3
100

output:

12

result:

ok 1 number(s): "12"

Test #46:

score: 0
Accepted
time: 60ms
memory: 56888kb

input:

5 9 3
000

output:

346

result:

ok 1 number(s): "346"

Test #47:

score: 0
Accepted
time: 1ms
memory: 5816kb

input:

8 6 2
00

output:

239

result:

ok 1 number(s): "239"

Test #48:

score: 0
Accepted
time: 2ms
memory: 6784kb

input:

32 14 2
10

output:

187011318

result:

ok 1 number(s): "187011318"

Test #49:

score: 0
Accepted
time: 583ms
memory: 491268kb

input:

62 4 3
101

output:

208274892

result:

ok 1 number(s): "208274892"

Test #50:

score: 0
Accepted
time: 700ms
memory: 548452kb

input:

69 39 3
000

output:

96817189

result:

ok 1 number(s): "96817189"

Test #51:

score: 0
Accepted
time: 774ms
memory: 638516kb

input:

80 45 3
011

output:

382069581

result:

ok 1 number(s): "382069581"

Test #52:

score: 0
Accepted
time: 4ms
memory: 8884kb

input:

84 80 2
11

output:

587719309

result:

ok 1 number(s): "587719309"

Test #53:

score: 0
Accepted
time: 975ms
memory: 794124kb

input:

84 99 3
010

output:

113094014

result:

ok 1 number(s): "113094014"

Test #54:

score: 0
Accepted
time: 4ms
memory: 8916kb

input:

93 92 2
00

output:

188742816

result:

ok 1 number(s): "188742816"

Test #55:

score: 0
Accepted
time: 968ms
memory: 794176kb

input:

99 97 3
000

output:

960735653

result:

ok 1 number(s): "960735653"

Test #56:

score: 0
Accepted
time: 932ms
memory: 794140kb

input:

99 98 3
110

output:

791615843

result:

ok 1 number(s): "791615843"

Test #57:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

2 3 2
10

output:

4

result:

ok 1 number(s): "4"

Test #58:

score: 0
Accepted
time: 1ms
memory: 5592kb

input:

1 1 1
1

output:

1

result:

ok 1 number(s): "1"

Test #59:

score: 0
Accepted
time: 48ms
memory: 40504kb

input:

3 7 3
010

output:

63

result:

ok 1 number(s): "63"

Test #60:

score: 0
Accepted
time: 35ms
memory: 32320kb

input:

6 6 3
010

output:

270

result:

ok 1 number(s): "270"

Test #61:

score: 0
Accepted
time: 424ms
memory: 359996kb

input:

46 32 3
110

output:

652851792

result:

ok 1 number(s): "652851792"

Test #62:

score: 0
Accepted
time: 736ms
memory: 638776kb

input:

80 65 3
100

output:

341912944

result:

ok 1 number(s): "341912944"

Test #63:

score: 0
Accepted
time: 942ms
memory: 802300kb

input:

94 100 3
011

output:

104563592

result:

ok 1 number(s): "104563592"

Test #64:

score: 0
Accepted
time: 627ms
memory: 523828kb

input:

33 66 3
000

output:

626913525

result:

ok 1 number(s): "626913525"

Test #65:

score: 0
Accepted
time: 787ms
memory: 630328kb

input:

79 54 3
101

output:

292172159

result:

ok 1 number(s): "292172159"

Test #66:

score: 0
Accepted
time: 851ms
memory: 720480kb

input:

82 90 3
000

output:

543518579

result:

ok 1 number(s): "543518579"

Test #67:

score: 0
Accepted
time: 891ms
memory: 736816kb

input:

92 91 3
011

output:

482998725

result:

ok 1 number(s): "482998725"

Test #68:

score: 0
Accepted
time: 925ms
memory: 777952kb

input:

97 95 3
011

output:

415831105

result:

ok 1 number(s): "415831105"

Test #69:

score: 0
Accepted
time: 949ms
memory: 785868kb

input:

98 98 3
101

output:

605798638

result:

ok 1 number(s): "605798638"

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2025-01-21 01:54:23 | 开源项目