Post Jobs

欧拉函数,Flv的结构分析

图片 8

Flv是网络上流行的非常广的一种媒体格式,很多大型媒体网站都在使用这种格式承载音视频信息,比如优酷等网站。

题目链接

如果$ax{\equiv}1(mod\,p)$,且a与p互质(gcd(a,p)=1),则称a关于模p的乘法逆元为x。(不互质则乘法逆元不存在)

   

 

有一个问题,在求解过程中有除法,答案很大,要求最终答案对某数p取模。显然,由于除法的出现,每一次运算之后取模是行不通的。(比如:求1*7/2,答案对5取模。如果每一次运算取模也就是7%5/2%5,会得到1,正确结果却是3)如果不想高精度把最终结果算出来再取模的话,有一个方法,就是把除以x转换为乘上x关于模p的乘法逆元。(事实上,乘法逆元应该视为线性同余方程的解也就是一些数而不是一个数,但是一般只需要使用任意一个(比如最小正整数解)就能完成任务)

Flv文件格式相对而言还是比较简单的,主要是由两部分组成

problem

为什么能这么做:

   

Recently George is preparing for the Graduate Record Examinations (GRE
for short). Obviously the most important thing is reciting the words. 
Now George is working on a word list containing N words. 
He has so poor a memory that it is too hard for him to remember all of
the words on the list. But he does find a way to help him to remember.
He finds that if a sequence of words has a property that for all pairs
of neighboring words, the previous one is a substring of the next one,
then the sequence of words is easy to remember. 
So he decides to eliminate some words from the word list first to make
the list easier for him. Meantime, he doesn’t want to miss the important
words. He gives each word an importance, which is represented by an
integer ranging from -1000 to 1000, then he wants to know which words to
eliminate to maximize the sum of the importance of remaining words.
Negative importance just means that George thought it useless and is a
waste of time to recite the word. 
Note that although he can eliminate any number of words from the word
list, he can never change the order between words. In another word, the
order of words appeared on the word list is consistent with the order in
the input. In addition, a word may have different meanings, so it can
appear on the list more than once, and it may have different importance
in each occurrence. 

设c是b关于模m的逆元,即$b*c{\equiv}1(mod\,m)$,那么有$a/b{\equiv}(a/b)*1{\equiv}(a/b)*b*c{\equiv}a*c(mod\,m)$

FLV
header

图片 1

求法:

FLV
body

Input

1.扩展欧几里得

   

The first line contains an integer T(1 <= T <= 50), indicating the
number of test cases. 
Each test case contains several lines. 
The first line contains an integer N(1 <= N <= 2 *
10 4), indicating the number of words. 
Then N lines follows, each contains a string S i and an
integer W i, representing the word and its importance.
i contains only lowercase letters. 
You can assume that the total length of all words will not exceeded 3 *
10 5.

$ax{\equiv}1(mod\,p)$,那么可以设$ax-1=p(-y)$,那么$ax+py=1=gcd(a,p)$,求解即可

   

Output

2.欧拉定理(费马小定理)

FLV header

   

前9个字节

图片 2

46 4c 56 01 05 00 00
00 00 09

第一到第三字节(46 4c
56) 的ascii的代码为”FLV”(注意大小写)

第四个字节为版本信息,一般都为(01)

第五个字节为流的信息,表示是否有视频信息,是否有音频信息。0000
0001(0x01)为有视频,0000
0100(0x04)为有音频,既有有视频又有音频为(0x05)

第六到第九字节存放的是整个头部长度,一般为(3+1+1+4)=9。

   

For each test case in the input, print one line: “Case #X: Y”, where X
is the test case number (starting with 1) and Y is the largest
importance of the remaining sequence of words.

质数筛法:

FLV body

   

Flv
body是由很多tag组成,tag又分成三种类型

  • script(脚本流)
  • video(视频流)
  • audio(音频流)

   

tag的结构举例如下:

图片 3

   

   

每个tag包含

  • tag header
  • tag data   

Sample Input

列一张表可以发现,每一个非质数x都是被(x/x的最小质因子)这个数筛掉的。

tag header

   

tag header
的第一个字节表示为记录的数据类型,(0x12)为脚本类型;(0x08)为音频类型;(0x09)为视频类型    

tag
header的第二到第四个字节表示为数据区长度

图片 4

(0x00 01 74)表示
为372,表示tag data 长度

tag header
的第五到第七个字节表示为时间戳,类型为(0x12)的tag时间戳一直为0,(0xFFFFFF)可以表示长度为4小时,单位为毫秒。

tag header
的第八个字节为扩展时间戳,一般都为0,长度为4小时的flv一般很少见了。

tag header
的第九到第十一个字节为streamID,总为0.

   

1
5
a 1
ab 2
abb 3
baba 5
abbab 8

注意:break那里不能是(!i%prime[j])!!!!!如果这样写一定要写成(!(i%prime[j]))!!感叹号优先级高!!

tag data

   

tag
data三种类型的结构表示如下:

Sample Output

nprime[1]=1;
for(i=2;i<=n;i++)
{
    if(!nprime[i])    prime[++len]=i;
    printf("%d: ",i);
    for(j=1;j<=len&&i*prime[j]<=n;j++)
    {
        nprime[i*prime[j]]=1;
        printf("%d ",i*prime[j]);
        if(i%prime[j]==0)    break;
    }
    puts("");
}

2: 4
3: 6 9
4: 8
5: 10 15 25
6: 12
7: 14 21 35 49
8: 16
9: 18 27
10: 20
11: 22 33
12: 24
13: 26 39
14: 28
15: 30 45
16: 32
17: 34
18: 36
19: 38
20: 40
21: 42
22: 44
23: 46
24: 48
25: 50

script(脚本流)

包含两个AMF(Action
Message Format)包,第一个AMF包封装了” onMetaData
“,第二个AMF包封装了诸如视频图像长宽,文件长度,视频帧率,音频比特率,位深等等。

图片 5

第一个字节表示AMF包类型,都是(0x02),表示字符串。

第二到第三个字节表示字符串长度,一般是(0x0a),表示10个字符串,就是第四到第十三个字节包含的”
onMetaData “字符串的长度。

第十四个字节是第二个AMF包类型,一般是(0x08),表示数组,第十五到第十八个字节是AMF包长度,表示数组元素个数。(0x10)表示包含16个数组元素长度。

后面即为各数组元素的封装,数组元素为元素名称和值组成的对。表示方法如下:

   

第1-2个字节表示元素名称的长度,假设为L。

后面跟着为长度为L的字符串。

第L+3个字节表示元素值的类型。

后面跟着为对应值,占用字节数取决于值的类型。

   

图片 6

   

Case #1: 14

思路:AC自动机+线段树。这题直观的想法是以每个字符串为尾串,求在当前串之前选取字符串并以当前串为结束得到的最大值,即dp[i]=max(dp[j])+w[i],s[j]是s[i]的子串且j<i;
我们可以反向建立fail树,那么对于串s[i]的最后一位指向的孩子,均是包含s[i]的串,所以以s[i]的最后一位为根节点的子树中的孩子节点表示的串均包含s[i],那么我们对串s[1]~s[n]逐一进行计算时,可以把结
果用线段树更新到子树中,然后对于每个串计算时,只需要考虑s[i]的每一位能得到的最大值(线段树单点查询),最后取最大值加上w[i],即为s[i]的最大值,然后更新到子树中。

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;
const int N=2e4+5;
const int M=3e5+5;
char s[M];
int w[N],pos[N];

struct Node
{
    int son[26];
}node[M];
int fail[M];
int root,tot;

struct Edge
{
    int to;
    int next;
}edge[M];
int head[M],cnt;

int in[M],out[M],tp;  ///树节点序号化;

int tx[M*4],tf[M*4],L,R,tmp; ///线段树;

inline int newnode()
{
  tot++;
  memset(node[tot].son,0,sizeof(node[tot].son));
  fail[tot]=0;
  return tot;
}

inline void addEdge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

inline void insert(char s[])
{
    int now=root;
    for(int i=0;s[i];i++)
    {
        if(!node[now].son[s[i]-'a'])
            node[now].son[s[i]-'a']=newnode();
        now=node[now].son[s[i]-'a'];
    }
}
inline void build()
{
    queue<int>Q;
    Q.push(root);
    while(!Q.empty())
    {
        int now=Q.front(); Q.pop();
        if(now!=root) addEdge(fail[now],now);
        for(int i=0;i<26;i++)
        {
            if(node[now].son[i])
            {
                if(now!=root)
                    fail[node[now].son[i]]=node[fail[now]].son[i];
                Q.push(node[now].son[i]);
            }
            else node[now].son[i]=node[fail[now]].son[i];

        }
    }
}
inline void dfs(int now)
{
   in[now]=++tp;
   for(int i=head[now];i;i=edge[i].next)
   {
       dfs(edge[i].to);
   }
   out[now]=tp;
}
inline void pushdown(int i)
{
    if(!tf[i]) return ;
    int pre=tf[i];
    tf[i<<1]=max(tf[i<<1],pre);
    tf[i<<1|1]=max(tf[i<<1|1],pre);
    tx[i<<1]=max(tx[i<<1],pre);
    tx[i<<1|1]=max(tx[i<<1|1],pre);
    tf[i]=0;
}
inline int query(int l,int r,int i)
{
    if(l==r) return tx[i];
    int mid=(l+r)>>1;
    pushdown(i);
    if(L<=mid) return query(l,mid,i<<1);
    else return query(mid+1,r,i<<1|1);
}
inline void update(int l,int r,int i)
{
    if(L<=l&&r<=R)
    {
        tf[i]=max(tf[i],tmp);
        tx[i]=max(tx[i],tmp);
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(i);
    if(L<=mid) update(l,mid,i<<1);
    if(R>mid)  update(mid+1,r,i<<1|1);
    tx[i]=max(tx[i<<1],tx[i<<1|1]);
}

void init()
{
    tot=-1;
    cnt=1;
    tp=0;
    root=newnode();
    memset(head,0,sizeof(head));
    memset(fail,0,sizeof(fail));
    memset(tx,0,sizeof(tx));
    memset(tf,0,sizeof(tf));
}
int main()
{
    int T,Case=1; scanf("%d",&T);
    while(T--)
    {
        init();
        int n; scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
           scanf("%s%d",s+pos[i-1],w+i);
           pos[i]=pos[i-1]+strlen(s+pos[i-1]);
           insert(s+pos[i-1]);
        }
        build();
        dfs(root);
        int ans=0;
        for(int i=1;i<=n;++i)
        {
            tmp=0;
            int now=root;
            for(int j=pos[i-1];j<pos[i];++j)
            {
               now=node[now].son[s[j]-'a'];
               L=in[now]; R=in[now];
               int res=query(1,tp,1);
               tmp=max(tmp,res);
            }
            tmp+=w[i];
            ans=max(ans,tmp);
            L=in[now];
            R=out[now];
            update(1,tp,1);
        }
        printf("Case #%d: %d\n",Case++,ans);
    }
    return 0;
}

调试跟踪一下就可以明白这个break的原理。

video(视频流)

   

视频流如下:

图片 7

前4bits表示类型:

·1– keyframe

·2 — inner frame

·3 — disposable inner
frame (h.263 only)

·4 — generated
keyframe

(0x17)前4bit表示为0001,表示为keyframe

   

后4bits表示解码器ID:

·2 — seronson h.263

·3 — screen video

·4 — On2 VP6

·5 — On2 VP6 with
alpha channel

·6 — Screen video
version 2

·7 — AVC (h.264)

(0x17)后4bits表示为0111,表示为avc(h.264)

   

第二个字节固定为0x01。

 

之后是视频数据。

   

   

 

例如当i=12时,第一次筛掉24。显然,24的最小质因子是2,24/2=12。之后发现12是2的倍数,说明12乘一个2以上的质数,得到的合数的最小质因子都是2,就不应当由12来筛掉。

audio(音频流)

图片 8

前4bits表示音频格式:

·0 — 未压缩

·1 — ADPCM

·2 — MP3

·4 — Nellymoser
16-kHz mono

·5 — Nellymoser 8-kHz
mono

·10 – AAC

(0x2b)前4bits为2,表示为mp3

   

下面两个bits表示samplerate:

·0 — 5.5KHz

·1 — 11kHz

·2 — 22kHz

·3 — 44kHz

(0x2b)中b表示为
1011,10为2,表示22kHz

   

下面1bit表示采样长度:

·0 — snd8Bit

·1 — snd16Bit

   

   

下面1bit表示类型:

·0 — sndMomo

·1 – sndStereo

   

之后是数据。

   

欧拉函数:$φ(n)$表示小于等于n且与n互质的整数个数。定义$φ(1)=1$。

tag size

在每个tag前面都有四个字节,表示前面tag的长度大小,因为script(脚本流)前面没有tag,所以script
tag前面的四个字节都为(0x00 00 00 00).

 

相应的入门代码
传送门:

显然,设$n=p1^a1*p2^a2*…*pk^ak$(就是把n分解质因数),那么小于n且不与n互质的整数,一定是集合$\{p1,p2,..,pk\}$中一些数的积。

也就是说,$φ(n)$就是

欧拉函数定义&基础求法&筛法:

欧拉函数ext

筛法补充说明:对于每一个质数p,欧拉函数值显然等于p-1。对于每一个合数a,用筛掉它的数b的函数值来计算它的函数值。

几个性质的补充说明:

这个证明没有仔细看是不是对的

(以下内容仅留作记录)

欧拉函数,用φ(n)表示

欧拉函数是求小于等于n的数中与n互质的数的数目

辣么,怎么求哩?~(~o ̄▽ ̄)~o

可以先在1到n-1中找到与n不互质的数,然后把他们减掉

比如φ(12)

把12质因数分解,12=2*2*3,其实就是得到了2和3两个质因数

然后把2的倍数和3的倍数都删掉

2的倍数:2,4,6,8,10,12

3的倍数:3,6,9,12

本来想直接用12 – 12/2 – 12/3

但是6和12重复减了

所以还要把即是2的倍数又是3的倍数的数加回来 (>﹏<)

所以这样写12 – 12/2 – 12/3 + 12/(2*3)

这叫什么,这叫容斥啊,容斥定理听过吧

比如φ(30),30 = 2*3*5

所以φ(30) = 30 – 30/2 – 30/3 – 30/5 + 30/(2*3) + 30/(2*5) +
30/(3*5) – 30/(2*3*5)

但是容斥写起来好麻烦( ̄. ̄)

有一种简单的方法

φ(12)   =   12*(1 – 1/2)*(1 – 1/3)                 =   12*(1 – 1/2 –
1/3 + 1/6)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图