Luogu 2150 [NOI 2015] sushi dinner

Portal
thinking

Ah, I'm too weak to do anything. I can't even fight violence. It's mainly because I've never done DP in the state of quality factor? Oh, I'm too weak!

For 30% 30% data

The essence of mutual quality is that there is no same quality factor. Let fi,S1,S2fi,S1,S2 represent the number of the first ii under consideration. The set of quality factors selected by the first person is s1s1, and that selected by the second person is s2s2. The equation of state transition is (only brush table method can be used):

f[i+1][S1][S2] += f[i][S1][S2]f[i+1][S1][S2] += f[i][S1][S2]
f[i+1][S1∪maski+1][S2] += f[i][S1][S2](S2∩maski+1=∅)f[i+1][S1∪maski+1][S2] += f[i][S1][S2](S2∩maski+1=∅)
f[i+1][S1][S2∪maski+1] += f[i][S1][S2](S1∩maski+1=∅)f[i+1][S1][S2∪maski+1] += f[i][S1][S2](S1∩maski+1=∅)

                      .

For 100% 100% data

This kind of question usually comes up with – √. If you think about it carefully, you can find that at most one number can only have a quality factor greater than n − √ n (two of them are greater than nn), so let's start from here. And then I really won't.

ff

Reference code
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
#define loop register int 
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
LL mod;
int n;

#define RunInstance(x) delete new x
struct brute
{
    int mask[35];
    LL f[2][1 << 10][1 << 10];

    brute() : mask(), f()
    {
        for (int i = 2; i <= n; i++)
            for (int j = 0; j < 10; j++)
                if (i % prime[j] == 0)
                    mask[i] |= 1 << j;

        int U = 1 << 10;
        f[1][0][0] = 1;
        for (loop i = 1; i < n; i++)
        {
            int cnt = i & 1;
            int next = !cnt;
            memset(f[next], 0, sizeof(f[next]));
            for (loop S1 = 0; S1 < U; S1++)
            {
                for (loop S2 = 0; S2 < U; S2++) if (f[cnt][S1][S2])
                {
                    (f[next][S1][S2] += f[cnt][S1][S2]) %= mod;
                    if (!(S2 & mask[i + 1]))
                        (f[next][S1 | mask[i + 1]][S2] += f[cnt][S1][S2]) %= mod;
                    if (!(S1 & mask[i + 1]))
                        (f[next][S1][S2 | mask[i + 1]] += f[cnt][S1][S2]) %= mod;
                }
            }
        }

        LL ans = 0;
        for (loop S1 = 0; S1 < U; S1++)
            for (loop S2 = 0; S2 < U; S2++)
                (ans += f[n & 1][S1][S2]) %= mod;
        printOut(ans);
    }
};
struct work
{
    work()
    {

    }
};

void run()
{
    n = readIn();
    mod = readIn();
    if (n <= 30)
        RunInstance(brute);
    else
        RunInstance(work);
}

int main()
{
    run();
    return 0;
}

Posted on Sun, 22 Mar 2020 08:11:03 -0700 by dotbob