列表

详情

NC252840. Indivisible Partition

描述

Eva defines a string S with length n (indexed from 0 to n-1 ) is divisible if:
Here S_i denotes the character of S with index i , for example, let S= abcde then S_0= a and S_1= b.
Then, Eva defines a string S is indivisible if S is not divisible.
For example, string abcde or string a is indivisible, but string aa is not indivisible.

Colin defines an indivisible partition of a string S with length n as a series of integers \{p_1,p_2,\dots,p_k\}\ (k \ge 2) satisfying:
Here S[l:r] denotes the substring of S with index form l to r , for example, let S= abcde then S[1:3]= bcd .

Given a string S , please count the number of different indivisible partitions of S module 998244353.
We consider two indivisible partitions \{p_1,p_2,\dots,p_{k_1}\},\{p_1',p_2',\dots,p_{k_2}'\} are different if k_1\not =k_2 , or there exists an integer i\in[1, k_1] satisfies p_i\not = p_i' .

Please note the unusual memory limit.

输入描述

The first line contains a string S\ (1 \le|S|\le 5\times 10^3) consisting of lowercase letters, representing the given string.

输出描述

A single integer, represents the number of different indivisible partitions of string S module 998244353.

示例1

输入: 

aab

输出: 

3

说明:

the 3 different indivisible partitions of aab are:

1. \{0,1,2,3\} , the string is divided into a + a + b
2. \{0,1,3\} , the string is divided into a + ab
3. \{0,3\} , the string aab itself meets the definition of indivisible.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

Java 解法, 执行用时: 451ms, 内存消耗: 15644K, 提交时间: 2023-06-06 18:13:53 

import java.util.*;

public class Main {
static final int p=998244353, N=5011;

static int add(int a,int b){
    return (a+=b)>=p?a-p:a;
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String s = scan.next();
    int n = s.length();
    s = " " + s;

    int[] a = new int[N];
    int[] f = new int[N];
    BitSet[] ok = new BitSet[N];

    for (int i = 1; i <= n; ++i) {
        ok[i] = new BitSet(N);
        Arrays.fill(ok[i].toLongArray(), 0);
    }

    for (int l = 1; l <= n; ++l) {
        int j = a[0] = 0;
        ok[l].set(l, false);

        for (int i = 1; i <= n - l; ++i) {
            while (j > 0 && s.charAt(l + i) != s.charAt(l + j)) {
                j = a[j - 1];
            }
            a[i] = s.charAt(l + i) == s.charAt(l + j) ? j + 1 : 0;
            j = a[i];
            ok[l].set(l + i, a[i] > 0 && (i + 1) % ((i + 1) - a[i]) == 0);
        }
    }

    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (!ok[j + 1].get(i)) {
                f[i] = add(f[i], f[j]);
            }
        }
    }

    System.out.println(f[n]);
    scan.close();
}
}

C++(clang++ 11.0.1) 解法, 执行用时: 132ms, 内存消耗: 460K, 提交时间: 2023-07-01 14:07:01 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e3+10;
const int MOD=998244353;
char s[maxn];
int fail[maxn];
int dp[maxn];
int n;
int main() {
	scanf("%s",s);
	n=strlen(s);
	dp[n]=1;
	for(int i=n-1;i>=0;i--)
	{
		char*f=s+i;
		int m=n-i;
		int k=0;
		fail[0]=0;
		dp[i]=dp[i+1];
		for(int j=1;j<m;j++)
		{
			while(k!=0&&f[j]!=f[k]) k=fail[k-1];
			if(f[k]==f[j]) k++;
			fail[j]=k;
			if(fail[j]==0||(j+1)%(j+1-fail[j])!=0)
				dp[i]=(dp[i]+dp[i+j+1])%MOD;
		}
	}
//	for(int i=0;i<n;i++)
	printf("%d\n",dp[0]);
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 92ms, 内存消耗: 568K, 提交时间: 2023-07-13 23:23:59 

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e3+10;
const int MOD=998244353;
string s;
int fail[maxn];
int dp[maxn];
int n,k;
int main(){
	cin>>s;
	n=s.length();
	dp[n]=1;
	for(int i=n-1;i>=0;i--){
		char*f=&s[i];
		k=0;
		dp[i]=dp[i+1];
		for(int j=1;j<n-i;j++){
			while(k!=0&&f[j]!=f[k]) k=fail[k-1];
			if(f[k]==f[j]) k++;
			fail[j]=k;
			if(fail[j]==0||(j+1)%(j+1-fail[j])!=0)
				dp[i]=(dp[i]+dp[i+j+1])%MOD;
		}
	}
	printf("%d",dp[0]);
	return 0;
}

上一题

© 2024 nowcoder.com