java_interface

发表于 2024-04-10 更新于 2024-04-11 Disqus：

JAVA速成Day3——接口

java提倡OOP(面向对象编程)，然后有个东西叫做抽象类，需要子类继承来重写其定义的方法。

然后接口这个东西更抽象，相比抽象类，它只有方法，没有字段：

interface bird{
    void fly();
    String getName();
}

当具体的类要实现这些接口时，需要使用 implements 关键字：

class blackbird implements bird{
    private String name;

    public blackbird(String name){
        this.name = name;
    }

    @Override
    public void fly() {
        System.out.println(name + " is flying~");
    }

    @Override
    public String getName() {
        return name;
    }
}

然而，java不能同时继承多个类，但是可以同时实现多个接口。

接口之间可以继承：

interface Hello {
    void hello();
}

interface bird extends Hello {
    void fly();
    String getName();
}

神奇的是，可以通过接口去引用对象：

public class test {
    public static void main(String[] args) {
        bird bb = new blackbird("taffy");
        bb.fly();
    }
}

然而，对于对象自己实现的方法，接口没办法引用。

实际上，在我整的JAVA速成Day1那篇介绍集合的文章中，我留了个坑：用Map引用TreeMap。

实际上这里的Map，以及List，都是接口。

它们引用的对象，只能调用自己即继承的接口内部的方法。

因此对于TreeMap中独属于该类的方法，接口Map不能调用。因此你会发现IDEA的自动补全里少了点API。

另外，接口中可以定义 default 方法，然后直接在接口内部实现：

interface bird{
    void fly();
    String getName();

    default void hello(){
        System.out.println(getName() + " will succeed!");
    }
}

class blackbird implements bird{
    private String name;

    public blackbird(String name){
        this.name = name;
    }

    @Override
    public void fly() {
        System.out.println(name + " is flying~");
    }

    @Override
    public String getName() {
        return name;
    }

    public void hh(){

    }
}

public class test {
    public static void main(String[] args) {
        bird bb = new blackbird("blackbird");
        bb.hello();
    }
}

这样的话，如果对于一个接口新增一个方法，就不需要更改所有实现它的子类了，只需要在需要的地方 override 即可。

晚安

事实上接口是可以有字段的，但是其类型为 public static final ：

public interface Person {
    public static final int MALE = 1;
    public static final int FEMALE = 2;
}

--update 24.4.11

JAVA速成Day1——集合

发表于 2024-04-09 更新于 2024-05-01 Disqus：

JAVA速成Day1——集合

主要针对南京大学软件学院机试

1. List

分为ArrayList和LinkedList

ArrayList可以理解为C++ STL的vector（

LinkedList则为链表实现动态数组

import java.util.ArrayList;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        // 创建
        ArrayList<String> list = new ArrayList<>();
        // LinkedList<String> list = new LinkedList<>();
        
        // 添加
        list.add("blackbird");
        list.add("greybird");
        list.add("darkbird");

        // 获取第i个元素
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            System.out.println(s);
        }
        // 迭代器遍历的for each
        for (String s : list) {
            System.out.println(s);
        }
        // 删除元素，下标从0开始
        list.remove(1);
        for (String s : list) {
            System.out.println(s);
        }
        // 修改元素
        list.set(1, "yy");
        for (String s : list) {
            System.out.println(s);
        }
    }
}

2. 数组排序

一般的数组升序排序：（这里的话，是可以指定排序范围的

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
    int[] list = new int[110];
    int n;
    Scanner sc = new Scanner(System.in);
    void sol(){
        n = sc.nextInt();
        for(int i = 0; i < n; i++)
            list[i] = sc.nextInt();
        Arrays.sort(list, 0, n);
        for(int i = 0; i < n; i++)
            System.out.print(list[i] + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        // 创建
        Main Solution = new Main();
        Solution.sol();
    }
}

降序的话，是需要自定义一个 Comparator 类的。

但是无论是Array.sort还是Collections.sort都没办法同时指定 Comparator 和下标范围。因此这里使用动态数组可能更为方便：

import java.util.*;


public class Main {
    ArrayList<Integer> blackbird = new ArrayList<>();
    int n;
    Scanner sc = new Scanner(System.in);
    Comparator<Integer> cmp = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            Integer val = o2 - o1;
            return val.intValue();
        }
    };
    void sol(){
        n = sc.nextInt();
        blackbird.clear();
        for(int i = 0; i < n; i++)
            blackbird.add(sc.nextInt());

        Collections.sort(blackbird, cmp);
        for(int i = 0; i < n; i++)
            System.out.print(blackbird.get(i) + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        // 创建
        Main Solution = new Main();
        Solution.sol();
    }
}

对于 Comparator 类中，我们需要重写 compare 函数。如果参数一根据你想要的定义小于参数二，那么返回负整数。等于返回零。大于返回正整数。

另外，集合不支持 int 这种基本数据类型。需要使用对应的对象 Integer 。

3. 队列

在ACM里，队列的使用非常广泛，包括如下：

BFS
单调队列，处理滑动窗口模型
优先队列模拟堆

个人认为，在ACM场景中，一般使用 LinkedList 实现普通队列：

import java.util.*;


public class Main {
    // 创建队列
    Queue<String> q = new LinkedList<>();
    int n;
    Scanner sc = new Scanner(System.in);

    void sol(){
        // 添加元素
        q.offer("blackbird");
        q.offer("greybird");
        q.offer("darkbird");
        System.out.println(q);

        // 删除元素
        q.poll();
        System.out.println(q);

        // 队首
        System.out.println(q.peek());
        System.out.println(q.peek());

        // 队尾元素的话，Queue是不支持的，可能需要自己维护
    }
    public static void main(String[] args) {
        // 创建
        Main Solution = new Main();
        Solution.sol();
    }
}

关于优先队列，可能需要传入 Comparator 接口。这里我选择使用java来实现dijkstra+堆优化算法来作为示例：

import java.util.*;


public class Main {
    static final int N = 200010;
    static int n, m, S, used=0;
    static Scanner sc = new Scanner(System.in);
    static int[] head = new int[N>>1];
    static int[] point = new int[N<<1];
    static int[] nxt = new int[N<<1];
    static int[] val = new int[N<<1];
    static int[] dis = new int[N>>1];
    static boolean[] vis = new boolean[N>>1];

    static void add(int u, int v, int w){
        point[++used] = v;
        nxt[used] = head[u];
        head[u] = used;
        val[used] = w;
    }

    static class node{
        int u, d;
        node(){}
        node(int _u, int _dis){u = _u; d = _dis;}
    }

    static void Dijkstra(){
        Comparator<node> cmp = new Comparator<node>() {
            @Override
            public int compare(node o1, node o2) {
                return o1.d - o2.d;
            }
        };
        PriorityQueue<node> q = new PriorityQueue<>(cmp);
        q.add(new node(S, 0));
        while(!q.isEmpty()){
            node nn = q.poll();
            int u = nn.u, d = nn.d;
            if(vis[u]) continue;
            vis[u] = true;
            for(int k = head[u]; k > 0; k = nxt[k]){
                int v = point[k];
                if(!vis[v] && dis[v] > dis[u] + val[k]){
                    dis[v] = dis[u] + val[k];
                    q.add(new node(v, dis[v]));
                }
            }
        }
    }
    static void sol(){
        n = sc.nextInt(); m = sc.nextInt(); S = sc.nextInt();
        for(int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f;
        dis[S] = 0;
        for(int i = 1; i <= m; i++){
            int u, v, w;
            u = sc.nextInt(); v = sc.nextInt(); w = sc.nextInt();
            add(u, v, w);
            add(v, u, w);
        }
        Dijkstra();
        for(int i = 1; i <= n; i++){
            System.out.print(dis[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        sol();
    }
}

顺带一提，这玩意在洛谷上MLE了（

关于双端队列，同样采用 LinkedList 接口。

众所周知，单调队列通常使用双端队列实现，而单调队列的一个典型例子就是实现复杂度的多重背包：

import java.util.*;


public class Main {
    static final int N = 20010;
    static Scanner sc = new Scanner(System.in);
    static int[][] f = new int[2][N];
    static int n, V;

    static void sol(){
        n = sc.nextInt(); V = sc.nextInt();
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int ii = i & 1;
            int v, w, s;
            v = sc.nextInt(); w = sc.nextInt(); s = sc.nextInt();
            for(int j = 0; j < v; j++){
                Deque<Integer> q = new LinkedList<>();
                for(int k = j; k <= V; k += v){
                    while(!q.isEmpty() && k - q.peekFirst() > s * v) q.pollFirst();
                    while(!q.isEmpty() && f[ii^1][q.peekLast()] + (k - q.peekLast()) / v * w < f[ii^1][k])
                        q.pollLast();
                    q.addLast(k);
                    f[ii][k] = f[ii^1][q.peekFirst()] + (k - q.peekFirst()) / v * w;
                    ans = Math.max(ans, f[ii][k]);
                }
            }
        }
        System.out.println(ans);
    }
    public static void main(String[] args) {
        sol();
    }
}

可以把dp的式子转化一下，得到可以使用单调队列维护的形式。

4. Map

首先java中有 HashMap ，类似于C++中的unordered_map：

import java.util.*;


public class Main {
    static final int N = 20010;
    static Scanner sc = new Scanner(System.in);


    static void sol(){
        HashMap<Integer, String> hashmap = new HashMap<>();
        // 添加key-value pair
        hashmap.put(520, "blackbird");
        hashmap.put(1314, "love u, ");
        hashmap.put(114514, "acm-icpc");
        // 获取值
        System.out.println(hashmap.get(1314) + hashmap.get(520));
        // 修改
        hashmap.put(114514, "fwyy");
        System.out.println(hashmap.get(114514));
        // 遍历
        for(Integer key: hashmap.keySet()){
            System.out.println(key + " -> " + hashmap.get(key));
        }
    }
    public static void main(String[] args) {
        sol();
    }
}

但是我们要是想要个有序的map，可以使用 TreeMap ：

import java.util.*;


public class Main {
    static final int N = 20010;
    static Scanner sc = new Scanner(System.in);


    static void sol(){
        Comparator<Integer> cmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                Integer sub = o1 - o2;
                return sub.intValue();
            }
        };
        Map<Integer, String> map = new TreeMap<>(cmp);
        // 添加key-value pair
        map.put(520, "blackbird");
        map.put(1314, "love u, ");
        map.put(666, "acm-icpc");
        // 获取值
        Integer key1314 = 1314;
        System.out.println(map.get(1314) + map.get(520));
        // 修改
        map.put(114514, "fwyy");
        System.out.println(map.get(114514));
        // 遍历
        for(Integer key: map.keySet()){
            System.out.println(key + " -> " + map.get(key));
        }
        // 查看是否存在键值对
        if(map.containsKey(520)){
            System.out.println("!!!!");
        }
    }
    public static void main(String[] args) {
        sol();
    }
}

可以使用自定义的 Comparator 。

这里我给自己挖了个坑，直接使用 Map 来定义。欸，是不是感觉少了点API了呢？hh

update（24.4.15）：

方法 getOrDefault(key, v) 。寻找key，若不存在则返回v。（source：leetcode 49）

5. Set

这里我只想讲红黑树实现的 TreeSet ，毕竟在ACM里一般都把set当平衡树来用（什么）

这里就不拿 blackbird 什么的当例子了，有点草（

import java.util.*;


public class Main {
    static final int N = 20010;
    static Scanner sc = new Scanner(System.in);


    static void sol(){
        TreeSet<Integer> s = new TreeSet<>();
        s.add(1); s.add(3); s.add(1); s.add(4); s.add(5); s.add(2); s.add(0);
        s.add(2333);
        System.out.println(s.contains(114514));
        for(Integer num: s){
            System.out.print(num + " ");
        }
        System.out.println();
        // 小于等于
        System.out.println(s.floor(10)); // 5
        // 大于等于
        System.out.println(s.ceiling(4)); // 4
        // 小于
        System.out.println(s.lower(5)); // 4
        // 大于
        System.out.println(s.higher(5)); // 2333
        // 删除
        s.remove(2333);
        for(Integer num: s){
            System.out.print(num + " ");
        }
    }
    public static void main(String[] args) {
        sol();
    }
}

欸，那java里是否有像C++中 multiset 类似的数据结构呢？答案是没有（焯！）

但是根据 stackoverflow 上的解释，可以使用 TreeMap<E, Integer> 来模拟 multiset ，其中value是计数器。

关于java中的集合就先说这么多了。

晚安

update 24.5.1

arraylist.toArray(T[] arr)

将Arraylist转化为正宗数组的方法，参数为存数据的数组。未指定默认为 Object[]

例如 arr.toArray(new int[arr.size()][2]); (https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked)

JAVA速成Day2——单例模式

发表于 2024-04-09 更新于 2024-04-15 Disqus：

JAVA速成Day2——单例模式

南软，我的南软

单例模式

确保一个类只有一个实例，并提供该实例的全局访问点。

线程不安全的懒汉式

懒汉代表延迟实例化，即只在需要的时候实例化一个对象。

public class Singleton {
    private static Singleton uniqueInstance;

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
    }

    public static Singleton getUniqueInstance(){ // 必须要是 static 
        if(uniqueInstance == null){
            // 这里是线程不安全的
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
}

线程安全的饿汉式

直接在声明对象的时候创建一个全局静态对象。

public class Singleton {
    private static Singleton uniqueInstance = new Singleton();

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
    }

    public static Singleton getUniqueInstance(){
        return uniqueInstance;
    }
}

这个方式丢失了节约资源的好处。

线程安全的懒汉式

在第一种方式的race condition那里上锁即可。方法是加上 synchronized 关键字。

public class Singleton {
    private static Singleton uniqueInstance;

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
        System.out.println("love u");
    }

    public static synchronized Singleton getUniqueInstance(){ // 必须要是 static
        if(uniqueInstance == null){
            // 这里是线程安全的
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
}

但是这里序列化了 getUniqueInstance 方法，失去了多线程并发的意义。

双重校验锁

public class Singleton {
    private volatile static Singleton uniqueInstance;

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
        System.out.println("love u");
    }

    public static Singleton getUniqueInstance(){ // 必须要是 static
        if(uniqueInstance == null){
            synchronized (Singleton.class) {
                if(uniqueInstance == null){
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
}

这里必须使用双重 if ，原因相信你能直接看出来。

至于 volatile 关键字，也是必不可少的。这是因为语句 uniqueInstance = new Singleton(); 并不是原子的，它需要进行：

分配内存空间
初始化对象
将 uniqueInstance 指向对应的内存地址。

但是 jvm 可能会将指令重排，将上述执行顺序更改为1>3>2，这在多线程的情况下是有问题的，可能在另一个线程得到未初始化的对象。

静态内部类

静态内部类。。。这个打codeforces倒是经常用。

public class Singleton {
    private static Singleton uniqueInstance;
    private Singleton(){
        System.out.println("love u, blackbird");
    }

    private static class SingletonHolder{
        private static final Singleton INSTANCE = new Singleton();
    }

    public static Singleton getUniqueInstance(){ // 必须要是 static
        return SingletonHolder.INSTANCE;
    }
}

原理有两点：

静态内部类在 Singleton 外部类加载的时候并没有被加载进内存，只有需要的时候（调用 get 方法）才会加载；
虚拟机提供了线程安全，不会多次加载静态内部类。

很神奇是吧？我也觉得~

枚举实现

这东西我第一次看的时候懵了。代码长这样：

1
2
3

public enum Singleton {
    INSTANCE;
}

挖个坑吧，不是很懂。

枚举

讲真之前我连C语言的enum是干啥的我都不知道。。。

在java中，可以通过 static final 来定义常量：

public class Weekday {
    public static final int SUN = 0;
    public static final int MON = 1;
    public static final int TUE = 2;
    public static final int WED = 3;
    public static final int THU = 4;
    public static final int FRI = 5;
    public static final int SAT = 6;
}

可以通过 Weekday.SUN 等形式来访问这些常量。

当然也可以不用int来定义常量，比如String这种。但是在比较的时候需要把 == 改成 equals()。

当我们的需求不依赖于这种int或者String的类型变量时，可以通过 enum 定义枚举类：

enum Weekday {
    SUN, MON, TUE, WED, THU, FRI, SAT;
}

int day = 1;
if (day == Weekday.SUN) { // Compile error: bad operand types for binary operator '=='
}

Weekday x = Weekday.SUN; // ok!
Weekday y = Color.RED; // Compile error: incompatible types

enum定义的枚举类是一种引用类型，但是可以用 == 来比较。这是因为enum类型的每个常量在jvm中都只有一个实例，你无法new一个enum对象。

if (day == Weekday.FRI) { // ok!
}
if (day.equals(Weekday.SUN)) { // ok, but more code!
}

（或许这也是可以使用enum实现单例模式的原因

enum编译后的结果maybe like：

public final class Color extends Enum { // 继承自Enum，标记为final class
    // 每个实例均为全局唯一:
    public static final Color RED = new Color();
    public static final Color GREEN = new Color();
    public static final Color BLUE = new Color();
    // private构造方法，确保外部无法调用new操作符:
    private Color() {}
}

可以发现，每个枚举对象都对应一个唯一的静态实例。同时构造方法是 private 的，不让你new。

但是，其实可以自定义字段与构造方法：

public class Main {
    public static void main(String[] args) {
        Weekday day = Weekday.SUN;
        if (day.dayValue == 6 || day.dayValue == 0) {
            System.out.println("Work at home!");
        } else {
            System.out.println("Work at office!");
        }
    }
}

enum Weekday {
    MON(1), TUE(2), WED(3), THU(4), FRI(5), SAT(6), SUN(0);

    public final int dayValue; // final!!!

    private Weekday(int dayValue) {
        this.dayValue = dayValue;
    }
}

可以重写 toString() 方法，这样调试输出比较方便：

public class Main {
    public static void main(String[] args) {
        Weekday day = Weekday.SUN;
        if (day.dayValue == 6 || day.dayValue == 0) {
            System.out.println("Today is " + day + ". Work at home!"); // 自动调用day.toString()
        } else {
            System.out.println("Today is " + day + ". Work at office!");
        }
    }
}

enum Weekday {
    MON(1, "星期一"), TUE(2, "星期二"), WED(3, "星期三"), THU(4, "星期四"), FRI(5, "星期五"), SAT(6, "星期六"), SUN(0, "星期日");

    public final int dayValue;
    private final String chinese;

    private Weekday(int dayValue, String chinese) {
        this.dayValue = dayValue;
        this.chinese = chinese;
    }

    @Override
    public String toString() {
        return this.chinese;
    }
}

回过来看单例模式

由于enum类部的对象在整个生命周期只会出现一次，而且无论是哪个enum类引用到的对象是同一个，因此可以据此实现单例模式。

public enum Singleton {
    INSTANCE();
    private String bird;
    private int hh;
    Singleton(){}

    public void setBird(String bird) {
        this.bird = bird;
    }

    public void setHh(int hh) {
        this.hh = hh;
    }

    public int getHh() {
        return hh;
    }

    public String getBird() {
        return bird;
    }


    public static void main(String[] args) {
        Singleton singleton = Singleton.INSTANCE;
        singleton.setBird("blackbird");
        singleton.setHh(2333);
        System.out.println(singleton.getBird() + " " + singleton.getHh());
        Singleton singleton1 = Singleton.INSTANCE;
        System.out.println(singleton1.getBird() + " " + singleton1.getHh());
    }
}
// blackbird 2333
// blackbird 2333

很神奇是吧hh

字符串哈希

发表于 2024-04-03 Disqus：

字符串哈希

将字符串转换为一个哈希值，从而判断两个字符串是否相同。

模板：

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int P = 131;
const int _ = 1510;
ull p[_], h[_];
int n;
char s[_];
void init(){
	p[0] = 1, h[0] = 0;
	for(int i = 1; i <= n; i++){
		p[i] = p[i-1] * P;
		h[i] = h[i-1] * P + s[i];
	}
}

ull get(int l, int r){
	return h[r] - h[l-1] * p[r-l+1];
}

bool substr(int l1, int r1, int l2, int r2){
	return get(l1, r1) == get(l2, r2);
}

上面是P取131或13331，然后模数采用 unsigned long long 的自动溢出机制。

练习题：https://codeforces.com/contest/1943/problem/B。div1的B，难度为2000，中等难度。

这题的重点实际上并不在于字符串哈希，而是在于判 aaa 和 ababa 这种情况。

但是对于整个子串的情况，需要特别判断是否为回文串。

如果你采用上述的哈希方式，你会发现你WA了。原因自然是哈希冲突。

然后我试了很多组 P 和 MOD，最后终于得到了一个不冲突的方案（2333和998244853）：

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int P = 2333;
const int _ = 200010;
const ull mod = 998244853;
ull p[_], h[_], hh[_];
int n, q;
string s;
set<int> even, odd;
void init(){
	p[0] = 1, h[0] = hh[0] = 0; even.clear(); odd.clear();
	for(int i = 1; i <= n; i++){
		p[i] = p[i-1] * P % mod;
		h[i] = h[i-1] * P + s[i-1]; h[i] %= mod;
		hh[i] = hh[i-1] * P + s[n-i]; hh[i] %= mod;
		if(i < n && s[i-1] != s[i]) odd.insert(i);
		if(i < n - 1 && s[i-1] != s[i+1]) even.insert(i);
	}
}

ull geth(int l, int r){
	return (h[r] - h[l-1] * p[r-l+1] % mod + mod) % mod;
}
ull gethh(int l, int r){
	int rr = n - l + 1, ll = n - r + 1;
	return (hh[rr] - hh[ll-1] * p[rr-ll+1] % mod + mod) % mod;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie();
	int T; cin >> T;
	while(T--){
		cin >> n >> q;
		cin >> s;
		init();
		while(q--){
			int l, r;
			cin >> l >> r;
			int len = r - l + 1;
			ll ans = 0;
			if(geth(l, r) != gethh(l, r)) ans = len;
			auto it = odd.lower_bound(l);
			auto it2 = even.lower_bound(l);
			if(it == odd.end() || (*it) >= r){
				;
			}else{
				if(it2 == even.end() || (*it2) >= r - 1)
					ans += 1ll * (len - 1) / 2 * ((len - 1) / 2 + 1);
				else
					ans += 1ll * (len - 1) * len / 2 - 1;
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

事实说明哈希冲突还是很玄学的。因此需要考虑更好的判回文串的方式：Manacher。

有空再写！

一些ACM计数问题——球盒模型等

发表于 2024-03-25 Disqus：

一些ACM计数问题——球盒模型等

1. 前置知识1

1.1 组合数

组合数的意义是从个不同的球中取出个球的方案数（）。

它的公式是：.

一般很少用它的递推形式：.

1.2 隔板法

在一系列的球之间选几个缝隙，插入板，就是隔板问题。

例如个球之间插入块板，可以将其分成组球（每组至少有一个球）。

由于个球之间有个缝隙，从中选出个缝隙，所对应的方案数是。

1.3 生成函数

没学过生成函数的推荐 https://www.bilibili.com/video/BV1E24y1171z?vd_source=a18dbba15826659c13a0c2fac0a3673c

笼统来讲，对于一个有限or无限的数列，它对应的生成函数为 .

生成函数主要解决以下问题：

有种不同的物品，其中第种物品可以取出个，问总共取出个物品的方案数。

对于第种物品的生成函数为：.

我们将个生成函数进行相乘，得到的多项式中项所对应的系数就是要求的答案。

具体实现复杂度为，可以使用 FFT 进行进一步优化。（但是我不会FFT

1.4 五边形数

五边形数就是如上图所示的点的个数。第个五边形数相比于第个五边形数，多出了红色的点，它的个数为。因此有 .

可通过差分前缀和求得通项公式：.

如果将的定义域扩展到负数，则有广义五边形数

关于五边形数，有五边形数定理：

欧拉函数

这个定理在后续正文讨论中会使用。

2. 正文1

球盒模型，是指将个球放到个盒中的方案计数问题。但是根据以下三项不同的要求，有8种变形：

球是否相同
盒子是否相同
盒子是否可以为空

接下来让我们一一进行解决。

1. 球相同，盒子不同，盒子不可以为空

等价于将球分为组。根据前置知识的隔板法，相当于在个缝隙中插入个板，对应的方案数为

2. 球相同，盒子不同，盒子可以为空

上个问题对于盒子的要求是：至少有一个球。

而本问题对于盒子的要求是：至少有零个球。

我们可以考虑将总球数增加，然后进行上个问题的求解。

这样所对应的问题是：个相同球与个不同的盒子，每个盒子至少有一个球。

然后我们可以把每个盒子中的每个球都删去一个，这样每个盒子都至少有零个球。此时总球数减少了，为个。

因此问题转化为：个相同球与个不同的盒子，每个盒子至少有零个球。

可以发现和本问题是一模一样的。答案为

3. 球相同，盒子相同，盒子可以为空

可以使用动态规划解决，个人感觉这个dp的转移算是比较难想的啦。

令表示将个球分到个盒子里的方案数。

关于状态转移，可以分为以下两中情况：

1、个盒子内，至少有一个盒子为空。由于盒子相同，所以我们可以将这个盒子去掉，方案数为；

2、个盒子内，每个盒子都至少有一个球。这种情况等价于把所有盒子内部去掉一个球的情况，方案数为。

因此可得转移方程：.

显然复杂度是的。

事实上，这个问题的特殊情况等价于整数划分问题，这里我们讨论一下：

一个整数可以用多少种方式划分为其他整数的和？例如：

5=1+1+1+1+1

5=1+1+1+2

5=1+2+2

5=1+1+3

5=2+3

5=1+4

5=5

这里我们把每个整数都看作一个物品，盒子有个。朴素dp做法复杂度为。

我们这样考虑，一个整数能够表示，其对应的生成函数为：.

我们要求的，是将所有的生成函数进行累乘后得到的多项式中所对应的系数：.

在前置知识中，我们提到欧拉函数

因此，，即 .

将这个庞大的式子转化成多项式，根据多项式乘法，项所对应的系数为：.

这里的要满足 .

然而，除了常数项为，其余带项的系数都应该为。

因此令上式子为，得到 .

可以发现这是一个递推的形式。由于广义五边形数的量级为，因此这里递推一次的复杂度为，总复杂度为 .

4. 球相同，盒子相同，盒子不可以为空

和第一二种情况类似，该问题对盒子的要求是：至少一个球

而上个问题的要求是：至少零个球

因此我们把每个盒子都减去一个球，事实上求的就是上述dp解法的 .

当然，我们可以对这道题单独定义一个dp状态。

然后根据上问题的转移，我们将状态分为“至少有一个盒子只有一个球”和“所有盒子都至少有大于一个球”的情况，得到转移式子：

原题链接：https://www.luogu.com.cn/problem/P1025

到目前为止，我们将所有球相同的情况都逐一进行了解读。事实上，正是球相同的这个性质，让我们可以在两种盒子是否为空的情况（如情况一二和情况三四）之间直接通过加球、删球来进行转换。

对于球不同的情况，我们还需要一点前置知识。

3. 前置知识2

3.1 第二类斯特林数

第二类斯特林数的定义和球盒模型相似：把个不同的数划分为个集合的方案数，要求不能有空集。

设第二类斯特林数为。对于，可以通过以下两种情况来递推：

1、前个数划分为个集合，剩下第个数单独为一个集合，方案数为；

2、前个数划分为个集合，剩下第个数放到这个集合之中，方案数为。

因此递推式为。

递推是的。然而，关于第二类斯特林数，有单独的公式：.

时间复杂度瓶颈为快速幂的复杂度。

说来惭愧，作为一名ICPC银牌选手，我却从来没有了解过斯特林数。我记得不知道哪里的比赛考的裸的第二类斯特林数，当时我对着这个自己推出来的的递推式想了半天怎么优化，想了一个小时想不出来，只能眼睁睁看着一堆人把这题过了，然后怀疑人生。赛后才知道有斯特林数这个东西。

4. 正文1

5. 球不同，盒子相同，盒子不可以为空

这个问题与第二类斯特林数一致。直接根据公式求即可。

6. 球不同，盒子相同，盒子可以为空

一种显然的想法：枚举不空盒子的个数，将对应的答案累加即可。

答案为。

特殊地，若，那么问题等价于将大小为的集合进行划分的所有方案数。

7. 球不同，盒子不同，盒子可以为空

这个问题就非常简单了。对于每一个数，你都可以有个盒子选择，答案显然为。

8. 球不同，盒子不同，盒子不可以为空

由于球不同，所以没办法通过将每个盒子进行减球来将问题转化为上一个情况。

考虑和第二类斯特林数（第五个情况）之间的差异，可以发现控制变量为：盒子不同了。

也就是说每个盒子都有了标号。所以很简单，我们只需要将第二类斯特林数乘上全排列个数就可以了，答案为。