卡牌问题题解

【前言】
一道稍微想起来有一点点难的数学题。
这是一个叫做吉尔布雷德定理的拓展。
吉尔布雷德原理本身的内容是将黑白相间的牌分为两堆，使两堆牌底的那张不同，然后交错洗成一堆，最终得到的结果依旧是黑白相间的一堆牌。
稍微拓展了一下，便有了这道题目。

【暴力】
O(n*m)的模拟即可。

【正解】
如果你使用了模拟，你可以过绝大部分数据，数据中很大一部分是可以接受这个复杂度的。
但是对于极限数据，模拟还不够。
当然，如果你使用了模拟，也许可以发现一些规律...

结论：
把新牌库均分为n份，分别为1到m，m+1到2m，2m+1到3m...，你会发现每一份的m张牌恰好1~m这些数值每个数值出现了1次。

如果你模拟了一些小数据并把他们的终末序列输出，应该可以发现这个结论。

结论当然也可以推出来。
我们发现，旧牌库就是一个1~m循环n次的序列，还可以发现，即使进行了第一步操作，旧牌库是循环序列的本质没有改变，如果你把旧牌库想象成一个从某处断开的环，第一步操作只不过是改变了断开的位置，其实可以无视这步操作。

重要的是操作2，旧牌库被打乱了，无视了第一步操作，旧牌库可以看做1,2,3,4...mn(这里指卡牌编号，并非卡牌上的数字)进行完操作2后，新牌库为1,nm,2,nm-1,...,b,nm-b+1,b+1,b+2,...nm-b
从b+1到nm-b，由于原本在旧牌库就是连续的，肯定满足结论，不需讨论，我们只需要知道前面的部分是否满足即可，当然，我们还可以这么想，卡牌上数字相同的牌都出现在不同的组即可。

研究卡牌上数字为1的卡牌，对于牌库底，出现在每m张的第一张，对于牌库顶，出现在每m张的最后一张，底一张顶一张的抽取，必然分列于km+1和km+2m(k为常数)，不属同组，这是靠得最近(除了同为牌库顶或同为牌库底的两张之外)的两张1，如果它们都没有分到一组，那么其他牌便不可能。

研究卡牌上数字为2的卡牌，对于牌库底，出现在每m张的第二张，对于牌库顶，出现在每m张的倒数第二张，底一张顶一张的抽取，必然分列于km+3和km+2m-2(k为常数)，不属同组，这是靠得最近(除了同为牌库顶或同为牌库底的两张之外)的两张2，如果它们都没有分到一组，那么其他牌便不可能。

......
研究卡牌上数字为m/2的卡牌，对于牌库底，出现在每m张的第m张，对于牌库顶，出现在每m张的第一张，底一张顶一张的抽取，必然分列于km+m-1和km+m+2(k为常数)，不属同组，这是靠得最近(除了同为牌库顶或同为牌库底的两张之外)的两张1，如果它们都没有分到一组，那么其他牌便不可能，对于m是奇数和偶数的情况都适用。

对于m/2+1到m，和1到m/2对称。
结论得证。

知道了这个结论，我们就很好求新牌库第x张到第y张的和了，先把x到y中完整的组找出来，直接求得它们的和，假设完整的组为第z组到第w组，那么不完整部分我们逐个找到它们在旧牌库中对应的卡牌即可，把关系列一下(麻烦是有一点点麻烦，但是呢，不要嫌弃)，最多两次O(m)的时间就可以全部求出来啦。

【小结】
其实很多这种变换之后再设问求解的问题都有结论，推不出来可以先自己暴力出小数据找规律。

参考代码(冗长的代码，实现方式不局限于这一种)：

class Solution {
public:
    /**
     * 
     * @param n long长整型 
     * @param m long长整型 
     * @param a long长整型 
     * @param b long长整型 
     * @param x long长整型 
     * @param y long长整型 
     * @return long长整型
     */
    long long work(long long n, long long m, long long a, long long b, long long x, long long y) {
        // write code here
        long long mo=998244353;
        long long xx=(x-1)/m+1,yy=y/m,z=m*(m+1)%mo*499122177%mo;
        long long ans=(yy-xx)*z%mo;
        xx=xx*m;
        yy=yy*m;
        for (long long i=x;i<=xx;i++)
        {
            if (i<=2*b)
            {
                if (i&1) 
                {
                    long long py=i;
                    py=(py+1)/2;
                    ans=(ans+(py+a-1)%m+1)%mo;
                }else
                {
                    long long py=i;
                    py=(py+1)/2;
                    ans=(ans+((a-py+m)%m+m)%m+1)%mo;
                }
            }else ans=(ans+((a-b+i+m-1)%m+m)%m+1)%mo;
        }
        for (long long i=yy+1;i<=y;i++)
        {
            if (i<=2*b)
            {
                if (i&1) 
                {
                    long long py=i;
                    py=(py+1)/2;
                    ans=(ans+(py+a-1)%m+1)%mo;
                }else
                {
                    long long py=i;
                    py=(py+1)/2;
                    ans=(ans+((a-py+m)%m+m)%m+1)%mo;
                }
            }else ans=(ans+((a-b+i+m-1)%m+m)%m+1)%mo;
        }
        return ans;
    }
};