| 
Failed Wake Up Test
(...のはずが 384 位で通過しました... が、だめだと思って事前に作ってあったので残しときます:)
| 
static const ll MODVAL = 1000000007; ll MODADD(ll x, ll y) { return (x+y)%MODVAL; } ll MODSUB(ll x, ll y) { return (x-y+MODVAL)%MODVAL; } ll MODMUL(ll x, ll y) { return (x*y)%MODVAL; } ll MODPOW(ll x, ll e) { ll v = 1; for(;e;x=MODMUL(x,x),e>>=1) if(e&1) v = MODMUL(v, x); return v; } ll MODINV(ll x) { return MODPOW(x, MODVAL-2); } #define MAXN 10010 ll facts[MAXN]; ll inv_facts[MAXN]; ll MODCOMB(ll n, ll r) { assert(0<=n && n<MAXN); assert(0<=r && r<=n); return MODMUL(facts[n], MODMUL(inv_facts[r], inv_facts[n-r])); } int main() { facts[0] = 1; inv_facts[0] = MODINV(facts[0]); RANGE(i, 1, MAXN) facts[i] = MODMUL(facts[i-1], i); RANGE(i, 1, MAXN) inv_facts[i] = MODMUL(inv_facts[i-1], MODINV(i)); REP(i, MAXN) assert(MODMUL(facts[i], inv_facts[i])==1); int T; cin>>T; REP(ttt, T) { ll N, K; cin>>N>>K; VI w(N); REP(i, N) cin>>w[i]; sort(ALL(w)); ll ans = 0; REP(i, N) { if(i-(K-1)>=0) { //ans += MODMUL(w[i], MODCOMB(i, i-(K-1))); // だめ ans = MODADD(ans, MODMUL(w[i], MODCOMB(i, i-(K-1)))); // OK } } cout<<"Case #"<<ttt+1<<": "<<ans<<endl; } return 0; }
| 
/////////////////////// [OPTION] maximumFlow #define INF 1000000 typedef int Weight; struct Edge { int src, dst; Weight weight; Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) { } }; bool operator < (const Edge &e, const Edge &f) { return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef vector<Weight> Array; typedef vector<Array> Matrix; #define RESIDUE(s,t) (capacity[s][t]-flow[s][t]) Weight maximumFlow(const Graph &g, int s, int t) { int n = g.size(); Matrix flow(n, Array(n)), capacity(n, Array(n)); REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight; Weight total = 0; while (1) { queue<int> Q; Q.push(s); vector<int> prev(n, -1); prev[s] = s; while (!Q.empty() && prev[t] < 0) { int u = Q.front(); Q.pop(); FOR(e,g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) { prev[e->dst] = u; Q.push(e->dst); } } if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side Weight inc = INF; for (int j = t; prev[j] != j; j = prev[j]) inc = min(inc, RESIDUE(prev[j], j)); for (int j = t; prev[j] != j; j = prev[j]) flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc; VI path; for (int j = t; prev[j] != j; j = prev[j]) path.push_back(j); path.push_back(s); reverse(ALL(path)); total += inc; // cout<<"Update "<<path<<" -> total "<<total<<endl; } } void add_edge(Graph& g, int s, int e, int w) { g[s].push_back(Edge(s, e, w)); g[e].push_back(Edge(e, s, 0)); } /////////////////////// maximumFlow ll N, M, L; string K1, K2; int check() { Graph g(M*2+2, Edges()); int S=M*2, E=M*2+1; REP(i, M) { add_edge(g, S, i, 1); add_edge(g, M+i, E, 1); } // i in K1, j in K2 REP(i, M) REP(j, M) { int lok=1; REP(li, L) { char a=K1[i*L+li], b=K2[j*L+li]; if(!(a=='?' || b=='?') && a!=b) lok=0; } if(lok) add_edge(g, i, M+j, 1); } int flow = maximumFlow(g, S, E); return flow==M; } int main() { int T; cin>>T; REP(ttt, T) { cin>>M; cin>>K1>>K2; N=K1.size(); L=N/M; int gok=1; REP(ci, N) { if(K1[ci]=='?') { int ok=0; REP(cand, 6) { K1[ci]=cand+'a'; if(check()) {ok=1;break;} } if(!ok) {gok=0;break;} } } if(!check()) gok=0; if(gok) { cout<<"Case #"<<ttt+1<<": "<<K1<<endl; } else { cout<<"Case #"<<ttt+1<<": IMPOSSIBLE"<<endl; } } return 0; }
| 
// X in [x0, x1] // Y in [y0, y1] struct Rect { int x0, y0, x1, y1; bool operator<(const Rect& o) const { return x0<o.x0; } }; ostream& operator<<(ostream& os, const Rect& r) { os<<"[Rect "<<r.x0<<" "<<r.y0<<" "<<r.x1<<" "<<r.y1<<" ]"; return os; } int W, H, P, Q, N, X, Y, A, B, C, D; int foo() { vector<Rect> rects(N); int x=X, y=Y; REP(i, N) { Rect r = (Rect){x-(P-1), y-(Q-1), x, y}; r.x0 = max(r.x0, 0); r.y0 = max(r.y0, 0); r.x1 = min(r.x1, W-1); r.y1 = min(r.y1, H-1); rects[i] = r; int nx = (x * A + y * B + 1) % W; int ny = (x * C + y * D + 1) % H; x = nx; y = ny; } sort(ALL(rects)); // cout<<rects<<endl; ll ng = 0; VI line(H); int ri=0; REP(scanx, W-P+1) { REP(y, H-Q+1) line[y] = max(line[y]-1, 0); for(;ri<N && rects[ri].x0==scanx;ri++) { int wi = rects[ri].x1 - rects[ri].x0 + 1; RANGE(y, rects[ri].y0, rects[ri].y1+1) { line[y] = max(line[y], wi); } } REP(y, H-Q+1) ng += line[y] ? 1 : 0; } int ans = (W-P+1)*(H-Q+1) - ng; return ans; } int main() { int T; cin>>T; REP(ttt, T) { cin>>W>>H>>P>>Q>>N>>X>>Y>>A>>B>>C>>D; int r1 = foo(); cout<<"Case #"<<ttt+1<<": "<<r1<<endl; } return 0; }
