| 
(しばらく)
5 = 2^0 * 3^0 * 5^1 を 5 : 0 0 1 と表すと 5 : 0 0 1 6 : 1 1 0 15 : 0 1 1 // 5, 6 からは作れないので根源的とすべきだがそう判定されない
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
set<int> h(vector<int>& A) {
set<int> s;
REP(i, A.size()) {
ll l = 1;
REP(j, A.size()) {
if(A[j]<A[i] && lcm(A[i], A[j])==A[i]) l=lcm(l, A[j]);
}
if(l < A[i]) s.insert(A[i]);
}
return s;
}
class LCMSet {
public:
string equal(vector <int> A, vector <int> B) {
return h(A)==h(B) ? "Equal":"Not equal";
}
};
| 
class TheMatrix { public: int MaxArea(vector <string> B) { int W=B[0].size(); int H=B.size(); Sum2D<ll> sum(W, H); // ライブラリ乙 REP(x, W) REP(y, H) sum.data[y][x] = B[y][x]-'0'; REP(x, W) REP(y, H) if((x+y)%2) sum.data[y][x]^=1; sum.prepare(); int ans = 0; REP(x, W) REP(y, H) RANGE(x2, x, W) RANGE(y2, y, H) { int w = x2-x+1; int h = y2-y+1; ll s = sum.sum(x, y, x2+1, y2+1); if(s==0 || s==w*h) ans=max(ans, w*h); } return ans; } };
| 
int main() { ios::sync_with_stdio(false); ll N, M, v, T, L, R; while(cin>>N) { SegTree<Gcd> st(N+1); SegTree<Add> cum(N+1); VI cur(N), diff(N+1); REP(i, N) { cin>>v; cur[i] = v; } diff[0]=cur[0]; cum.update(0, diff[0]); RANGE(i, 1, N) { diff[i]=cur[i]-cur[i-1]; cum.update(i, diff[i]); st.update(i, diff[i]); } cin>>M; REP(i, M) { cin>>T>>L>>R; L--; R--; if(T==0) { ll head = cum.query(0, L+1); ll v = st.query(L+1, R+1); cout<<Gcd::op(head, v)<<endl; } else { diff[L] += T; diff[R+1] -= T; st.update(L, diff[L]); st.update(R+1, diff[R+1]); cum.update(L, diff[L]); cum.update(R+1, diff[R+1]); } } } return 0; }
| 
double dp[5010][5010]; // dp[a][b] ... s[a, b]が回文になる確率 class PalindromicSubstringsDiv1 { public: double expectedPalindromes(vector <string> S1, vector <string> S2) { CLEAR(dp, 0); string s = accumulate(ALL(S1), string(""))+accumulate(ALL(S2), string("")); int N=s.size(); double ans=0; RANGE(L, 1, N+1) REP(i, N-L+1) { char a=s[i], b=s[i+L-1]; double lans=1.0/26; if(L==1) lans=1.0; else { if(a!='?' && b!='?' && a==b) lans = 1.0; if(a!='?' && b!='?' && a!=b) lans = 0.0; } double inner = L<=2 ? 1.0 : dp[i+1][i+L-1-1]; dp[i][i+L-1] = lans * inner; ans += dp[i][i+L-1]; } return ans; } };
| 
// めんどくさい bool isNum(const string& s, int& idx, int limit, int& out) { if(idx>=limit) return false; if(!isdigit(s[idx])) return false; out=0; int read=0; while(idx<limit && isdigit(s[idx])) { out=out*10+(s[idx]-'0'); idx++; read++; } if(out==0 && read>1) return false; return true; } string realAns; // めんどくさい bool valid2(const string& s, int limit, bool final=false) { int idx=0; int v; if(idx>=limit) return !final; if(!isNum(s, idx, limit, v)) return false; if(!(1<=v&&v<=200)) return false; if(idx>=limit) return !final; if(s[idx++]!=0x0a) return false; int loop = v; stringstream ans; REP(i, loop) { int a, b; if(idx>=limit) return !final; if(!isNum(s, idx, limit, v)) return false; if(!(1<=v&&v<=10)) return false; if(idx>=limit) return !final; if(s[idx++]!=' ') return false; a=v; if(idx>=limit) return !final; if(!isNum(s, idx, limit, v)) return false; if(!(1<=v&&v<=10)) return false; if(idx>=limit) return !final; if(s[idx++]!=0x0a) return false; b=v; ans<<"ans.PB("<<(a^b)<<");"; } if(final && idx!=limit) return false; if(final) realAns = ans.str(); return true; } VVI w; string src, validAns; int cur[128]; int L=128; VVI ans; void dfs(int idx) { if(validAns.size()) return; if(idx==ans.size()) { string ss=src; REP(j, ss.size()) ss[j]^=ans[j%L][cur[j%L]]; if(valid2(ss, ss.size(), true)) { cout<<"//Found valid ans "<<endl; validAns=ss; } return; } REP(i, ans[idx].size()) { cur[idx]=i; bool go=true; { string ss=src; REP(j, ss.size()) ss[j]^=ans[j%L][cur[j%L]]; if(!valid2(ss, idx+1)) go=false; } if(go) dfs(idx+1); } } bool validChars(const VI& s) { int cnt=0; REP(i, s.size()) { if(isdigit(s[i]) || s[i]==' ' || s[i]==0x0a) cnt++; } return cnt==s.size(); } int main(int argc, char**argv) { //ios::sync_with_stdio(false); int c; string s; int co=0; FILE* fin = fopen(argv[1], "rb"); w = VVI(L, VI()); while((c=fgetc(fin))!=EOF) { w[co%L].PB(c); s.PB(c); co++; } src=s; ans = VVI(L, VI()); REP(l, L) { REP(a, 256) { VI ss=w[l]; REP(i, ss.size()) ss[i] = (ss[i] ^ a) & 0xFF; if(validChars(ss)) ans[l].PB(a); } } dfs(0); cout<<realAns<<endl; return 0; }
