ログインしてください。
提出 #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 | ||||
| 結果 |
|
|
| セット名 | テストケース |
|---|---|
| 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 |