Submission #4036015
Source Code Expand
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;
auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
const mod = 10^^9+7;
alias mint = FactorRing!mod;
void main()
{
int h, w, k; readV(h, w, k);
int[] b;
loop: foreach (i; 0..1<<(w-1)) {
foreach (j; 0..w-2)
if (i.bitTest(j) && i.bitTest(j+1))
continue loop;
b ~= i;
}
auto dp = new mint[][](h+1, w);
dp[0][0] = 1;
foreach (i; 0..h)
foreach (j; 0..w)
foreach (bi; b) {
if (j > 0 && bi.bitTest(j-1)) dp[i+1][j-1] += dp[i][j];
else if (j < w-1 && bi.bitTest(j)) dp[i+1][j+1] += dp[i][j];
else dp[i+1][j] += dp[i][j];
}
writeln(dp[h][k-1]);
}
pragma(inline) {
pure bool bitTest(T)(T n, size_t i) { return (n & (T(1) << i)) != 0; }
pure T bitSet(T)(T n, size_t i) { return n | (T(1) << i); }
pure T bitReset(T)(T n, size_t i) { return n & ~(T(1) << i); }
pure T bitComp(T)(T n, size_t i) { return n ^ (T(1) << i); }
pure T bitSet(T)(T n, size_t s, size_t e) { return n | ((T(1) << e) - 1) & ~((T(1) << s) - 1); }
pure T bitReset(T)(T n, size_t s, size_t e) { return n & (~((T(1) << e) - 1) | ((T(1) << s) - 1)); }
pure T bitComp(T)(T n, size_t s, size_t e) { return n ^ ((T(1) << e) - 1) & ~((T(1) << s) - 1); }
import core.bitop;
pure int bsf(T)(T n) { return core.bitop.bsf(ulong(n)); }
pure int bsr(T)(T n) { return core.bitop.bsr(ulong(n)); }
pure int popcnt(T)(T n) { return core.bitop.popcnt(ulong(n)); }
}
struct FactorRing(int m, bool pos = false)
{
version(BigEndian) union { long vl; struct { int vi2; int vi; } } else union { long vl; int vi; }
alias FR = FactorRing!(m, pos);
@property static init() { return FR(0); }
@property int value() { return vi; }
@property void value(int v) { vi = mod(v); }
alias value this;
this(int v) { vi = v; }
this(int v, bool runMod) { vi = runMod ? mod(v) : v; }
this(long v) { vi = mod(v); }
ref auto opAssign(int v) { vi = v; return this; }
pure auto mod(int v) const { static if (pos) return v%m; else return (v%m+m)%m; }
pure auto mod(long v) const { static if (pos) return cast(int)(v%m); else return cast(int)((v%m+m)%m); }
static if (!pos) pure ref auto opUnary(string op: "-")() { return FR(mod(-vi)); }
static if (m < int.max / 2) {
pure ref auto opBinary(string op)(int r) if (op == "+" || op == "-") { return FR(mod(mixin("vi"~op~"r"))); }
ref auto opOpAssign(string op)(int r) if (op == "+" || op == "-") { vi = mod(mixin("vi"~op~"r")); return this; }
} else {
pure ref auto opBinary(string op)(int r) if (op == "+" || op == "-") { return FR(mod(mixin("vl"~op~"r"))); }
ref auto opOpAssign(string op)(int r) if (op == "+" || op == "-") { vi = mod(mixin("vl"~op~"r")); return this; }
}
pure ref auto opBinary(string op: "*")(int r) { return FR(mod(vl*r)); }
ref auto opOpAssign(string op: "*")(int r) { vi = mod(vl*r); return this; }
pure ref auto opBinary(string op)(ref FR r) if (op == "+" || op == "-" || op == "*") { return opBinary!op(r.vi); }
ref auto opOpAssign(string op)(ref FR r) if (op == "+" || op == "-" || op == "*") { return opOpAssign!op(r.vi); }
}
Submission Info
Submission Time |
|
Task |
D - Number of Amidakuji |
User |
tesh |
Language |
D (DMD64 v2.070.1) |
Score |
400 |
Code Size |
3387 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt |
All |
in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt |
Case Name |
Status |
Exec Time |
Memory |
in01.txt |
AC |
1 ms |
256 KB |
in02.txt |
AC |
1 ms |
256 KB |
in03.txt |
AC |
1 ms |
256 KB |
in04.txt |
AC |
1 ms |
256 KB |
in05.txt |
AC |
1 ms |
256 KB |
in06.txt |
AC |
1 ms |
256 KB |
in07.txt |
AC |
1 ms |
256 KB |
in08.txt |
AC |
1 ms |
256 KB |
in09.txt |
AC |
1 ms |
256 KB |
in10.txt |
AC |
1 ms |
256 KB |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
sample_04.txt |
AC |
1 ms |
256 KB |
sample_05.txt |
AC |
1 ms |
256 KB |
sample_06.txt |
AC |
1 ms |
256 KB |