提出 #1978387


ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
#define mod 998244353
#define pb push_back
using namespace std;

int n; char s[109]; vector<int> a;
map<pair<vector<int>,bool>,int> mp;
int solve(vector<int> a,bool flag){
	int n=a.size();
	pair<vector<int>,bool> now=make_pair(a,flag);
	if (!n) return 1; if (n==1) return a[0]+1;
	if (mp.count(now)) return mp[now];
	int i,j,k,tmp,ans=0; vector<int> b,c;
	b.clear(); b.pb(a[0]);
	ans=solve(b,0);
	b.clear();
	for (i=1; i<n; i++) b.pb(a[i]);
	ans=(ll)ans*solve(b,0)%mod;
	for (i=1; i<=(n>>1); i++){
		b.clear();
		for (j=0; j<i; j++) b.pb(1);
		for (j=1; i*j<=n; j++){
			//if (i*j==n && flag) break;
			for (k=0; k<i; k++) b[k]&=a[i*(j-1)+k];
			if (j>1){
				tmp=solve(b,0);
				c.clear();
				for (k=i*j; k<n; k++) c.pb(a[k]);
				ans=(ans+(ll)tmp*solve(c,0))%mod;
			}
		}
	}
	
	mp[now]=ans; return ans;
}
int main(){
	scanf("%s",s+1); n=strlen(s+1);
	int i;
	for (i=1; i<=n; i++) a.pb(s[i]-'0');
	printf("%d\n",solve(a,0));
	return 0;
}

提出情報

提出日時
問題 E - Encoding Subsets
ユーザ miaom
言語 C++14 (GCC 5.4.1)
得点 1400
コード長 1029 Byte
結果 AC
実行時間 1914 ms
メモリ 7680 KiB

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:38:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1); n=strlen(s+1);
                 ^

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 1400 / 1400
結果
AC × 4
AC × 44
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 1 ms 256 KiB
sample_02.txt AC 1 ms 256 KiB
sample_03.txt AC 1 ms 256 KiB
sample_04.txt AC 3 ms 256 KiB
subtask_1_01.txt AC 1 ms 256 KiB
subtask_1_02.txt AC 1 ms 256 KiB
subtask_1_03.txt AC 1 ms 256 KiB
subtask_1_04.txt AC 1 ms 256 KiB
subtask_1_05.txt AC 1 ms 256 KiB
subtask_1_06.txt AC 1 ms 256 KiB
subtask_1_07.txt AC 1 ms 256 KiB
subtask_1_08.txt AC 1 ms 256 KiB
subtask_1_09.txt AC 1 ms 256 KiB
subtask_1_10.txt AC 6 ms 256 KiB
subtask_1_11.txt AC 9 ms 384 KiB
subtask_1_12.txt AC 77 ms 768 KiB
subtask_1_13.txt AC 51 ms 640 KiB
subtask_1_14.txt AC 72 ms 768 KiB
subtask_1_15.txt AC 47 ms 512 KiB
subtask_1_16.txt AC 872 ms 3584 KiB
subtask_1_17.txt AC 1004 ms 4480 KiB
subtask_1_18.txt AC 1075 ms 3968 KiB
subtask_1_19.txt AC 1675 ms 6400 KiB
subtask_1_20.txt AC 23 ms 384 KiB
subtask_1_21.txt AC 22 ms 384 KiB
subtask_1_22.txt AC 92 ms 512 KiB
subtask_1_23.txt AC 23 ms 384 KiB
subtask_1_24.txt AC 68 ms 512 KiB
subtask_1_25.txt AC 28 ms 384 KiB
subtask_1_26.txt AC 74 ms 512 KiB
subtask_1_27.txt AC 1660 ms 6400 KiB
subtask_1_28.txt AC 1723 ms 6784 KiB
subtask_1_29.txt AC 1808 ms 7168 KiB
subtask_1_30.txt AC 1598 ms 6144 KiB
subtask_1_31.txt AC 1687 ms 6400 KiB
subtask_1_32.txt AC 1914 ms 7680 KiB
subtask_1_33.txt AC 1884 ms 7680 KiB
subtask_1_34.txt AC 1900 ms 7680 KiB
subtask_1_35.txt AC 1908 ms 7680 KiB
subtask_1_36.txt AC 1898 ms 7680 KiB