2022-10-2总结(下午)

奇数计数

如果 $k=1$ 的话，直接求出序列的异或和，偶数都会两两消掉，所以剩下的就是那个出现了奇数次的数。

如果 $k=2$ 的话，先求出序列的异或和，然后记录一个数组 t[]，如果 $a_i$ 的第 $j$ 位为 $1$ 的话，就令 t[j] ^= a[i]，然后找到 $s$ 为 $1$ 的某一位，因为 $s$ 是某两个数异或得到的值，所以 $s$ 某一位为 $1$ 的话，必定是其中只有一个数这一位为 $1$ ，此时的 t[j] 即为其中一个数，另一个数就是 s^t[j] 。

#include <cstdio>
#include <iostream>
using namespace std;

int n, k;
int s, t[32];

int main()
{
    cin >> n >> k;
    
    for(int i = 1, x; i <= n; i++)
    {
        cin >> x;
        s ^= x;
        for(int j = 0; j <= 30; j++)
            if(x>>j&1) t[j] ^= x;
    }
    if(k == 1)
        cout << s << "\n";
    else
    {
        for(int j = 0; j <= 30; j++)
        {
            if(s>>j&1)
            {
                int a = t[j], b = s^a;
                if(a > b) swap(a, b);
                cout << a << " " << b << "\n";
                return 0;
            }
        }
    }
}

好图计数

由简单的组合数学可以得到通项公式: $f(n) = (n^2+2n-18)*(n!/24)$

但是 $n \le 10^9$，无法直接求阶乘。

可以考虑分段打表，每 $10^7$ 个位置打一个表，这样利用已有的阶乘值可以在 $10^7$ 次计算内算出任意一个数的阶乘。

#include <cstdio>
#include <iostream>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("road.in", "r", stdin);
        freopen("road.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef long long ll;
const int P = 1e9+7;
const int len = 1e7;
const int inv24 = 41666667;
const int biao[] = {
    1,682498929,491101308,76479948,723816384,67347853,27368307,625544428,199888908,888050723,927880474,281863274,661224977,623534362,970055531,261384175,195888993,66404266,547665832,109838563,933245637,724691727,368925948,268838846,136026497,112390913,135498044,217544623,419363534,500780548,668123525,128487469,30977140,522049725,309058615,386027524,189239124,148528617,940567523,917084264,429277690,996164327,358655417,568392357,780072518,462639908,275105629,909210595,99199382,703397904,733333339,97830135,608823837,256141983,141827977,696628828,637939935,811575797,848924691,131772368,724464507,272814771,326159309,456152084,903466878,92255682,769795511,373745190,606241871,825871994,957939114,435887178,852304035,663307737,375297772,217598709,624148346,671734977,624500515,748510389,203191898,423951674,629786193,672850561,814362881,823845496,116667533,256473217,627655552,245795606,586445753,172114298,193781724,778983779,83868974,315103615,965785236,492741665,377329025,847549272,698611116
};

int main()
{
    ll n; cin >> n;
    ll fact = biao[n/len];
    for(int i = n-n%len+1; i <= n; i++)
        (fact *= i) %= P;
    ll ans = (n*n+2*n-18)%P * fact%P * inv24%P;
    cout << ans << "\n";
}