بعد از یه سال و اندی، بلخره یه سوال با ضرب ماتریس حل کردم! $^_^$
پیشنهاد میکنم اگه با ضرب دوتا ماتریس تو هم آشنایی ندارین، قبل از خوندن راه حل یه نیگا به اینجا بندازین!
همونجور که @کنکوری گفت، اگه جواب برای $n$ رو بگیم $f(n)$، داریم:
$$f(n) = \frac16(f(n-1) + f(n-2) + ... + f(n-6)) + 1$$ خب! ماتریس $M_i$ که یه سطر و ۷ تا ستون داره رو تعریف میکنیم:

فرض کنین ماتریس $T$ هم یه ماتریس $7 \times 7$ این شکلیه:
خب، حالا اگه $M_i$ رو تو $T$ ضرب کنیم، میشه:
$ \begin{pmatrix} 1 &f(i-4) & f(i-3) & f(i-2) & f(i-1) & f(i) & 1+\frac16(f(i-5) + ... + f(i)) \end{pmatrix}$

که همون $M_{i+1}$ـه! پس حالا برا حساب کردن $M_n$، میایم میگیم:
$$M_n = M_{n-1}T = M_{n-2}T^2 = ... = M_5T^{n-5}$$
خب چون طبق فرض سوال، $f(i)$ برای $i \le 5$ برابر ۰ـه، $M_5$ میشه یه ماتریس ۱ در ۷ که اولیش ۱ـه بقیش ۰ـه...
حالا تنها مشکل، حساب کردن $T^{n-5}$ـه. چون ضرب ماتریس خاصیت شرکت پذیری داره (ینی $M_1(M_2M_3) = (M_1M_2)M_3$ )پس میشه اونو هم مثل به توان رسوندن عددا، $O(logn)$ حساب کرد.
پس در نهایت زمان اجرای راه حل میشه $7^3log(n)$ که خوبه!
پیاده سازیش یکم دردسر داره... ولی بعد از اینکه اون ماتریسا رو دراوردیم و ضرب کردیم، جواب یا همون $f(n)$ میشه خونه هفتم $M_n$!

اینم جواب :

در هر مرحله 6 تا حالت ممکنه اتفاق بیفته که احتمال همشون هم 1/6 هستش پس اگر جواب برای i رو با a(i) نشون بدیم جواب برای n برابر این خواهد بود:

a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)/6 بعلاوه ی یک

که با یه dp ساده حل میشه:

http://pastebin.ubuntu.com/11495952/ نکته 1: خوش حالم که بابت مقدار دهی به 6 تا خانه ی اول ایراد نگرفتید(خودم پاکش کردم)

الان یه ذره بدیهی ترم شد.

نکته 2: جهت افزایش سرعت کامپایل bits/stdc++.h با iostream ویرایش شد.تا بیجهت زمان کامپایل افزایش نیابد.