[Luogu cf643f] bears and juice (conclusion)

Bears and Juice

Topic link ：luogu CF643F

The main idea of the topic

Yes n A bear p Bed , There are some wine barrels , You can set the quantity , One of them put wine and the other put fruit juice , Then each bear can choose a barrel to gather every day （ Can be null ）, If the bear eats wine, it will occupy a bed to sleep , If there is not enough bed or the bear sleeps all, he will lose .
Then ask you to give you 1~q Time of day , How many barrels can you get at most , So that these bears must be able to find the location of the wine without losing .

Ideas

It's a magical question ！
Consider how to distinguish wine barrels （ Because you can find your wine in that bucket ）, Then let's consider how we can't distinguish .
Then we found another thing is that we can only get information from who is drunk , Useful information .

Let's consider how to distinguish , For a barrel, if we list a table, it means $i$ Tiandi $j$ Did the bear eat it .
Obviously, if the watch is different, it is a different bucket , How many watches are there ？

Consider enumerating how many bears ate this , Then for every bear it can be here $x$ Eat on any day of the day .
$R_x=\sum _{i=0}^{\min (n-1,p)}\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^i$

Then it's over ！
（ Since you can't invert, how many primes can you maintain for each combinatorial number , And then what is the big product ）
（ It's small. It may be $i$ Removed , That is to say $130$ Inside , For large ones, just record the product directly ）

（ Preprocessing $R$ Can $O(\min (n,p)q)$ Complete the answer ）
（ belt $\log$ Whether it's written Lala or not /tp）

Code

#include<cstdio>

using namespace std;

int n, p, q;
unsigned int ans, sum, di, vals[131];
int val[131], id[131], tot, num[131];

unsigned int ksm(unsigned int x, int y) {
    
	unsigned int re = 1;
	while (y) {
    
		if (y & 1) re = re * x;
		x = x * x; y >>= 1;
	}
	return re;
}

void Run(int x, int gx) {
    
	for (int i = 1; i <= tot; i++) {
    
		while (x % val[i] == 0) {
    
			num[i] += gx; x /= val[i];
		}
	}
	di = di * x;
}

int main() {
    
	for (int i = 2; i <= 130; i++) {
    
		bool prime = 1;
		for (int j = 2; j < i; j++) if (i % j == 0) {
    prime = 0; break;}
		if (prime) id[i] = ++tot, val[tot] = i;
	}
	
	scanf("%d %d %d", &n, &p, &q);
	di = 1; vals[0] = 1;
	for (int i = 1; i <= p && i < n; i++) {
    
		Run(n - i + 1, 1); Run(i, -1);
		sum = 1;
		for (int j = 1; j <= tot; j++) sum *= ksm(val[j], num[j]);
		vals[i] = sum * di;
	}
	
	for (int i = 1; i <= q; i++) {
    
		sum = 0; di = 1;
		for (int j = 0; j <= p && j < n; j++)
			sum += vals[j] * di, di = di * i;
		ans ^= sum * i;
	}
	printf("%u", ans);
	
	return 0;
}