結果

A,B,CはAC。Dは今朝AC。プログラミングの才能がない・・・

A - Harmony

条件を満たすKはAとBの中間点。これが整数になるのはA,Bがともに偶数or奇数の場合。

B - 0 or 1 Swap

入れ替えで動かせるのは2個。ということは整列済みのものと比較して相違が2個なら1回の入れ替えで昇順にすることができる。入れ替え不要(最初から整列済み)の場合を忘れずに*1。

C - City Savers

なるべくほかの勇者と被らないように討伐する。端っこから考えていけばいい。勇者Nは街N+1を討伐した後に街Nを討伐。勇者N-1は街Nを討伐した後に街N-1を討伐…。勇者1は街1を討伐した後に…でもよし。

討伐数は最大 $10^{9}*10^{5}$ とintの範囲を超えるのでlongを使おう*2。

D - Digits Parade

とりあえず?が0の場合の $\mod 13$ を求めてみる(入力例1なら $2005 \mod 13$ )
とりあえず $10^{n} \mod 13$ を求めてみる

1.と2.を合わせて $\mod 13=5$ となるようにできれば良いのではないか？最上位桁から考えて…DPっぽい？というところまでは気付いたけどこの後なぜか $10^{n}$ の逆元を求め始めるなど迷走して時間切れ。

方針

最上位桁から $\mod 13$ を計算し、結果ごと( $0,1,2,\cdots,12$ )にカウントする。
$dp[i,j]$ :最上位から $i$ 桁目までで, $\mod13$ の結果が $j$ となるものの数。

$j*10^{|S|-i} \mod 13=x: \,1\gt j \gt 9$ に対して $x=0,1,\cdots,12$ となるものを数える。

var tmp = new long[mod];
for (var j = 1; j < 10; ++j)
{
    var num = (xor10[S.Length - i] * j) % mod;//(10^(|S|-i) mod 13) * j mod 13
    tmp[num]++;//同じ値が出てくることはないので=1でも良い
}

上位桁が全て0の場合、そのまま加算

for (var j = 0; j < mod; ++j)
{
    dp[i, j] += tmp[j];
}

上位桁が全て0ではない場合、これまでの結果と組み合わせる。 $j*10^{|S|-i} \mod 13$ で $j=0$ の場合もここで加算しておく。

for (var j = 0; j < mod; ++j)
{
    dp[i, j] += dp[i - 1, j];
    for (var k = 0; k < mod; ++k)
    {
        dp[i, (j + k) % mod] += dp[i - 1, j] * tmp[k];
    }
}

※?でない場合は一つ前の結果を持ち越し

if ('?' != S[i - 1])
{
    for (var k = 0; k < mod; ++k)
    { dp[i, k] = dp[i - 1, k]; }
    continue;
}

最後にすべて0の場合を加算

dp[S.Length, 0]++;

?を全部0とした場合の $\mod13$ (numxor)と合わせて5になるものを出力。

WriteLine(dp[S.Length, (5 - numxor + mod) % mod] % Mod);

$10^{n} \mod 13!=0$ を利用すればもうちょっとまとめられる

var dp = new long[S.Length + 1, mod];
for (var i = 1; i <= S.Length; ++i)
{
    if ('?' != S[i - 1])
    {
        for (var k = 0; k < mod; ++k)
        { dp[i, k] = dp[i - 1, k]; }
        continue;
    }
    var tmp = new long[mod];
    for (var j = 0; j < 10; ++j)
    { tmp[(xor10[S.Length - i] * j) % mod] = 1; }
    for (var j = 0; j < mod; ++j)
    {
        for (var k = 0; k < mod; ++k)
        { dp[i, (j + k) % mod] += dp[i - 1, j] * tmp[k]; }
    }
    for (var j = 1; j < mod; ++j)
    { dp[i, j] = (dp[i, j] + tmp[j]) % Mod; }
}
dp[S.Length, 0]++;
WriteLine(dp[S.Length, (5 - numxor + mod) % mod] % Mod);