<div class="solution-view">
    <div class="row">
        <div class="col-md-6">
            <p>提交时间：2026-06-14 13:48:11</p>
        </div>
        <div class="col-md-6">
            <p>运行 ID: <a href="/solution/detail?id=91641">91641</a></p>
        </div>
    </div>
    <div class="pre"><p>#include &lt;bits/stdc++.h&gt;
using namespace std;

typedef long long ll;
const int maxn = 263000;

int n, k, str, lim;
char s[20], t[20];
int fl[64][maxn], fr[64][maxn];
ll res[64][maxn], m;
int mat[20][2][2], nx[maxn][2][2], popcnt[maxn];

int mult(int st, bool o1, bool o2)
{
    int ans = 0;
    for (int i = 0; i &lt; n; i++) ans |= ((popcnt[st &amp; mat[i][o1][o2]] &amp; 1) &lt;&lt; i);
    return ans;
}

int RE, FL, FR;
void calc(ll nw, int len)
{
    RE = FL = FR = 0;
    for (int j = 1; j &lt; k &amp;&amp; j &lt;= len; j++)
    {
        ll x = nw &amp; ((1 &lt;&lt; j) - 1);
        ll y = (str &amp; (((1 &lt;&lt; j) - 1) &lt;&lt; (k - j))) &gt;&gt; (k - j);
        if (x == y) FL |= (1 &lt;&lt; j);
    }
    for (int j = 0; j &lt; k - 1 &amp;&amp; j &lt; len; j++)
    {
        ll x = nw &gt;&gt; (len - j - 1);
        ll y = str &amp; ((1 &lt;&lt; (j + 1)) - 1);
        if (x == y) FR |= (1 &lt;&lt; (k - j - 1));
    }
    for (int j = k; j &lt;= len; j++)
    {
        ll x = (nw &gt;&gt; (len - j));
        x &amp;= ((1 &lt;&lt; k) - 1);
        if (x == str) RE++;
    }
}

ll work(ll x)
{
    if (x &lt; k - 1) return 0; x++;
    int st = 1;
    int rs = 0, ln = 0;
    ll nw = 0, ans = 0;
    for (int i = lim; ~i; i--)
    {
        if (!((x &gt;&gt; i) &amp; 1)) st = nx[st][(m &gt;&gt; i) &amp; 1][0];
        else
        {
            int ls = nx[st][(m &gt;&gt; i) &amp; 1][0];
            if (i &gt;= 10 || (1 &lt;&lt; i) &gt;= k)
            {
                ans += res[i][ls] + popcnt[rs &amp; fl[i][ls]];
                rs = fr[i][ls];
            }
            else nw |= ((ll)fl[i][ls] &lt;&lt; ln), ln += (1 &lt;&lt; i);
            st = nx[st][(m &gt;&gt; i) &amp; 1][1];
        }
    }
    calc(nw, ln);
    return ans + RE + popcnt[rs &amp; FL];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

    int T;
    cin &gt;&gt; T;
    for (int i = 1; i &lt; (1 &lt;&lt; 18); i++) popcnt[i] = popcnt[i ^ (i &amp; -i)] + 1;
    while (T--)
    {
        memset(mat, 0, sizeof(mat));

        ll l, r; str = 0;
        cin &gt;&gt; n &gt;&gt; m &gt;&gt; k &gt;&gt; l &gt;&gt; r &gt;&gt; s &gt;&gt; t;
        l = m * n + 1 - l, r = m * n + 1 - r;
        swap(l, r);
        for (int i = 0; i &lt; k; i++) str |= ((t[i] == &#039;1&#039;) &lt;&lt; (k - i - 1));
        int N = 1 &lt;&lt; n;
        for (int i = 0; i &lt;= n / 2; i++) swap(s[i], s[n - i]);

        for (int c = 0; c &lt; 2; c++)
            for (int i = 0; i &lt; n; i++)
                for (int j = 0; j &lt;= n; j++)
                {
                    if (s[j] ^ &#039;1&#039;) continue;
                    int nw = i - c + j;
                    if (nw &lt; 0 || (nw &amp; 1)) continue; nw &gt;&gt;= 1;
                    mat[i][1][c] |= (1 &lt;&lt; nw);
                }
        for (int c = 0; c &lt; 2; c++)
            for (int i = c; i &lt; n; i++)
            {
                int nw = i - c;
                if (nw &amp; 1) continue; nw &gt;&gt;= 1;
                mat[i][0][c] |= (1 &lt;&lt; nw);
            }
        
        for (int st = 0; st &lt; N; st++)
            for (int i = 0; i &lt; 2; i++)
                for (int j = 0; j &lt; 2; j++) nx[st][i][j] = mult(st, i, j);
        lim = 0;
        while ((1ll &lt;&lt; lim) &lt;= r || (1ll &lt;&lt; lim) &lt;= m) lim++;
        for (int st = 0; st &lt; N; st++)
        {
            fl[0][st] = fr[0][st] = (bool)(st &amp; 1);
            res[0][st] = 0;
            if (k == 1)
            {
                res[0][st] = (fl[0][st] == str);
                fl[0][st] = fr[0][st] = 0;
            }
        }

        for (int i = 1; i &lt;= lim; i++)
        {
            bool ch = (m &gt;&gt; (i - 1)) &amp; 1;
            for (int st = 0; st &lt; N; st++)
            {
                int ls = nx[st][ch][0], rs = nx[st][ch][1];
                if (i &lt;= 4 &amp;&amp; (1 &lt;&lt; i) &lt; k)
                    fl[i][st] = fr[i][st] = (fr[i - 1][rs] &lt;&lt; (1 &lt;&lt; (i - 1))) | fl[i - 1][ls], res[i][st] = 0;
                else if (i &gt;= 10 || (1 &lt;&lt; i) &gt;= (k &lt;&lt; 1))
                {
                    fl[i][st] = fl[i - 1][ls], fr[i][st] = fr[i - 1][rs];
                    res[i][st] = res[i - 1][ls] + res[i - 1][rs] + popcnt[fr[i - 1][ls] &amp; fl[i - 1][rs]];
                }
                else
                {
                    int len = 1 &lt;&lt; i;
                    ll nw = ((ll)fr[i - 1][rs] &lt;&lt; (1 &lt;&lt; (i - 1))) | fl[i - 1][ls];
                    fl[i][st] = fr[i][st] = res[i][st] = 0;
                    calc(nw, len); res[i][st] = RE;
                    fl[i][st] = FL, fr[i][st] = FR;
                }
            }
        }

        if (r - l + 1 &lt; k)
        {
            cout &lt;&lt; &quot;0\n&quot;;
            continue;
        }
        cout &lt;&lt; work(r) - work(l + k - 2) &lt;&lt; &quot;\n&quot;;
    }
	return 0;
}
</p></div>
</div>
<script type="text/javascript">
    (function ($) {
        $(document).ready(function () {
            $('.pre p').each(function(i, block) {  // use <pre><p>
                hljs.highlightBlock(block);
            });
        })
    })(jQuery);
</script>