Wireless Password HDU - 2825 AC 로봇 DP 개수

m개의 단어를 주고 구조가 n이고 적어도 k개의 단어를 포함하는 열의 종류를 묻는다
소박한 자동기에서 DP는 자동기의 모든 상태를 두루 훑어보았습니다. dp[i][j][k]: 길이가 i인 직렬이 상태 j에 일치하고 k 인코딩 상태word의 직렬이 나타나는 종류입니다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define FOR(a) for(int i=1;i<=a;i++)
const int inf=0x3f3f3f3f;
const int maxn=140+9; 
const int mod=20090717;

const int sigma=26;

int n,m,k;

int dp[30][110][1<<10];	
//dp[i][j][k]:   i       j，   k  word    
int num[5005];	//num[i]:i        1 

struct automata{
	int ch[maxn][sigma];
	int val[maxn];
	int f[maxn];
	int sz;

	int newnode(){
		memset(ch[sz],0,sizeof(ch[sz]));
		f[sz]=val[sz]=0;
		return sz++;
	}

	void init(){
		memset(val,0,sizeof(val));
		sz=0;
		newnode();
	}

	void insert(char *s,int v){	
		int u=0;
		int len=strlen(s);
		for(int i=0;iq;
		q.push(0);	
		while(!q.empty()){
			int u=q.front();q.pop();

			val[u]|=val[f[u]];

			for(int i=0;i0){
						for(int c=0;c<26;c++){
							int nxti=i+1;
							int nxtj=ch[j][c];
							int nxtp=(p|val[nxtj]);
							dp[nxti][nxtj][nxtp]+=dp[i][j][p];
							dp[nxti][nxtj][nxtp]%=mod;
						}
					}
				}
			}
		}
		int ans=0;
		for(int p=0;p

Wireless Password HDU - 2825 AC 로봇 DP 개수

좋은 웹페이지 즐겨찾기