Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import sys
MOD = 1000000007
def main():
for (i, (n, k, cards)) in enumerate(testcases()):
print "Case #{0}: {1}".format(i+1, subsum(n, k, cards))
def testcases(cin=sys.stdin):
m = int(cin.next())
for _ in xrange(m):
n, k = map(int, cin.next().split())
cards = map(int, cin.next().split())
yield (n, k, cards)
def subsum(n, k, cards):
ans = 0
cards.sort()
for i in xrange(k-1, n):
ans += cards[i] * choose(i, k-1)
ans %= MOD
return ans
MAX_S = 10000
FACTS = [1]
for i in xrange(1, 1+MAX_S):
FACTS.append((FACTS[-1]*i) % MOD)
def choose(n, k):
return (FACTS[n]*modInv(FACTS[k]*FACTS[n-k])) % MOD
def modInv(a):
x, nx, b = 0, 1, MOD
while a > 0:
q = b // a
nx, x = x-q*nx, nx
a, b = b-q*a, a
return x
if __name__ == "__main__": sys.exit(main())
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> VI;
// so lazy! (64-bit req. to do this)
int main() {
int nc; cin >> nc;
for (int cNum = 1; cNum <= nc; ++cNum) {
int w, h, p, q, n; cin >> w >> h >> p >> q >> n;
int x, y, a, b, c, d; cin >> x >> y >> a >> b >> c >> d;
vector<VI> screen(w+1, VI(h+1));
for (int i = 0; i < n; ++i) {
screen[x][y] = 1;
int tx = (x*a + y*b + 1) % w;
int ty = (x*c + y*d + 1) % h;
x = tx; y = ty;
}
int pCount = 0;
for (int i = w-1; i >= 0; --i)
for (int j = h-1; j >= 0; --j) {
screen[i][j] += screen[i+1][j] + screen[i][j+1] - screen[i+1][j+1];
if ((i+p <= w) && (j+q <= h) && (screen[i][j] == screen[i+p][j] + screen[i][j+q] - screen[i+p][j+q]))
++pCount;
}
cout << "Case #" << cNum << ": " << pCount << '\n';
}
}
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VP;
// use sentinels to simplify sweep?
int process(int h, int q, const map<int, int> &activeY) {
int ret = 0, last = 0;
for (map<int, int>::const_iterator i = activeY.begin(); i != activeY.end(); ++i) {
ret += max(0, i->first-last-q+1);
last = i->first+1;
}
ret += max(0, h-last-q+1);
return ret;
}
int main() {
int nc; cin >> nc;
for (int cNum = 1; cNum <= nc; ++cNum) {
int w, h, p, q, n; cin >> w >> h >> p >> q >> n;
int x, y, a, b, c, d; cin >> x >> y >> a >> b >> c >> d;
VP dead(n); dead[0] = PII(x, y);
for (int i = 1; i < n; ++i) {
dead[i].first = (dead[i-1].first*a + dead[i-1].second*b + 1) % w;
dead[i].second = (dead[i-1].first*c + dead[i-1].second*d + 1) % h;
}
sort(dead.begin(), dead.end()); // duplicates are OK
map<int,int> activeY;
VP::const_iterator rP = dead.begin();
VP::const_iterator lP = dead.begin();
int curL = 0;
while ((rP != dead.end()) && (rP->first < curL+p)) {
++activeY[rP->second];
++rP;
}
int pCount = 0, curC = process(h, q, activeY);
while ((rP != dead.end()) || ((lP != dead.end()) && (lP->first < w-p))) {
int nxtLR = (rP != dead.end()) ? rP->first-p : w;
int nxtLL = (lP != dead.end()) ? lP->first : w;
int nxtL = min(nxtLR, nxtLL) + 1;
pCount += curC*(nxtL-curL);
curL = nxtL;
while ((rP != dead.end()) && (rP->first < curL+p)) {
++activeY[rP->second];
++rP;
}
while ((lP != dead.end()) && (lP->first < curL)) {
--activeY[lP->second];
if (!activeY[lP->second]) activeY.erase(lP->second);
++lP;
}
curC = process(h, q, activeY);
}
pCount += curC*(w-p+1-curL);
cout << "Case #" << cNum << ": " << pCount << '\n';
}
}
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef vector<int> VI;
bool augment(int m, const vector<VI> &edgeL, vector<int> &match) {
queue<int> q;
VI pred(2*m, -1);
for (int i = 0; i < m; ++i)
if (match[i] == -1)
q.push(i);
while (!q.empty()) {
int qL = q.size();
while (qL--) {
int t = q.front(); q.pop();
for (VI::const_iterator i = edgeL[t].begin(); i != edgeL[t].end(); ++i)
if (pred[m+*i] == -1) {
pred[m+*i] = t;
q.push(*i);
}
}
qL = q.size();
while (qL--) {
int t = q.front(); q.pop();
if (match[m+t] == -1) {
int v = m+t;
while (v != -1) {
match[v] = pred[v];
match[pred[v]] = v;
v = pred[pred[v]];
}
return true;
}
else {
pred[match[m+t]] = m+t;
q.push(match[m+t]);
}
}
}
return false;
}
int bipart(int m, const vector<VI> &edgeL) {
vector<int> match(2*m, -1);
int mSize = 0;
while ((mSize < m) && augment(m, edgeL, match)) ++mSize;
return mSize;
}
bool compat(int m, const string &k1, const string &k2, int a, int b) {
int sL = k1.size() / m;
for (int k = 0; k < sL; ++k) {
int i = sL*a + k, j = sL*b + k;
if ((k1[i] != '?') && (k2[j] != '?') && (k1[i] != k2[j]))
return false;
}
return true;
}
string solve(int m, string k1, const string &k2) {
vector<VI> edgeL(m);
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j)
if (compat(m, k1, k2, i, j))
edgeL[i].push_back(j);
if (bipart(m, edgeL) != m) return "IMPOSSIBLE";
int sL = k1.size() / m;
for (int i = 0; i < m; ++i)
for (int k = 0; k < sL; ++k)
if (k1[sL*i+k] == '?') {
char &c = k1[sL*i+k];
VI pEdge = edgeL[i];
for (c = 'a'; c <= 'f'; ++c) {
edgeL[i].clear();
for (VI::const_iterator j = pEdge.begin(); j != pEdge.end(); ++j)
if (compat(m, k1, k2, i, *j))
edgeL[i].push_back(*j);
if (bipart(m, edgeL) == m) break;
}
}
return k1;
}
int main() {
int nc; cin >> nc;
for (int cNum = 1; cNum <= nc; ++cNum) {
int m; cin >> m;
string k1, k2; cin >> k1 >> k2;
cout << "Case #" << cNum << ": " << solve(m, k1, k2) << '\n';
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.